洛谷P3960 列队
? 解题记录 ? ? 洛谷 ? ? 线段树 ?    2018-10-09 08:42:56    370    0    0

Sylvia是一个热爱学习的女孩子。

前段时间,Sylvia参加了学校的军训。众所周知,军训的时候需要站方阵。 Sylvia所在的方阵中有 n×m 名学生,方阵的行数为 n,列数为 m

为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中的学生从 1 到 n×m 编上了号码(参见后面的样例)。即:初始时,第 i 行第 j 列的学生的编号是 (i−1)×m+j

然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天中,一共发生了 q 件这样的离队事件。每一次离队事件可以用数对 (x,y)1≤x≤n1≤y≤m)描述,表示第 x 行第 y 列的学生离队。

在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达这样的两条指令:

  1. 向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条指令之后,空位在第 x 行第 m 列。
  2. 向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条指令之后,空位在第 n 行第 m 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后,下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 n 行第 m 列一个空位,这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊,所以Sylvia想要计算每一次离队事件中,离队的同学的编号是多少。

注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后方阵中同学的编号可能是乱序的。

输入格式

输入共 q+1 行。

第 1 行包含 3 个用空格分隔的正整数 n,m,q,表示方阵大小是 n 行 m 列,一共发生了 q 次事件。

接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x,y,用一个空格分隔,表示这个离队事件中离队的学生当时排在第 x 行第 y 列。

输出格式

按照事件输入的顺序,每一个事件输出一行一个整数,表示这个离队事件中离队学生的编号。

样例一

input

2 2 3
1 1
2 2
1 2

output

1
1
4

explanation 

列队的过程如上图所示,每一行描述了一个事件。

在第一个事件中,编号为 1 的同学离队,这时空位在第一行第一列。接着所有同学向左标齐,这时编号为 2 的同学向左移动一步,空位移动到第一行第二列。然后所有同学向上标齐,这时编号为 4 的同学向上一步,这时空位移动到第二行第二列。最后编号为 1 的同学返回填补到空位中。

样例二

见样例数据下载。

限制与约定

测试点编号nmq其他约定
1,2≤1000≤1000≤500
3,4
5,6
7,8≤5×104≤5×104
9,10
11,12=1≤105≤105所有事件 x=1
13,14≤3×105≤3×105
15,16≤3×105
17,18≤105≤105≤105
19,20≤3×105≤3×105≤3×105



练习动态开点线段树的好题,考虑对每一行开个线段树,最后一列开个线段树。发现每一行和最后一列在做的操作其实都是把一个数拿走,把后面的数向前平移,把一个数插入在最后。并且查询第k个数。

自然可以想到用坐标离散化的排名来表示每一个数的下标,相当于当平衡树用了。这样每一次操作就是相当于把一个下标位置-1,在最大的下标位置后+1,查询就是爬树查K大。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#define LL long long
#define SGT Segment_Tree_Forest
using namespace std;

