样例过了，但一个点都没跑过去，可能是区间合并出了问题，救救孩子吧孩子调了好久都没调出来呜呜呜
题目:跳树
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
int op[N];
int n,m,q;
struct tree{
int fa,son;//最高跳到第几辈祖先和最高位跳到第几代儿子
int path;//路径
tree (){
memset(this,0,sizeof(tree));
}
tree operator+(const tree &p2)const{
tree ans;
ans=*this;
if(!p2.fa||!son){
ans.path=path<<p2.son|p2.path;
ans.fa+=p2.fa;
ans.son+=p2.son;
}
else if(p2.fa>=son){//被全部抹去
ans.fa+=(p2.fa-son);
ans.son=p2.son;
ans.path=p2.path;
}
else{//只抹去了一部分
ans.path=(path>>(son-p2.fa)<<p2.son|p2.path);
ans.son+=(p2.son-p2.fa);
}
return ans;
}
}sgm[N*4];
void build(int p,int pl,int pr){
if(pl==pr){
if(op[pl]==3) sgm[p].fa=1;
else sgm[p].son=1;
if(op[pl]==2) sgm[p].path=1;
return ;
}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
sgm[p]=sgm[ls(p)]+sgm[rs(p)];
}
tree query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r){
return sgm[p];
}
tree res;
int mid=(pl+pr)>>1;
if(l<=mid) {
res=res+query(ls(p),pl,mid,l,r);
}
if(mid+1<=r) {
res=res+query(rs(p),mid+1,pr,l,r);
}
return res;
}
void update(int p,int pl,int pr,int x,int tp){
if(pl==pr&&pl==x){
sgm[p].son=0,sgm[p].fa=0,sgm[p].path=0;
if(tp==3) sgm[p].fa=1;
else sgm[p].son=1;
if(tp==2) sgm[p].path=1;
return ;
}
int mid=(pl+pr)>>1;
if(x<=mid) update(ls(p),pl,mid,x,tp);
if(mid+1<=x) update(rs(p),mid+1,pr,x,tp);
sgm[p]=sgm[ls(p)]+sgm[rs(p)];
}
signed main(){
cin>>n>>m>>q;
for(int i=1;i<=m;i++) cin>>op[i];
build(1,1,m);
while(q--){
int op1;
cin>>op1;
if(op1==1){
int s,l,r;
tree need;
cin>>s>>l>>r;
need=query(1,1,m,l,r);
s=max(1LL,s>>need.fa)<<need.son|need.path;
cout<<s<<endl;
}
else{
int x,y;
cin>>x>>y;
update(1,1,m,x,y);
}
}
return 0;
}