【洛谷 P3391】 文藝平衡樹 【平衡樹】

【洛谷 P3391】 文藝平衡樹

題目大意：

寫一種資料結構支援靜态區間的翻轉操作。

思路：

考慮使用線段樹中的懶标記，每次區間發生變化時遇到懶标記就下傳。

每次下傳時懶标記 x o r   1 xor ~1 xor 1，就是如果沒有懶标記那麼就打上，如果以前有的話那麼說明這個區間翻轉了兩次，和沒翻轉一樣。

使用平衡樹 fhq Treap 解決。

注意分裂的時候不是按照權值分裂了，而是前 k 個。

所謂的模闆題

代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#include<ctime>
#define r register
#define rep(i,x,y) for(r ll i=x;i<=y;++i)
#define per(i,x,y) for(r ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=1e5+10;
ll a[V],n,m,q,root,cnt;
ll u,v,x,y,z;
inline ll in()
{
	ll res=0,f=1;
	char ch;
	while((ch=getchar())<'0'||ch>'9')
	 if(ch=='-') f=-1;
	res=res*10+ch-48;
	while((ch=getchar())>='0'&&ch<='9')
	 res=res*10+ch-48;
	return res*f;
}
inline void put(ll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) put(x/10);
	putchar(x%10+48);
}
struct fhqtreap
{
	ll lc,rc,pos;
	ll siz,val,lazy;
}treap[110003];
void update(ll x) { treap[x].siz=treap[treap[x].lc].siz+treap[treap[x].rc].siz+1; }
ll newnode(ll x) 
{
	treap[++cnt].val=x;
	treap[cnt].siz=1;
	treap[cnt].pos=rand();
	return cnt;
}
void pushdown(ll x) //懶标記的下傳
{
	swap(treap[x].lc,treap[x].rc);
	treap[treap[x].lc].lazy^=1;
	treap[treap[x].rc].lazy^=1;
	treap[x].lazy=0;
}
void split(ll now,ll k,ll &x,ll &y)
{
	if(now==0)
	{
		x=y=0;
		return ;
	}
	if(treap[now].lazy) pushdown(now);
	if(k>=treap[treap[now].lc].siz+1)
	{
		x=now;
		split(treap[now].rc,k-treap[treap[now].lc].siz-1,treap[now].rc,y);
	}
	else 
	{
		y=now;
		split(treap[now].lc,k,x,treap[now].lc);
	}
	update(now);
}
ll make(ll x,ll y)
{
	if(x==0||y==0) return x+y;
	if(treap[x].pos<treap[y].pos)
	{
		if(treap[x].lazy) pushdown(x); //記得及時下傳懶标記
		treap[x].rc=make(treap[x].rc,y);
		update(x);
		return x;
	}
	else 
	{
		if(treap[y].lazy) pushdown(y);
		treap[y].lc=make(x,treap[y].lc);
		update(y);
		return y;
	}
}
ll K(ll now,ll k)
{
	while(1+1==2)
	{
		if(k<=treap[treap[now].lc].siz) now=treap[now].lc;
		else if(k==treap[treap[now].lc].siz+1) return now;
		else k-=(treap[treap[now].lc].siz+1),now=treap[now].rc;
	}
}
void print(ll now) //中序周遊輸出答案
{
	if(now==0) return ;
	if(treap[now].lazy) pushdown(now);
	if(treap[now].lc) print(treap[now].lc);
	printf("%lld ",treap[now].val);
	if(treap[now].rc) print(treap[now].rc);
}
int main()
{
	n=in(),m=in();
	rep(i,1,n)
	 root=make(root,newnode(i));
	rep(i,1,m)
	{
		
		u=in(),v=in();
		split(root,v,x,z);//1~v->x,v+1->z
		split(x,u-1,x,y);//1~u-1->x,u~v->y
		treap[y].lazy^=1;
		root=make(make(x,y),z);
	}
	print(root);
	return 0;
}