列队，NOIP2017 TG D2T3。
树状数组经典题。
题目链接：洛谷。
题意：
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 想要计算每一次离队事件中，离队的同学 的编号是多少。
注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。
题解：
注意到这个方阵被分成了最右侧一列，左侧\(m-1\)列的每一行，共\(n\)行这\(n+1\)个序列。
操作的本质是：每次从其中一个序列中删除一个值，然后在一个序列中加入一个值。
考虑前50%的部分分：
q是非常小的，我们发现可以把与\(x_i\)无关的行排除掉，因为这些行根本不会有操作。
然后维护每行和最后一列即可。
那么前80%呢？
前50%见上文。下面是后30%
注意到所有的操作只在第一行。
我们考虑把第一行和最后一列并在一起，形成新的序列。
这个序列要支持：删除第\(k\)个元素，在末尾加入元素。
可以使用平衡树实现，但是NOIP不考啊？
考虑用树状数组做？怎么做？树状数组维护这一位有没有元素，\(0\)就是没有，\(1\)就是有。
第\(k\)位就是前缀和等于\(k\)。
删除就是\(1\to 0\)。
添加就是\(0\to 1\)，特别的，在末尾添加只要记一个末尾的指针就好了。
怎么找第k位？
树状数组上二分，\(O(log n)\)。
那么100%的数据呢？
发现这个矩阵开始的每一位都确定。
如果我们不维护每一行原来的元素，而是维护新加进来的元素呢？
新加进来的元素总数不会超过\(q\)。
而原来的元素可以直接得到。对于每一行，开一个树状数组来维护答案即可。
这个做法要求离线做，先对所有询问按照\(x_i\)排序，然后按照60%~80%的方法维护。
最后把每行的树状数组（合起来不超过\(q\)个元素），和最后一列的放在一起维护就好了。
时间复杂度\(O(qlog(q)+qlog(m+n+q))\)。
我的代码使用了指针来指向多棵树状数组，是洛谷跑的最快的！1488ms！
代码如下：
#pragma GCC optimize("O2")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;++i)
#define dF(i,a,b) for(int i=a;i>=b;--i)
#define F2(i,a,b) for(int i=a;i<b;++i)
#define getchar() (SS==TT&&(TT=(SS=BB)+fread(BB,1,1<<15,stdin),TT==SS)?EOF:*SS++)
#define RR register
char BB[<<],*SS=BB,*TT=BB;
inline int read(){
RR int x;RR bool f;RR char c;
for (f=; (c=getchar())<''||c>''; f=c=='-');
for (x=c-''; (c=getchar())>=''&&c<=''; x=(x<<)+(x<<)+c-'');
return f?-x:x;
}
using namespace std;
int q,I[];
long long n,m,a[],b[];
inline bool cmp(int p1,int p2){return a[p1]==a[p2]?p1<p2:a[p1]<a[p2];}
int h[],len[],len2[],bit[];
long long arr[];
long long Ans[];
inline void Ins(int*array,int siz,int i,int x){for(;i<=siz;array[i]+=x,i+=i&-i);}
inline int binary(int*array,int siz,int x){
int l=,r,mid,sum,ans;
while(l<=siz&&array[l]<x) l<<=, ans=l;
r=l; sum=array[l>>=];
while(l<r-){
mid=l+r>>;
if(mid>siz||array[mid]+sum>=x) r=mid, ans=mid;
else l=mid, sum+=array[l];
} ans=r;
return ans;
}
int stk[],top;
int main(){
n=read(), m=read(), q=read();
F(i,,q) a[i]=read(), b[i]=read(), I[i]=i;
sort(I+,I+q+,cmp);
F(i,,m-) Ins(bit,m-,i,);
F(i,,n) len[i]=m-;
F(i,,q){
if(a[I[i-]]!=a[I[i]])
while(top) Ins(bit,m-,stk[top--],);
if(b[I[i]]>len[a[I[i]]]) continue;
int pos=binary(bit,m-,b[I[i]]);
Ans[I[i]]=(a[I[i]]-)*m+pos;
Ins(bit,m-,pos,-);
stk[++top]=pos;
--len[a[I[i]]];
}
int iter=;
F(i,,n){
while(iter<=q&&a[I[iter]]<i) ++iter;
h[i]=iter-;
}
h[n+]=q;
memset(bit,,sizeof bit);
F(i,,n) len[i]=, len2[i]=m-; len[n+]=n;
F(i,,n) Ins(bit+h[n+],n+q,i,), arr[q+i]=i*m;
F(i,,q){
if(Ans[i]){
int pos=binary(bit+h[n+],n+q,a[i]);
Ins(bit+h[n+],n+q,pos,-);
Ins(bit+h[n+],n+q,++len[n+],);
arr[h[n+]+len[n+]]=Ans[i];
Ins(bit+h[a[i]],h[a[i]+]-h[a[i]],++len[a[i]],);
arr[h[a[i]]+len[a[i]]]=arr[h[n+]+pos];
--len2[a[i]];
}
else{
int pos=binary(bit+h[n+],n+q,a[i]);
Ins(bit+h[n+],n+q,pos,-);
Ins(bit+h[n+],n+q,++len[n+],);
if(b[i]!=m){
int pos2=binary(bit+h[a[i]],h[a[i]+]-h[a[i]],b[i]-len2[a[i]]);
Ins(bit+h[a[i]],h[a[i]+]-h[a[i]],pos2,-);
Ans[i]=arr[h[a[i]]+pos2];
Ins(bit+h[a[i]],h[a[i]+]-h[a[i]],++len[a[i]],);
arr[h[a[i]]+len[a[i]]]=arr[h[n+]+pos];
} else Ans[i]=arr[h[n+]+pos];
arr[h[n+]+len[n+]]=Ans[i];
}
}
F(i,,q) printf("%lld\n",Ans[i]);
return ;
}