洛谷P3960 列队

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

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

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

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

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

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

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

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

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

输入格式

输入共 $q + 1$ 行。

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

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

输出格式

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

样例一

input

output

1
1
4

explanation

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

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

样例二

见样例数据下载。

限制与约定

测试点编号	$n$	$m$	$q$	其他约定
1,2	$\leq 1000$	$\leq 1000$	$\leq 500$	无
3,4
5,6
7,8	$\leq 5 \times 10^{4}$	$\leq 5 \times 10^{4}$
9,10	$\leq 5 \times 10^{4}$	$\leq 5 \times 10^{4}$
11,12	$= 1$	$\leq 10^{5}$	$\leq 10^{5}$	所有事件 $x = 1$
13,14	$= 1$	$\leq 3 \times 10^{5}$	$\leq 3 \times 10^{5}$
15,16	$\leq 3 \times 10^{5}$	$\leq 3 \times 10^{5}$	$\leq 3 \times 10^{5}$
17,18	$\leq 10^{5}$	$\leq 10^{5}$	$\leq 10^{5}$	无
19,20	$\leq 3 \times 10^{5}$	$\leq 3 \times 10^{5}$	$\leq 3 \times 10^{5}$	无

练习动态开点线段树的好题，考虑对每一行开个线段树，最后一列开个线段树。发现每一行和最后一列在做的操作其实都是把一个数拿走，把后面的数向前平移，把一个数插入在最后。并且查询第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;
}

Rockdu's Blog