毒瘤数据结构题
传送门：$>here<$
题意：给出一个$N*M$的方阵，每个人依次编号。有一个人离队，所有人先向左看齐，再向右看齐（挤占空位）。然后离队的人再回到队伍右下角站好。整个过程中人的编号不变。有$Q$次离队事件，给出离队位置，询问每一次离队的人的编号。
数据范围：$N,M,Q leq 3*10^5$
$Solution$
考虑用$N$棵线段树分别维护每一排的前$M-1$个人，第$N+1$棵线段树维护最后一列的人。我们的线段树是权值线段树，对于每一排（列也一样），第$l$个叶子对应原始排列的第$l$个人，值为0或1，维护的是这个位置的人是否还在这个位置。其实就是让权值线段树来干平衡树该干的事。
由于最多加入$Q$个人，所以线段树多开$Q$个位置初始化为0。刚开始建树时，对于前面有人的位置建1，否则建0
插入比较有趣，例如$(x,y)$这个人离队，那么首先删去第$x$棵线段树中排名为$y$的人，再删去第$N+1$棵线段树中排名为$x$的人。将后者插到第$x$棵线段树的最后，在将前者插入到第$N+1$棵线段树的最后。
现在有个问题，空间太大，根本不行……
考虑总共只有$Q$次离队，意味着很多节点是根本用不到的。考虑动态开点！
动态开点在这里的意思是，只开我们要用到的节点。对于那些没有用过的节点，形象一点，意味着这些点在队列中根本没有动过——即保持初始位置。这样我们就可以"算"出来了。询问到一个点，如果这个点还没有开过，就意味着它是满的。
$my code$
细节很多难以调试，我调试了好几天了（其实一个月前就开始做了……）
/*By DennyQi 2018*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define int ll const int MAXN = 1010; const int INF = 1061109567; inline int Max(const int a, const int b){ return (a > b) ? a : b; } inline int Min(const int a, const int b){ return (a < b) ? a : b; } inline int read(){ int x = 0; int w = 1; register char c = getchar(); for(; c ^ '-' && (c < '0' || c > '9'); c = getchar()); if(c == '-') w = -1, c = getchar(); for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w; } int N,M,Q,numNode,x,y,L,psn1,psn2,mx_lst,cnt; int rt[300010],lst[300010],idx[60000010],ls[6000010],rs[60000010],size[60000010]; inline int get_size(int l, int r, int x){ if(x == N+1) return Max(Min(r,N)-l+1, 0); else return Max(Min(r,M-1)-l+1, 0); } int query(int& o, int l, int r, int k, int x){ if(!o){ o = ++cnt; size[o] = get_size(l, r, x); if(l == r){ if(x == N+1){ idx[o] = M * l; } else{ idx[o] = M*(x-1) + l; } } } if(l == r){ return idx[o]; } int lsize, mid=(l+r)/2; if(!ls[o]) lsize = get_size(l,mid,x); else lsize = size[ls[o]]; if(lsize >= k){ return query(ls[o], l, mid, k, x); } else{ return query(rs[o], mid+1, r, k-lsize, x); } } void modify(int& o, int l, int r, int k, int x, int p, int id, int pos){ if(!o){ o = ++cnt; size[o] = get_size(l, r, x); if(l == r){ if(x == N+1){ idx[o] = M * l; } else{ idx[o] = M*(x-1) + l; } } } size[o] += p; if(l == r){ if(p == 1){ idx[o] = id; } else{ if(p == -1 && x==N+1){ psn2 = idx[o]; idx[o] = 0; } } return; } int lsize, mid=(l+r)/2; if(!ls[o]){ lsize = get_size(l, mid, x); }else{ lsize = size[ls[o]]; } if(p == 1){ if(mid >= pos){ modify(ls[o], l, mid, k, x, p, id, pos); } else{ modify(rs[o], mid+1, r, k, x, p, id, pos); } return; } if(lsize >= k){ modify(ls[o], l, mid, k, x, p, id, pos); } else{ modify(rs[o], mid+1, r, k-lsize, x, p, id, pos); } } signed main(){ // freopen(".in","r",stdin); N = read(), M = read(), Q = read(); for(int i = 1; i <= N; ++i){ lst[i] = M-1; } lst[N+1] = N; for(int i = 1; i <= Q; ++i){ x = read(), y = read(); if(y == M){ psn1 = query(rt[N+1], 1, N+Q, x, N+1); printf("%lld ", psn1); modify(rt[N+1], 1, N+Q, x, N+1, -1, psn1, 0); modify(rt[N+1], 1, N+Q, N, N+1, 1, psn1, ++lst[N+1]); } else{ psn1 = query(rt[x], 1, M+Q, y, x); printf("%lld ", psn1); modify(rt[x], 1, M+Q, y, x, -1, 0, 0); modify(rt[N+1], 1, N+Q, x, N+1, -1, 0, 0); modify(rt[x], 1, M+Q, M-1, x, 1, psn2, ++lst[x]); modify(rt[N+1], 1, N+Q, N, N+1, 1, psn1,++lst[N+1]); } } return 0; }