P3391 【模板】文艺平衡树（@无旋Treap,* *）

【模板】文艺平衡树 - 洛谷

题目描述

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

其中需要提供以下操作：翻转一个区间，例如原有序序列是 5 4 3 2 1，翻转区间是 [2,4] 的话，结果是 5 2 3 4 1

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

5 3
1 3
1 3
1 4

输出 #1复制

4 3 2 1 5

说明/提示

【数据范围】
对于 100% 的数据，1≤𝑛,𝑚≤100000，1≤𝑙≤𝑟≤𝑛。

解析： 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<stdio.h>
using namespace std;
typedef long long LL;
//#define int LL
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const LL Mod = 998244353;
const int N = 1e7 + 10, M = 1 << 15;
int n, m;
int rt;
struct Treap {
	int son[N][2], s[N],w[N],pro[N];
	int idx;
	bool fl[N];
	int build(int x) {
		w[++idx] = x, s[idx] = 1, pro[idx] = rand();
		return idx;
	}
	void up(int u) {
		s[u] = s[son[u][1]] + s[son[u][0]] + 1;
	}
	void pushdown(int u) {
		swap(son[u][1], son[u][0]);
		int l = son[u][0], r = son[u][1];
		if (l)fl[l] ^= 1;
		if (r)fl[r] ^= 1;
		fl[u] = 0;
	}
	int merge(int l, int r) {
		if (!l || !r) {
			return l + r;
		}
		if (pro[l] < pro[r]) {
			if (fl[l])pushdown(l);
			son[l][1] = merge(son[l][1], r);
			up(l);
			return l;
		}
		if (fl[r])pushdown(r);
		son[r][0] = merge(l, son[r][0]);
		up(r);
		return r;
	}
	void split(int u,int k,int &l,int&r) {
		if (!u) {
			l = r = 0;
			return;
		}
		if (fl[u])pushdown(u);
		int &lch = son[u][0],& rch = son[u][1];
		if (k > s[lch]) {
			l = u;
			split(rch, k - s[lch] - 1, rch, r);
		}
		else {
			r = u;
			split(lch, k, l, lch);
		}
		up(u);
	}

	void coutt(int u) {
		if (!u)return;
		if (fl[u])pushdown(u);
		coutt(son[u][0]);
		printf("%d ", w[u]);
		coutt(son[u][1]);
	}
}tr;

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		rt=tr.merge(rt, tr.build(i));
	}
	while (m--) {
		int l, r, a, b, c;
		scanf("%d%d", &l, &r);
		tr.split(rt, l - 1, a, b);
		tr.split(b, r-l+1, b, c);

		tr.fl[b] ^= 1;
		rt=tr.merge(a, b);
		rt = tr.merge(rt, c);
	}
	tr.coutt(rt);
	return 0;
}