社区讨论

求卡常方法

XXP3301_Pipi
P6781 [Ynoi2008] rupq参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mbwcbcny
此快照首次捕获于
2025/06/14 22:36
8 个月前
此快照最后确认于
2025/11/04 07:10
4 个月前
查看原帖
rt，已经大战此题整整20h，惨遭卡常，求有没有好的卡常方法
FHQ-Treap 和 Splay 都试了一遍，都卡不过去
本地测试已经从20s卡到6s
FHQ:
CPP
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define Ckmax(x,y) x=max(x,y)
#define Ckmin(x,y) x=min(x,y)
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N=2e6+5;
const int IINF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}

template<typename Type>
inline void read(Type &res){
    Type x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    res=x*f;
}

mt19937 seed(time(0));
const uint FUL=0xffffffff;

int n,Q;
bool a[N];
uint b[N];
int val[N];

struct Data{
	uint s0,s1,mx;
	
	friend Data operator + (Data x,Data y){
		return Data{(x.s0&y.s1)|((~x.s0)&y.s0),(x.s1&y.s1)|((~x.s1)&y.s0),max(x.mx,y.mx)};
	}
}EPT;

#define Init(x) Data{FUL,~(x),(x)}
#define likely(x) __builtin_expect(!!(x),1)

struct FHQTreap{
	int ls,rs,pri;
	int cl,cr;
	int x; uint v; 
	Data vl,vr,rst;
	int siz;	
}tr[N];

int root;

void Print(int p){
	 if(!p) puts("EMPTY");
	 else 
    printf("Tr[%d]: ls=%d,rs=%d,Bs=(%d,%d),V=(%d,%d),Vl=%u,Vr=%u,Rst=%u,Siz=%d\n",p,tr[p].ls,tr[p].rs,tr[p].cl,tr[p].cr,tr[p].x,tr[p].v,tr[p].vl.mx,tr[p].vr.mx,tr[p].rst.mx,tr[p].siz);
}

void Print(int p,string s,bool fir){
	cout<<s<<(fir?"+---":"\\---"); Print(p);
	if(!p) return;
	s+=(fir?"|    ":"    ");
	Print(tr[p].ls,s,1);
	Print(tr[p].rs,s,0);
}

Data AskL(int p,int k){
	if(!p||tr[p].cl<=k) return EPT;
	if(!k) return tr[p].vl;
	Data res=EPT;
	while(1){
		if(!p||tr[p].cl<=k) break;
		if(!k){res=tr[p].vl+res;break;}
		int pls=tr[p].ls,prs=tr[p].rs;
		int cl=tr[pls].cl+max(0,(!tr[p].x)-tr[pls].cr);
		int cr=tr[p].x+max(0,tr[pls].cr-(!tr[p].x));
		if(likely(cl<=k)) p=prs,k=k-cl+cr;
		else{
			res=tr[prs].rst+res;
			if(likely(!tr[p].x&&!tr[pls].cr)) res=Init(tr[p].v)+res;
			p=pls;
		}
	}
	return res;
}

Data AskR(int p,int k){
	if(!p||tr[p].cr<=k) return EPT;
	if(!k) return tr[p].vr;
	Data res=EPT;
	while(1){
		if(!p||tr[p].cr<=k) break;
		if(!k){res=res+tr[p].vr;break;}
		int pls=tr[p].ls,prs=tr[p].rs;
		int cl=(!tr[p].x)+max(0,tr[prs].cl-tr[p].x);
		int cr=tr[prs].cr+max(0,tr[p].x-tr[prs].cl);
		if(likely(cr<=k)) p=pls,k=k-cr+cl;
		else{
			res=res+tr[pls].rst;
			if(likely(tr[p].x&&!tr[prs].cl)) res=res+Init(tr[p].v);
			p=prs;
		}
	}
	return res;
}

