洛谷 P3391 文艺平衡树

本文主要是介绍洛谷 P3391 文艺平衡树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

输入输出格式

输入格式：

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数

接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

输出格式：

输出一行n个数字，表示原始序列经过m次变换后的结果

输入输出样例

输入样例#1：

输出样例#1：

4 3 2 1 5

说明

N,M<=100000

又是一道模板题，怎么那么像线段树啊。

不过好像不太一样，至今不懂啥时候pushdown（想哭）。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,rt,fa[N],tag[N],ch[N][2],sz[N];
void pushup(int x)
{sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
}
void pushdown(int x)
{tag[ch[x][0]]^=1;tag[ch[x][1]]^=1;swap(ch[x][0],ch[x][1]);tag[x]=0;
}
void rotate(int x,int &k)
{int y=fa[x],z=fa[y],lc,rc;if(ch[y][0]==x)lc=0;elselc=1;rc=lc^1;if(y==k)k=x;elsech[z][ch[z][1]==y]=x;fa[x]=z,fa[y]=x;fa[ch[x][rc]]=y;ch[y][lc]=ch[x][rc];ch[x][rc]=y;pushup(y),pushup(x);
}
void splay(int x,int &k)
{while(x!=k){int y=fa[x],z=fa[y];if(y!=k){if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k);elserotate(y,k);}rotate(x,k);}
}
int fnd(int x,int rnk)
{if(tag[x])pushdown(x);int lc=ch[x][0],rc=ch[x][1];if(sz[lc]+1==rnk)return x;if(sz[lc]>=rnk)return fnd(lc,rnk);return fnd(rc,rnk-sz[lc]-1);
}
void split(int l,int r)
{int x=fnd(rt,l),y=fnd(rt,r);splay(x,rt);splay(y,ch[x][1]);
}
void rev(int l,int r)
{split(l,r+2);int x=ch[ch[rt][1]][0];tag[x]^=1;
}
void build(int l,int r,int f)
{if(l>r)return ;if(l==r){fa[l]=f;sz[l]=1;ch[f][l>f]=l;return ;}int mid=(l+r)/2;build(l,mid-1,mid),build(mid+1,r,mid);fa[mid]=f;ch[f][mid>f]=mid;pushup(mid);
}
int main()
{scanf("%d%d",&n,&m);build(1,n+2,0);rt=(n+3)/2;while(m--){int l,r;scanf("%d%d",&l,&r);rev(l,r);}for(int i=2;i<=n+1;i++)printf("%d ",fnd(rt,i)-1);printf("\n");return 0;
}

这篇关于洛谷 P3391 文艺平衡树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！