P3391 【模板】文艺平衡树

【模板】文艺平衡树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间。

输入格式

第一行两个正整数 \(n,m\)，表示序列长度与操作个数。序列中第 \(i\) 项初始为 \(i\)。
接下来 \(m\) 行，每行两个正整数 \(l,r\)，表示翻转的区间。

输出格式

输出一行 \(n\) 个正整数，表示原始序列经过 \(m\) 次变换后的结果。

【数据范围】
对于 \(100\%\) 的数据，$1 \le n, m \leq 100000 $，\(1 \le l \le r \le n\)。

感觉和模板平衡树很像，唯一的区别就是这题不用按点权分裂，而是直接按节点个数分裂

每次交换操作就直接给区间打tag，然后交换左右儿子
最后统计的时候直接中序dfs就好了

Code:

#include<bits/stdc++.h>
#include<ctime>
const int N=1e5+5;
using namespace std;
struct Tree{
	int val,tag,siz,pri,ls,rs;
}t[N<<2];
int n,m,cnt,rt;
int new_(int w=0)
{
	int x=++cnt;
	t[x].val=w,t[x].siz=1,t[x].pri=rand();
	return x;
}
void upd(int x)
{
	t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
}
void pushdown(int x)
{
	if(!t[x].tag)return ;
	t[x].tag=0;
	t[t[x].ls].tag^=1;
	t[t[x].rs].tag^=1;
	swap(t[x].ls,t[x].rs);
	return ;
}
void split(int x,int k,int &a,int &b)
{
	if(!x){a=b=0;return;}
	pushdown(x);
	if(k<=t[t[x].ls].siz)
	{
		b=x;
		split(t[b].ls,k,a,t[b].ls);
		upd(b);
	}
	else
	{
		a=x;k-=(t[t[x].ls].siz+1);
		split(t[a].rs,k,t[a].rs,b);
		upd(a);
	}
}
int merge(int x,int y)
{
	if(!x||!y)return x+y;
	if(t[x].pri<t[y].pri)
	{
		pushdown(x);
		t[x].rs=merge(t[x].rs,y);
		upd(x);
		return x;
	}
	else
	{
		pushdown(y);
		t[y].ls=merge(x,t[y].ls);
		upd(y);
		return y;
	}
}
queue<int> Q;
void calc(int x)
{
	if(!x)return ;
	pushdown(x);
	calc(t[x].ls);
	Q.push(t[x].val);
	calc(t[x].rs);
}
void work()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		rt=merge(rt,new_(i));
	}
	for(int i=1,l,r;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		int a=0,b=0,c=0;
		split(rt,l-1,a,b);//a[1,l-1] : b[l,n]
		split(b,r-l+1,b,c);//b[l,r] : c[r+1,n]
		//cout<<"val:"<<t[a].val<<" "<<t[b].val<<" "<<t[c].val<<"\n";
		//cout<<"siz:"<<t[a].siz<<" "<<t[b].siz<<" "<<t[c].siz<<"\n";
		t[b].tag^=1;
		rt=merge(merge(a,b),c);
	}
	calc(rt);
	while(!Q.empty())
	{
		printf("%d ",Q.front());
		Q.pop();
	}
}
int main()
{
	//freopen("P3391.in","r",stdin);
	srand(clock());
	work();
}