inline void Pushup(int p){
//	printf("Pushup(%d,%d,%d)\n",p,tr[p].ls,tr[p].rs);
	int pcl=0,pcr=0; 
	int ls=tr[p].ls,rs=tr[p].rs;
	if(tr[p].x){
		pcl=0,tr[p].vl=tr[ls].vl;
		pcr=1,tr[p].vr=(!tr[rs].cl)?(Init(tr[p].v)+tr[rs].vr):tr[rs].vr;
	}
	else{
		pcr=0,tr[p].vr=tr[rs].vr;
		pcl=1,tr[p].vl=(!tr[ls].cr)?(tr[ls].vl+Init(tr[p].v)):tr[ls].vl;
	}
	
	tr[p].cr=pcr+max(0,tr[ls].cr-pcl);
	tr[p].vl=tr[p].vl+(tr[rs].rst=AskL(rs,tr[p].cr));
	tr[p].cr=tr[rs].cr+max(0,tr[p].cr-tr[rs].cl);
	
	tr[p].cl=pcl+max(0,tr[rs].cl-pcr);
	tr[p].vr=(tr[ls].rst=AskR(ls,tr[p].cl))+tr[p].vr;
	tr[p].cl=tr[ls].cl+max(0,tr[p].cl-tr[ls].cr);
	
	tr[p].siz=tr[ls].siz+tr[rs].siz+1;
//	Print(p);
}

void Buildtr(int p){
	if(!p) return;
	Buildtr(tr[p].ls);
	Buildtr(tr[p].rs);
	Pushup(p);
}

void Split(int p,int k,int &L,int &R){
	if(!p) return L=R=0,void();
	if(tr[tr[p].ls].siz>=k){
		R=p; Split(tr[p].ls,k,L,tr[p].ls);
		Pushup(p);
	}
	else{
		L=p; Split(tr[p].rs,k-tr[tr[p].ls].siz-1,tr[p].rs,R);
		Pushup(p);
	}
}

int Merge(int p,int q){
	if(!p) return q;
	if(!q) return p;
	if(tr[p].pri>tr[q].pri){
		tr[p].rs=Merge(tr[p].rs,q);
		Pushup(p); return p;
	}
	else{
		tr[q].ls=Merge(p,tr[q].ls);
		Pushup(q); return q;
	}
}

void Update(int x,uint y){
	int L,M,R;
	Split(root,x-1,L,R);
	Split(R,1,M,R);
	tr[M].x^=1,tr[M].v=y;
	if(tr[M].x){
		tr[M].cl=0,tr[M].vl=EPT;
		tr[M].cr=1,tr[M].vr=Init(tr[M].v);
	}
	else{
		tr[M].cl=1,tr[M].vl=Init(tr[M].v);
		tr[M].cr=0,tr[M].vr=EPT;
	}
	root=Merge(L,Merge(M,R));
}

inline uint Ask(int l,int r){
	int L,M,R;
	Split(root,r,L,R);
	Split(L,l-1,L,M);
	Data dat=tr[M].vl+tr[M].vr;
	uint res=dat.mx^dat.s1;
	root=Merge(L,Merge(M,R));
	return res;
}

inline void Swap(int l,int r){
	int L,M,R;
	Split(root,r,L,R);
	Split(L,l-1,L,M);
	root=Merge(L,Merge(R,M));
}

signed main(){
//	FileIO();
	read(n),read(Q);
	EPT={0,FUL,0};
	tr[0].vl=tr[0].vr=EPT;
	for(int i=1;i<=n;i++){
		read(a[i]),read(b[i]);
		val[i]=i;
		tr[i].x=a[i],tr[i].v=b[i];
	}
	shuffle(val+1,val+n+1,seed);
	val[0]=2e9;
	stack<int> stk;
	stk.push(0);
	for(int i=1;i<=n;i++){
		int x=0;
		while(val[i]>val[stk.top()])
			x=stk.top(),stk.pop();
		tr[stk.top()].rs=i; tr[i].ls=x;
		tr[i].pri=val[i];
		if(!stk.top()) root=i;
		stk.push(i);
	}
	Buildtr(root);
//	 Print(root,"",1);
	while(Q--){
		int op; read(op);
		if(op==1){
			int x; uint y;
			read(x),read(y);
			Update(x,y);
		}
		else if(op==2){
			int l,r;
			read(l),read(r);
			printf("%u\n",Ask(l,r));
		}
		else if(op==3){
			int l,r;
			read(l),read(r);
			Swap(l,r);
		}
//		 Print(root,"",1);
	}
    return 0;
}
Splay:
CPP
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define Ckmax(x,y) x=max(x,y)
#define Ckmin(x,y) x=min(x,y)
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N=2e6+5;
const int IINF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}

