超级 FHQ-treap 出现神秘问题,悬赏20元。
查看原帖
超级 FHQ-treap 出现神秘问题,悬赏20元。
550471
Ice_function楼主2025/1/8 17:00

如题,在初步调试过后猜测是 push_down 或者push_np(resize) 的问题

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+10,UDF=-0x3f3f3f3f;

int n,q,a[N];

struct node{
	int val,S,rk,ls,rs,size,tagrev,tagdif,sx,lx,rx;
};

struct treap{
	node tr[N];
	int tot=1,root=1;
	int newnode(int val){tr[++tot]={val,0,rand(),0,0,1,0,UDF,UDF,UDF,UDF};return tot;}
	void resize(int u)
	{
		auto a=tr[tr[u].ls],b=tr[tr[u].rs];
		tr[u].S=a.S+b.S+tr[u].val;
		tr[u].size=a.size+b.size+1;
		tr[u].tagdif=UDF,tr[u].tagrev=0;
		tr[u].lx=max({0,a.lx,a.S+tr[u].val,a.S+tr[u].val+b.lx});
		tr[u].rx=max({0,b.rx,b.S+tr[u].val,b.S+tr[u].val+a.rx});
		tr[u].sx=max({0,a.sx,b.sx,tr[u].val,tr[u].val+a.rx,tr[u].val+b.lx,tr[u].val+a.rx+b.lx});
	}

	void push_down(int u)
	{
		if (tr[u].tagrev)
		{
			tr[tr[u].ls].tagrev^=1,tr[tr[u].rs].tagrev^=1;
			swap(tr[u].ls,tr[u].rs);
			resize(u);
			tr[u].tagrev=0;
		}
		if (tr[u].tagdif!=UDF)
		{
			tr[tr[u].ls].tagdif=tr[tr[u].rs].tagdif=tr[u].tagdif;
			tr[u].S=tr[u].size*tr[u].tagdif;
			if (tr[u].tagdif>0) tr[u].sx=tr[u].lx=tr[u].rx=tr[u].S;
			else tr[u].sx=tr[u].lx=tr[u].rx=tr[u].S;
			resize(u);
			tr[u].tagdif=UDF;
		}
	}
	void split(int now,int rk,int &l,int &r)
	{
		if (!now){l=r=0;return;}
		push_down(now);
		int siz=tr[tr[now].ls].size;
		if (rk<=siz) r=now,split(tr[now].ls,rk,l,tr[now].ls);
		else l=now,split(tr[now].rs,rk-siz-1,tr[now].rs,r);
		resize(now);
	}
	int merge(int u,int v)
	{
		if (!u || !v) return u+v;
		if (tr[u].rk<tr[v].rk)
		{
			push_down(u);
			tr[u].rs=merge(tr[u].rs,v);
			resize(u);
			return u;
		}
		else
		{
			push_down(v);
			tr[v].ls=merge(u,tr[v].ls);
			resize(v);
			return v;
		}
	}
	int ins[N];
	void insert(int pos,int tot)
	{
		int l,r;
		split(root,pos,l,r);
		for (int i=1;i<=tot;i++) l=merge(l,newnode(ins[i]));
		root=merge(l,r);
	}
	void del(int pos,int tot)
	{
		int L=pos+1,R=pos+tot;
		int l,mid,r;
		split(root,R,l,r);
		split(l,L-1,l,mid);
		root=merge(l,r);
	}
	void modify(int pos,int tot,int x)
	{
		int L=pos+1,R=pos+tot;
		int l,mid,r;
		split(root,R,l,r);
		split(l,L-1,l,mid);
		tr[mid].tagdif=x;
		root=merge(merge(l,mid),r);
	}
	void reverse(int pos,int tot)
	{
		int L=pos+1,R=pos+tot;
		int l,mid,r;
		split(root,R,l,r);
		split(l,L-1,l,mid);
		tr[mid].tagrev^=1;
		root=merge(merge(l,mid),r);
	}
	int queryS(int pos,int tot)
	{
		int L=pos+1,R=pos+tot;
		int l,mid,r;
		split(root,R,l,r);
		split(l,L-1,l,mid);
		int ans=tr[mid].S;
		root=merge(merge(l,mid),r);
		return ans;
	}
	int queryQ(){return tr[root].sx;}
};

int main()
{
	srand(time(0));
	scanf("%d %d",&n,&q);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	treap tre;
	for (int i=1;i<=n;i++) tre.root=tre.merge(tre.root,tre.newnode(a[i]));
	
	for (int opt=1;opt<=q;opt++)
	{
		char op[10];int pos,tot,x;
		scanf("%s",op);
		if (op[0]=='I')
		{
			scanf("%d %d",&pos,&tot);
			for (int i=1;i<=tot;i++) scanf("%d",&tre.ins[i]);
			tre.insert(pos,tot);
		}
		else if (op[0]=='D')
		{
			scanf("%d %d",&pos,&tot);
			tre.del(pos,tot);
		}
		else if (op[2]=='K')
		{
			scanf("%d %d %d",&pos,&tot,&x);
			tre.modify(pos,tot,x);
		}
		else if (op[0]=='R')
		{
			scanf("%d %d",&pos,&tot);
			tre.reverse(pos,tot);
		}
		else if (op[0]=='G')
		{
			scanf("%d %d",&pos,&tot);
			printf("%d\n",tre.queryS(pos,tot));
		}
		else if (op[2]=='X') printf("%d\n",tre.queryQ());
	}
	
	return 0;
}
2025/1/8 17:00
加载中...