const int maxn = 6e5 + 5;
//′óD?:n + q
namespace Segment_Tree_Forest {
    const int L = 0, R = 1;
    struct node {
        int ch[2], sum, down;
        LL num;
    } t[maxn * 70];
    int cnt;
    void push_up(int rt) {
        t[rt].sum = t[t[rt].ch[L]].sum + t[t[rt].ch[R]].sum;
    }
    void push_down(int rt, int tl, int tr) {
        if(t[rt].down) {
            int mid = tl + tr >> 1;
            if(!t[rt].ch[L]) t[rt].ch[L] = ++cnt;
            t[cnt].sum += mid - tl + 1;
            t[cnt].down = 1;
            if(!t[rt].ch[R]) t[rt].ch[R] = ++cnt;
            t[cnt].sum += tr - mid;
            t[cnt].down = 1;
            t[rt].down = 0;
        }
    }
    void add(int l, int r, int tl, int tr, int &rt) {
        if(!rt) rt = ++cnt;
        if(l == tl && r == tr) {
            t[rt].down = 1;
            t[rt].sum += tr - tl + 1;
            return ;
        }
        int mid = tl + tr >> 1;
        push_down(rt, tl, tr);
        if(r <= mid) add(l, r, tl, mid, t[rt].ch[L]);
        else if(l > mid) add(l, r, mid + 1, tr, t[rt].ch[R]);
        else add(l, mid, tl, mid, t[rt].ch[L]),
             add(mid + 1, r, mid + 1, tr, t[rt].ch[R]);
        push_up(rt);
    }
    //posê?????ê÷?D????£???óDk′ó 
    void ins(int pos, int tl, int tr, LL w, int dt, int & rt) {
        if(!rt) rt = ++cnt;
        if(tl == tr) {
            t[rt].num = w;
            return t[rt].sum += dt, void();
        }
        int mid = tl + tr >> 1;
        push_down(rt, tl, tr);
        if(pos <= mid) ins(pos, tl, mid, w, dt, t[rt].ch[L]);
        else ins(pos, mid + 1, tr, w, dt, t[rt].ch[R]);
        push_up(rt);
    }
    int GetRk(int k, int tl, int tr, int rt) {
        if(tl == tr) return tl;
        int mid = tl + tr >> 1;
        push_down(rt, tl, tr);
        if(t[t[rt].ch[L]].sum >= k) 
        return GetRk(k, tl, mid, t[rt].ch[L]);
        else return GetRk(k - t[t[rt].ch[L]].sum, mid + 1, tr, t[rt].ch[R]);
    }
    LL GetNm(int k, int tl, int tr, int rt) {
        if(tl == tr) 
            return t[rt].num;
        int mid = tl + tr >> 1;
        push_down(rt, tl, tr);
        if(t[t[rt].ch[L]].sum >= k) 
        return GetNm(k, tl, mid, t[rt].ch[L]);
        else return GetNm(k - t[t[rt].ch[L]].sum, mid + 1, tr, t[rt].ch[R]);
    }
}

int rt[maxn], mxs[maxn], rtlc, mxlc, n, m, q, x, y;

void line(int x, int y, LL w) {
    int k = SGT::GetRk(y, 1, m + q - 1, rt[x]);
    SGT::ins(k, 1, m + q - 1, 0, -1, rt[x]);
    SGT::ins(++mxs[x], 1, m + q - 1, w, 1, rt[x]);
}

void col(int x, LL w) {
    int k = SGT::GetRk(x, 1, n + q, rtlc);
    SGT::ins(k, 1, n + q, 0, -1, rtlc);
    SGT::ins(++mxlc, 1, n + q, w, 1, rtlc);
}

LL query(int x, int y) {
    LL k;
    if(y == m) {
        k = SGT::GetRk(x, 1, n + q, rtlc);
        if(k <= n) return y + 1ll * m * (k - 1);
        else return SGT::GetNm(x, 1, n + q, rtlc);
    }
    k = SGT::GetRk(y, 1, m + q - 1, rt[x]);
    if(k <= m - 1) return k + 1ll * (x - 1) * m;
    else return SGT::GetNm(y, 1, m + q - 1, rt[x]);//edts[x][k - (m - 1) - 1];
}

void work(int x, int y, LL w) {
    if(y < m) {
        int k = SGT::GetRk(x, 1, n + q, rtlc);
        if(k <= n) line(x, y, 1ll * m * k);
        else line(x, y, SGT::GetNm(x, 1, n + q, rtlc));
    }
    col(x, w);
}

int main() {
    //freopen("testdata.in", "r", stdin);
    //freopen("testdata.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &q);
    for(register int i = 1; i <= n; ++i)
        SGT::add(1, m - 1, 1, m - 1 + q, rt[i]), mxs[i] = m - 1;
    SGT::add(1, n, 1, n + q, rtlc), mxlc = n;
    LL tmp;
    for(register int i = 1; i <= q; ++i) {
        scanf("%d%d", &x, &y);
        printf("%lld\n", tmp = query(x, y));
        work(x, y, tmp);
    }
    return 0;
}




上一篇: 洛谷P1850 换教室

下一篇: 洛谷P3953 逛公园

370 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航