兄弟们求助卡常,AC n <= 150000
  • 板块P5350 序列
  • 楼主_Aurore_
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/28 15:15
  • 上次更新2023/11/3 12:14:53
查看原帖
兄弟们求助卡常,AC n <= 150000
593595
_Aurore_楼主2023/6/28 15:15

就是这分毒瘤代码,正确性没有问题,但是人傻常数大

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=3e5+10,mod=1e9+7;
int rot,tot;
struct node{
	int l,r;
	int siz,w,key,sum;
	bool tag;//反转标记
	int odt,add;//区间推平标记,加法标记 
}t[MAXN*11];
void pushup(int i){
	t[i].siz=t[t[i].l].siz+t[t[i].r].siz+1;
	t[i].sum=((t[t[i].l].sum+t[t[i].r].sum)%mod+t[i].w)%mod;
}
int newnode(int x){
	t[++tot].siz=1;
	t[tot].w=t[tot].sum=x;
	t[tot].key=rand();
	t[tot].odt=-1;
	return tot;
}
int copynode(node A){
	t[++tot]=A;
	return tot;
}
void reverse(int i){
	if(!i) return ;
	int ls=t[i].l,rs=t[i].r;
	if(ls) t[i].r=copynode(t[ls]);
	else t[i].r=0;
	if(rs) t[i].l=copynode(t[rs]);
	else t[i].l=0;
	t[i].tag^=1;
}
void pushdown(int i){
	if(!i) return ;
	int ls=t[i].l,rs=t[i].r;
	if(ls) t[i].l=copynode(t[ls]);
	else t[i].l=0;
	if(rs) t[i].r=copynode(t[rs]);
	else t[i].r=0;
	if(t[i].odt!=-1){
		t[t[i].l].odt=t[t[i].r].odt=t[i].odt;
		t[t[i].l].w=t[t[i].r].w=t[i].odt;
		t[t[i].l].add=t[t[i].r].add=0;
		t[t[i].l].sum=(1ll*t[t[i].l].siz*t[i].odt)%mod;
		t[t[i].r].sum=(1ll*t[t[i].r].siz*t[i].odt)%mod;
		t[i].odt=-1;
	}
	if(t[i].add){
		t[t[i].l].add=(t[t[i].l].add+t[i].add)%mod;
		t[t[i].r].add=(t[t[i].r].add+t[i].add)%mod;
		t[t[i].l].w=(t[t[i].l].w+t[i].add)%mod;
		t[t[i].r].w=(t[t[i].r].w+t[i].add)%mod;
		t[t[i].l].sum=(t[t[i].l].sum+(1ll*t[t[i].l].siz*t[i].add)%mod)%mod;
		t[t[i].r].sum=(t[t[i].r].sum+(1ll*t[t[i].r].siz*t[i].add)%mod)%mod;
		t[i].add=0;
	}
	if(t[i].tag){
		reverse(t[i].l);
		reverse(t[i].r);
		t[i].tag=0;
	}
}
void split(int i,int v,int &l,int &r){
	if(!i){
		l=r=0;
		return ;
	}
	pushdown(i);
	if(t[t[i].l].siz+1<=v){
		l=copynode(t[i]);
		split(t[l].r,v-t[t[i].l].siz-1,t[l].r,r);
		pushup(l);
	}
	else{
		r=copynode(t[i]);
		split(t[r].l,v,l,t[r].l);
		pushup(r);
	}
}
int merge(int l,int r){
	if(!l||!r) return l+r;
	if(t[l].key<=t[r].key){
		pushdown(l);
		int id=copynode(t[l]);
		t[id].r=merge(t[id].r,r);
		pushup(id);
		return id;
	}
	else{
		pushdown(r);
		int id=copynode(t[r]);
		t[id].l=merge(l,t[id].l);
		pushup(id);
		return id;
	}
}
int query(int L,int R){
	int l,mid,r;
	split(rot,R,l,r);
	split(l,L-1,l,mid);
	return t[mid].sum;
}
void ODT(int L,int R,int w){
	int l,mid,r;
	split(rot,R,l,r);
	split(l,L-1,l,mid);
	t[mid].add=0;
	t[mid].odt=t[mid].w=w;
	t[mid].sum=(1ll*t[mid].siz*w%mod);
	rot=merge(merge(l,mid),r);
}
void update(int L,int R,int w){
	int l,mid,r;
	split(rot,R,l,r);
	split(l,L-1,l,mid);
	t[mid].add=(t[mid].add+w)%mod;
	t[mid].w=(t[mid].w+w)%mod;
	t[mid].sum=(t[mid].sum+(1ll*t[mid].siz*w)%mod)%mod;
	rot=merge(merge(l,mid),r);
}
void copy(int l1,int r1,int l2,int r2){
	bool flag=0;
	if(l1>r2){
		swap(l1,l2);
		swap(r1,r2);
		flag=1;
	} 
	int l,mid1,mid2,mid3,r;
	split(rot,r2,l,r);
	split(l,l2-1,l,mid3);//l2<=mid2<=r2
	split(l,r1,l,mid2);
	split(l,l1-1,l,mid1);//l1<=mid1<=r1
	if(!flag){
		rot=merge(l,merge(mid1,merge(mid2,merge(copynode(t[mid1]),r))));
	}//复制的顺序是正常的 
	else{
		rot=merge(l,merge(copynode(t[mid3]),merge(mid2,merge(mid3,r))));
	}//复制顺序是颠倒的 
}
void Swap(int l1,int r1,int l2,int r2){
	if(l1>r2){
		swap(l1,l2);
		swap(r1,r2);
	} 
	int l,mid1,mid2,mid3,r;
	split(rot,r2,l,r);
	split(l,l2-1,l,mid3);//l2<=mid2<=r2
	split(l,r1,l,mid2);
	split(l,l1-1,l,mid1);//l1<=mid1<=r1
	rot=merge(l,merge(mid3,merge(mid2,merge(mid1,r))));
}
void rever(int L,int R){
	int l,mid,r;
	split(rot,R,l,r);
	split(l,L-1,l,mid);
	reverse(mid);
	rot=merge(merge(l,mid),r);
}
int n,q,top,a[MAXN];
void dfs(int i){
	if(!i) return ;
	pushdown(i);
	dfs(t[i].l);
	a[++top]=t[i].w;
	dfs(t[i].r); 
}
int build(int l,int r){
	if(l==r)
		return newnode(a[l]);
	int mid=(l+r)/2;
	int ls=build(l,mid);
	int rs=build(mid+1,r);
	return merge(ls,rs);
}
void print(int i){
	if(!i) return ;
	print(t[i].l);
	printf("%d ",t[i].w);
	print(t[i].r);
}
void rebuild(bool flag){
	top=0;
	dfs(rot);
	memset(t,0,sizeof(t));
	rot=tot=0;
	rot=build(1,top);
	if(!flag) return ;
	print(rot);
}
signed main(){
	//freopen("1.in","r",stdin); 
	//freopen("2.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	rot=build(1,n);
	int last=0;
	while(q--){
		int opt=read();
		if(opt==1){
			int l=read(),r=read();
			last=query(l,r);
			printf("%d\n",last);
		}
		else if(opt==2){
			int l=read(),r=read(),w=read();
			ODT(l,r,w);
		}
		else if(opt==3){
			int l=read(),r=read(),w=read();
			update(l,r,w);
		}
		else if(opt==4){
			int l1=read(),r1=read(),l2=read(),r2=read();
			copy(l1,r1,l2,r2); 
		}
		else if(opt==5){
			int l1=read(),r1=read(),l2=read(),r2=read();
			Swap(l1,r1,l2,r2); 
		}
		else{
			int l=read(),r=read();
			rever(l,r);
		}
		if(tot>MAXN*9) rebuild(0);
	}
	rebuild(1);
	return 0;
}
2023/6/28 15:15
加载中...