社区讨论

不知道错哪了,求调

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 条回复,欢迎继续交流。

正在加载回复...