LibreOJ 2319 「NOIP2017」列队

考虑每行维护一棵线段树，最后一列单独维护。
每次出队的时候更新。
但是空间喜闻乐见地炸掉了。

动态开点即可，用 0 表示还在，用 1 表示被删了。
则需要支持的操作就是查找第 k 个 0 的位置，非常简单。
注意出队的时候，要把这一行最右边新增的点插入。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 3e5;
int n,m,q;
struct node
{
    int sum;
    int ls,rs;
} seg[(N << 6) + 10];
int rt[N + 5],seg_tot;
vector<long long> vec[N + 5];
void insert(int x,int &p,int tl,int tr)
{
    static int tot = 0;
    !p && (p = ++tot),++seg[p].sum;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int query(int k,int p,int tl,int tr)
{
    if(tl == tr)
        return tl;
    int mid = tl + tr >> 1;
    int sum = (mid - tl + 1) - seg[seg[p].ls].sum;
    return k <= sum ? query(k,seg[p].ls,tl,mid) : query(k - sum,seg[p].rs,mid + 1,tr);
}
long long ans,cur;
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    int x,y;
    for(register int i = 1;i <= q;++i)
    {
        scanf("%d%d",&x,&y);
        if(y == m)
        {
            insert(ans = query(x,rt[0],1,n + q),rt[0],1,n + q);
            vec[0].push_back(ans = ans <= n ? (long long)ans * m : vec[0][ans - n - 1]);
        }
        else
        {
            insert(ans = query(y,rt[x],1,m + q),rt[x],1,m + q);
            ans = ans < m ? (long long)(x - 1) * m + ans : vec[x][ans - m];
            insert(cur = query(x,rt[0],1,n + q),rt[0],1,n + q);
            vec[x].push_back(cur = cur <= n ? (long long)cur * m : vec[0][cur - n - 1]),vec[0].push_back(ans);
        }
        printf("%lld\n",ans);
    }
}