template<typename Type>
inline void read(Type &res){
    Type x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    res=x*f;
}

mt19937 seed(time(0));
const uint FUL=0xffffffff;

int n,Q;
int a[N];
uint b[N];

struct Data{
	uint s0,s1,mx;
	
	friend Data operator + (Data x,Data y){
		return Data{(x.s0&y.s1)|((~x.s0)&y.s0),(x.s1&y.s1)|((~x.s1)&y.s0),max(x.mx,y.mx)};
	}
};

#define Init(x) Data{FUL,~(x),(x)}
#define EPT Data{0,FUL,0}
#define likely(x) __builtin_expect(!!(x),1)

struct SplayNode{
	int s[2],fa;
	int cl,cr;
	int x; uint v;
	Data vl,vr,rst;
	int siz;
	#define ls s[0]
	#define rs s[1]
}tr[N]; 

int root,tot;

void Print(int p){
	 if(!p) puts("EMPTY");
	 else 
    printf("Tr[%d]: ls=%d,rs=%d,Bs=(%d,%d),V=(%d,%d),Vl=%u,Vr=%u,Rst=%u,Siz=%d\n",p,tr[p].ls,tr[p].rs,tr[p].cl,tr[p].cr,tr[p].x,tr[p].v,tr[p].vl.s1,tr[p].vr.s1,tr[p].rst.s1,tr[p].siz);
}

void Print(int p,string s,bool fir){
	cout<<s<<(fir?"+---":"\\---"); Print(p);
	if(!p) return;
	s+=(fir?"|    ":"    ");
	Print(tr[p].ls,s,1);
	Print(tr[p].rs,s,0);
}

Data AskL(int p,int k){
	if(!p||tr[p].cl<=k) return EPT;
	if(!k) return tr[p].vl;
	Data res=EPT;
	while(1){
		if(!p||tr[p].cl<=k) break;
		if(!k){res=tr[p].vl+res;break;}
		int pls=tr[p].ls,prs=tr[p].rs;
		int cl=tr[pls].cl+max(0,(!tr[p].x)-tr[pls].cr);
		int cr=tr[p].x+max(0,tr[pls].cr-(!tr[p].x));
		if(likely(cl<=k)) p=prs,k=k-cl+cr;
		else{
			res=tr[prs].rst+res;
			if(likely(!tr[p].x&&!tr[pls].cr)) res=Init(tr[p].v)+res;
			p=pls;
		}
	}
	return res;
}

Data AskR(int p,int k){
	if(!p||tr[p].cr<=k) return EPT;
	if(!k) return tr[p].vr;
	Data res=EPT;
	while(1){
		if(!p||tr[p].cr<=k) break;
		if(!k){res=res+tr[p].vr;break;}
		int pls=tr[p].ls,prs=tr[p].rs;
		int cl=(!tr[p].x)+max(0,tr[prs].cl-tr[p].x);
		int cr=tr[prs].cr+max(0,tr[p].x-tr[prs].cl);
		if(likely(cr<=k)) p=pls,k=k-cr+cl;
		else{
			res=res+tr[pls].rst;
			if(likely(tr[p].x&&!tr[prs].cl)) res=res+Init(tr[p].v);
			p=prs;
		}
	}
	return res;
}

