离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号之前过审核啊,您最帅了~~(不会是小姐姐吧)~~