社区讨论
不知道错哪了,求调
P4344[SHOI2015] 脑洞治疗仪参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lyr9r643
- 此快照首次捕获于
- 2024/07/18 20:50 2 年前
- 此快照最后确认于
- 2024/07/18 22:15 2 年前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node{
int sum,maxa,maxl,maxr,size,val;
int Lazy=-1;
}tree[800008];
int n,m;
void down(int p){
tree[p*2].Lazy=tree[p].Lazy;
tree[p*2+1].Lazy=tree[p].Lazy;
if(tree[p].Lazy==0){
tree[p*2].sum=tree[p*2].maxa=tree[p*2].maxl=tree[p*2].maxr=tree[p*2].size;
tree[p*2+1].sum=tree[p*2+1].maxa=tree[p*2+1].maxl=tree[p*2+1].maxr=tree[p*2+1].size;
}else if(tree[p].Lazy==1){
tree[p*2].sum=tree[p*2].maxa=tree[p*2].maxl=tree[p*2].maxr=0;
tree[p*2+1].sum=tree[p*2+1].maxa=tree[p*2+1].maxl=tree[p*2+1].maxr=0;
}
tree[p].Lazy=-1;
}
void push_up(int p){
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
if(tree[p*2].size==tree[p*2].sum) tree[p].maxl=tree[p*2].size+tree[p*2+1].maxl;
else tree[p].maxl=tree[p*2].maxl;
if(tree[p*2+1].size==tree[p*2+1].sum) tree[p].maxr=tree[p*2+1].size+tree[p*2].maxr;
else tree[p].maxl=tree[p*2+1].maxr;
tree[p].size=tree[p*2].size+tree[p*2+1].size;
tree[p].maxa=max(max(tree[p*2].maxr+tree[p*2+1].maxl,tree[p*2].maxa),tree[p*2+1].maxa);
}
void build(int p,int l,int r){
if(l==r) tree[p].val=tree[p].size=1;
else{
build(p*2,l,(l+r)/2);
build(p*2+1,(l+r)/2+1,r);
push_up(p);
}
}
void change(int p,int l,int r,int L,int R,int c){
if(l>=L&&r<=R){
tree[p].Lazy=c;
tree[p].val=c;
if(c==0) tree[p].sum=tree[p].maxa=tree[p].maxl=tree[p].maxr=tree[p].size;
else tree[p].sum=tree[p].maxa=tree[p].maxl=tree[p].maxr=0;
}else{
down(p);
//cout<<l<<" "<<r<<endl;
if((l+r)/2>=L) change(p*2,l,(l+r)/2,L,R,c);
if((l+r)/2<R) change(p*2+1,(l+r)/2+1,r,L,R,c);
push_up(p);
}
}
int Find(int p,int l,int r,int L,int R){ //查询L到R中有多少个非脑洞
down(p);
int ans=0;
if(l>=L&&r<=R) return tree[p].size-tree[p].sum;
if((l+r)/2>=L) ans+=Find(p*2,l,(l+r)/2,L,R);
if((l+r)/2<R) ans+=Find(p*2+1,(l+r)/2+1,r,L,R);
return ans;
}
int erfen(int p,int l,int r,int L,int R,int k){ //二分求L到R的第k个脑洞位置
down(p);
//if(tree[p].sum<k) return -1;
if(l==r) return l;
if((l+r)/2>=R) return erfen(p*2,l,(l+r)/2,L,R,k);
else if((l+r)/2<L) return erfen(p*2+1,(l+r)/2,l,L,R,k);
int aa=L-(l+r)/2+1-Find(p*2,L,(l+r)/2,L,R);
if(aa<k) return erfen(p*2+1,(l+r)/2+1,r,L,R,k-aa);
else return erfen(p*2,l,(l+r)/2,L,R,k);
}
Node outt(int p,int l,int r,int L,int R){ //查询L到R有连续的脑洞长度最大值
down(p);
Node a1,a2;
if(l>=L&&r<=R) return tree[p];
if((l+r)/2>=L) a1=outt(p*2,l,(l+r)/2,L,R);
if((l+r)/2<R) a2=outt(p*2+1,(l+r)/2+1,r,L,R);
else return a1;
if((l+r)/2<L) return a2;
Node tp;
tp.sum=a1.sum+a2.sum;
if(a1.size==a1.sum) tp.maxl=a1.size+a2.maxl;
else tp.maxl=a1.maxl;
if(a2.size==a2.sum) tp.maxr=a2.size+a1.maxr;
else tp.maxl=a2.maxr;
tp.size=a1.size+a2.size;
tp.maxa=max(max(a1.maxr+a2.maxl,a1.maxa),a2.maxa);
return tp;
}
signed main(){
cin>>n>>m;
build(1,1,n);
//for(int i=1;i<n*2;i++) cout<<tree[i].val<<" ";
//cout<<Find(1,1,n,1,n)<<endl;
while(m--){
int op;
cin>>op;
if(op==0){
int l,r;
cin>>l>>r;
change(1,1,n,l,r,0);
}else if(op==1){
int l,r,l1,r1;
cin>>l>>r>>l1>>r1;
int k=Find(1,1,n,l,r);
change(1,1,n,l,r,0);
int aa=Find(1,1,n,l1,r1);
if(r1-l1+1-aa<=k){
change(1,1,n,l1,r1,1);
}else{
int ggg=erfen(1,1,n,l1,r1,k);
//cout<<"啊啊啊啊"<<ggg<<endl;
//if(ggg==-1) ggg=n;
change(1,1,n,l1,ggg,1);
}
}else{
int l,r;
cin>>l>>r;
cout<<outt(1,1,n,l,r).maxa<<endl;
}
//for(int i=1;i<=25;i++) cout<<i<<":"<<tree[i].val<<"|";
//cout<<Find(1,1,n,1,n)<<endl;
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...