离noip只有一天了，我终于搞懂了线段树的骚操作，为了加深理解以及帮助一下和我之前一样不会平衡树（其实我会一点）但却看不懂线段树的思路的小可爱们，当然，~~**不会有人和我一样菜的**~~。
下面讲一讲思路，主要参考@ Sakura_梦瑶 大佬的 根据线段树二分的性质来维护一个序列是十分方便的，像这类有主席树和动态点开线段树，这里我使用的是动态点开线段树（其实在这之前我都不知道有这玩意儿）。
然而，我skyshow~~境泽~~就是死，就是从这跳下去也不用动态，这辈子都不用vector，所以，我选择使用以静态来模拟动态，我们用n+1棵线段树来分别维护n行的前m-1列，第n+1棵来维护第m列，这样，就可以了，然而值得指出的是，这里所构建的线段树不同于像打的板子一样的那种（当然，有人也许一开始就打的板子和我的不一样），这一点我耗费了很长时间才弄懂。
下面是代码，先发我最开始写错的~~（惊喜吧！）~~
```cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
long long stree[666666];
long long cnt;
long long n,m,q;
long long us[6666666];
long long num[6666666];
long long num1;
long long x,y;
long long lson[6666666];
long long rson[6666666];
long long sum[666666];
long long doa;
bool flag;
void insert(long long &pos,long long l,long long r,long long k,long long th){
if(!pos){
pos=++cnt;
}
if(l==r){
num[pos]=k;
return;
}
long long mid=l+r>>1;
long long cur=(mid-l+1);
if(cur>=th){
insert(lson[pos],l,mid,k,th);
}
else insert(rson[pos],mid+1,r,k,th-cur);
}
void find_th(long long &pos,long long l,long long r,long long th){
if(!pos){
pos=++cnt;
}
us[pos]++;
if(l==r){
if(num[pos]){
num1=num[pos];
}
else if(flag){
num1=(x-1)*m+l;
}
else{
num1=l*m;
}
return;
}
long long mid=l+r>>1;
long long cur=(mid-l+1)-us[lson[pos]];
if(cur>=th){
find_th(lson[pos],l,mid,th);
}
else find_th(rson[pos],mid+1,r,th-cur);
return;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&q);
for(long long iakioi=1;iakioi<=q;iakioi++){
scanf("%lld%lld",&x,&y);
if(y==m){
flag=0;
//printf("%lld %lld\n",x,y);
find_th(stree[n+1],1,n+q,x);
printf("%lld\n",num1);
long long th=++sum[n+1];
insert(stree[n+1],1,n+q,num1,n+th);
}
else{
flag=1;
find_th(stree[x],1,m+q,y);
printf("%lld\n",num1);
doa=num1;
y=m;
find_th(stree[n+1],1,n+q,x);
long long th=++sum[x];
insert(stree[x],1,m+q,num1,m+th);
th=++sum[n+1];
insert(stree[n+1],1,n+q,doa,n+th);
}
}
return 0;
}
```
为什么我要先发一波错误代码呢？，其实不是想坑人什么的，是想提醒大家细节真的超重要，对比代码要来了，你们留意一下区别，详细注释也在下面
```cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
long long stree[666666];//这里不是指线段树，而是那几颗线段树的初始根节点
long long cnt;//线段树节点
long long n,m,q;
long long us[6666666];
long long num[6666666];//66666666什么的，不要在意啦
long long num1;
long long x,y;
long long lson[6666666];//左子树根节点
long long rson[6666666];//右子树根节点
long long sum[666666];//当前线段树扩展的节点数
long long doa;//辅助储存功能
bool flag;//分辨是否是前m-1行的
void insert(long long &pos,long long l,long long r,long long k,long long th){//注意&符号
if(!pos){
pos=++cnt;//-》当前节点编号
}
if(l==r){
num[pos]=k;
return;
}
long long mid=l+r>>1;
long long cur=(mid-l+1);
if(cur>=th){//不懂先看主程序
insert(lson[pos],l,mid,k,th);
}
else insert(rson[pos],mid+1,r,k,th-cur);
}
void find_th(long long &pos,long long l,long long r,long long th){//注意&符号
if(!pos){
pos=++cnt;
}
us[pos]++;//表示这一段中有多少节点出队列，这样就可以维护了，想一想为什么（l==r时被确定了，所以不用担心）
if(l==r){
if(num[pos]){
num1=num[pos];
}
else if(flag){//flag为真表示在前m-1列
num1=(x-1)*m+l;//这里很显然是l
}
else{
num1=l*m;
}
return;
}
long long mid=l+r>>1;
long long cur=(mid-l+1)-us[lson[pos]];
if(cur>=th){
find_th(lson[pos],l,mid,th);
}
else find_th(rson[pos],mid+1,r,th-cur);
return;
}
int main(){//从主程序开始看代码是个好习惯
scanf("%lld%lld%lld",&n,&m,&q);
for(long long iakioi=1;iakioi<=q;iakioi++){//皮这一下，开森
scanf("%lld%lld",&x,&y);
if(y==m){
flag=0;
//printf("%lld %lld\n",x,y);
find_th(stree[n+1],1,n+q,x);
printf("%lld\n",num1);
long long th=++sum[n+1];
insert(stree[n+1],1,n+q,num1,n+th);
}
else{
flag=1;
find_th(stree[x],1,m+q-1,y);
printf("%lld\n",num1);
doa=num1;
y=m;
flag=0;
find_th(stree[n+1],1,n+q,x);
long long th=++sum[x];
insert(stree[x],1,m+q-1,num1,m+th-1);//注意这里是m-1+q和m+th-1，血的教训
th=++sum[n+1];
insert(stree[n+1],1,n+q,doa,n+th);
}
}
return 0;
}
```
另外，建议在考场上没有很大自信的话就不要强求正解，不然一个细节就爆零了很吃亏，我调了一上午，无数次怀疑自己写错了，最后睡了个午觉才发现（睡午觉有益身心健康）。
再看不懂的可以私信我，但一定要指出哪里不懂
另外求管理员能在10号之前过审核啊，您最帅了~~（不会是小姐姐吧）~~