inline void Pushup(int p){
//	printf("Pushup(%d,%d,%d)\n",p,tr[p].ls,tr[p].rs);
	int pcl=0,pcr=0; 
	int pls=tr[p].ls,prs=tr[p].rs;
	if(tr[p].x==1){
		pcl=0,tr[p].vl=tr[pls].vl;
		pcr=1,tr[p].vr=(!tr[prs].cl)?(Init(tr[p].v)+tr[prs].vr):tr[prs].vr;
	}
	else if(tr[p].x==0){
		pcr=0,tr[p].vr=tr[prs].vr;
		pcl=1,tr[p].vl=(!tr[pls].cr)?(tr[pls].vl+Init(tr[p].v)):tr[pls].vl;
	}
	else{
		pcl=0,tr[p].vl=tr[pls].vl;
		pcr=0,tr[p].vr=tr[prs].vr;
	}
	
	tr[p].cr=pcr+max(0,tr[pls].cr-pcl);
	tr[p].vl=tr[p].vl+(tr[prs].rst=AskL(prs,tr[p].cr));
	tr[p].cr=tr[prs].cr+max(0,tr[p].cr-tr[prs].cl);
	
	tr[p].cl=pcl+max(0,tr[prs].cl-pcr);
	tr[p].vr=(tr[pls].rst=AskR(pls,tr[p].cl))+tr[p].vr;
	tr[p].cl=tr[pls].cl+max(0,tr[p].cl-tr[pls].cr);
	
	tr[p].siz=tr[pls].siz+tr[prs].siz+1;
//	Print(p);
}

void Buildtr(int &p,int l,int r,int pr){
	p=++tot; int mid=(l+r)>>1;
	tr[p].fa=pr; tr[p].x=a[mid],tr[p].v=b[mid];
	if(l!=mid) Buildtr(tr[p].ls,l,mid-1,p);
	if(r!=mid) Buildtr(tr[p].rs,mid+1,r,p);
	Pushup(p);
}

inline int Dir(int p){return tr[tr[p].fa].rs==p;}

void Rotate(int x){
	int y=tr[x].fa,z=tr[y].fa,c=Dir(x);
	tr[y].s[c]=tr[x].s[c^1];
	if(tr[x].s[c^1]) tr[tr[x].s[c^1]].fa=y;
	tr[x].s[c^1]=y; tr[y].fa=x;
	tr[x].fa=z;
	tr[z].s[y==tr[z].rs]=x;
	Pushup(y); Pushup(x);
}

void Splay(int x,int z){
	while(tr[x].fa!=z){
		int y=tr[x].fa;
		if(tr[y].fa!=z)
			Rotate(Dir(x)==Dir(y)?y:x);
		Rotate(x);
	}
	if(!z) root=x;
}

int AskNode(int p,int k){
//	printf("AskNode(%d)=",k);
	while(1){
		if(tr[tr[p].ls].siz+1==k) break;
		else if(tr[tr[p].ls].siz>=k) p=tr[p].ls;
		else k-=tr[tr[p].ls].siz+1,p=tr[p].rs;
	}
//	printf("%d\n",p);
	return p;
}

void Update(int x,uint y){
	int p=AskNode(root,x+1);
	tr[p].x^=1,tr[p].v=y;
	Pushup(p); Splay(p,0);
}

uint Ask(int l,int r){
	int p=AskNode(root,l); Splay(p,0);
	int q=AskNode(root,r+2); Splay(q,p);
	Data res=tr[tr[q].ls].vl+tr[tr[q].ls].vr;
	return res.mx^res.s1;
}

void Swap(int l,int r){
	if(r==n) return;
	int p=AskNode(root,l); Splay(p,0);
	int q=AskNode(root,r+2); Splay(q,p);
	int z=AskNode(root,n+1);
	if(tr[z].rs) Rotate(tr[z].rs);
	tr[z].rs=tr[q].ls; tr[q].ls=0;
	Pushup(z),Pushup(q);
	Splay(z,0);
}

signed main(){
	read(n),read(Q);
	for(int i=1;i<=n;i++) read(a[i]),read(b[i]);
	a[0]=a[n+1]=-1;
	tr[0].vl=tr[0].vr=tr[0].rst=EPT;
	Buildtr(root,0,n+1,0);
//	Print(root,"",1);
	while(Q--){
		int op; read(op);
		if(op==1){
			int x; uint y;
			read(x),read(y);
			Update(x,y);
		}
		else if(op==2){
			int l,r; read(l),read(r);
			printf("%u\n",Ask(l,r));
		}
		else if(op==3){
			int l,r; read(l),read(r);
			Swap(l,r);
		}
//		Print(root,"",1);
	}
}

回复

共 4 条回复，欢迎继续交流。

正在加载回复...