萌新fhqtreap没过样例求调
查看原帖
萌新fhqtreap没过样例求调
310773
PCCP楼主2023/7/28 22:42

RT,蒟蒻看了一边讨论区,感觉好像没什么问题,但是就是过不了样例,求助大佬们帮蒟蒻看看到底哪里出错了(

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<random>
#include<vector>
using namespace std;
const int N=5e5+10;
const int INF=1e9;
vector<int> q;
int sta[N],cnt,a[N];
struct fhq{
	int root,tot=1;
	int ch[N][2],val[N],siz[N],sum[N],lms[N],rms[N],mms[N],lare[N],laco[N];
	int newnode(int k){
		int id=sta[cnt--];
		lare[id]=ch[id][0]=ch[id][1]=0;lms[id]=rms[id]=max(0,k);
		mms[id]=val[tot]=sum[id]=k;siz[id]=1;laco[id]=-INF;
		return id;
	}
	void pushup(int pos){
		siz[pos]=siz[ch[pos][0]]+siz[ch[pos][1]]+1;sum[pos]=sum[ch[pos][0]]+sum[ch[pos][1]];
		lms[pos]=max(lms[ch[pos][0]],sum[ch[pos][0]]+lms[ch[pos][1]]);
		rms[pos]=max(rms[ch[pos][1]],sum[ch[pos][1]]+rms[ch[pos][0]]);
		mms[pos]=max({lms[pos],rms[pos],rms[ch[pos][0]]+lms[ch[pos][1]],mms[ch[pos][0]],mms[ch[pos][1]]});
	}
	void reverse(int x){
		swap(ch[x][0],ch[x][1]);swap(lms[x],rms[x]);lare[x]^=1;
	}
	void cover(int x,int k){
		sum[x]=siz[x]*k;lms[x]=rms[x]=max(0,sum[x]);mms[x]=max(k,sum[x]);laco[x]=k;
	}
	void pushdown(int x){
		if(!x){
			return;
		}
		if(lare[x]){
			if(ch[x][0]){
				reverse(ch[x][0]);
			}
			if(ch[x][1]){
				reverse(ch[x][1]);
			}
			lare[x]=false;
		}
		if(laco[x]!=-INF){
			if(ch[x][0]){
				cover(ch[x][0],laco[x]);
			}
			if(ch[x][1]){
				cover(ch[x][1],laco[x]);
			}
			laco[x]=-INF;
		}
	}
	void split(int pos,int k,int &x,int &y){
		if(!pos){
			x=y=0;
			return;
		}
		pushdown(pos);
		if(siz[ch[pos][0]]+1<=k){
			x=pos;
			split(ch[pos][1],k-siz[ch[pos][0]]-1,ch[x][1],y);
		}
		else{
			y=pos;
			split(ch[pos][0],k,x,ch[y][0]);
		}
		pushup(pos);
	}
	int merge(int x,int y){
		if(!x||!y){
			return x+y;
		}
		if(90000008%(siz[x]+siz[y])<siz[x]){
			pushdown(x);
			ch[x][1]=merge(ch[x][1],y);
			pushup(x);
			return x;
		}
		else{
			pushdown(y);
			ch[y][0]=merge(x,ch[y][0]);
			pushup(y);
			return y;
		}
	}
	void era(int x){
		if(!x){
			return;
		}
		sta[++cnt]=x;
		if(ch[x][0]){
			era(ch[x][0]);
		}
		if(ch[x][1]){
			era(ch[x][1]);
		}
	}
	int build(int l,int r){
		if(l==r){
			return newnode(a[l]);
		}
		int mid=(l+r)>>1;
		return merge(build(l,mid),build(mid+1,r));
	}
}tr;
int n,m;
string s;
int main(){
	scanf("%d%d",&n,&m);
	int x,y,k;
	for(int i=1;i<=500001;i++){
		sta[++cnt]=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	tr.root=tr.merge(tr.root,tr.build(1,n));
	while(m--){
		cin>>s;
//		cout<<"s: "<<s<<endl;
		if(s=="INSERT"){
			scanf("%d%d",&x,&y);
			for(int i=1;i<=y;i++){
				scanf("%d",&a[i]);
			}
			int u,v;
			tr.split(tr.root,x,u,v);
			u=tr.merge(u,tr.build(1,y));
			tr.root=tr.merge(u,v);
		}
		else if(s=="DELETE"){
			scanf("%d%d",&x,&y);
			int u,v,w;
			tr.split(tr.root,x-1,u,v);
			tr.split(v,y,v,w);
			tr.era(v);
			tr.root=tr.merge(u,w);
		}
		else if(s=="MAKE-SAME"){
			scanf("%d%d%d",&x,&y,&k);
			int u,v,w;
			tr.split(tr.root,x-1,u,v);
			tr.split(v,y,v,w);
			tr.cover(v,k);
			v=tr.merge(u,v);
			tr.root=tr.merge(v,w);
		}
		else if(s=="REVERSE"){
			scanf("%d%d",&x,&y);
			int u,v,w;
			tr.split(tr.root,x-1,u,v);
			tr.split(v,y,v,w);
			tr.reverse(v);
			v=tr.merge(v,w);
			tr.root=tr.merge(u,v);
		}
		else if(s=="GET-SUM"){
			int u,v,w;
			scanf("%d%d",&x,&y);
			cout<<"CASE 5: "<<endl;
			tr.split(tr.root,x-1,u,v);
			tr.split(v,y,v,w);
			printf("%d\n",tr.sum[v]);
//			cout<<"????????????????"<<endl;
			v=tr.merge(u,v);
			tr.root=tr.merge(v,w);
		}
		else{
			int u,v,w;
			cout<<"CASE 6: "<<endl;
			printf("%d\n",tr.mms[tr.root]);
		}
	}
} 
2023/7/28 22:42
加载中...