传送门：洛谷 - P3391
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列
其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5 4 3 2 1$，翻转区间是 $[2,4]$ 的话，结果是 $5 2 3 4 1$
输入描述
第一行两个正整数 $n$,$m$，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$
接下来 $m$ 行，每行两个正整数 $l$,$r$表示翻转的区间
输出描述
输出一行 $n$ 个正整数，表示原始序列经过 $m$ 次变换后的结果
思路分析
按大小分裂
如果是用splay的话，考虑对区间$[l,r]$翻转，先将$l$的前驱旋转懂根节点，再将$r$的后继旋转到根节点的儿子，那么$[l,r]$整个区间就在$r$的后继的左儿子中了，打上标记就行了
样例输入
5 3
1 3
1 3
1 4
样例输出
4 3 2 1 5
Splay代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a, b) memset(a,b,sizeof(a))
namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if (p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if (pend == p1) {
IOerror = 1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template<class T>
inline bool read(T &x) {
bool sign = 0;
char ch = nc();
x = 0;
for (; blank(ch); ch = nc());
if (IOerror)return false;
if (ch == '-')sign = 1, ch = nc();
for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
if (sign)x = -x;
return true;
}
template<class T, class... U>
bool read(T &h, U &... t) {
return read(h) && read(t...);
}
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
struct node {
int siz, fa, sum, val, ch[2], lazy;
void clear() {
siz = fa = sum = val = ch[0] = ch[1] = lazy = 0;
}
} tree[N];
int n,q;
int root, cnt;
#define ls tree[x].ch[0]
#define rs tree[x].ch[1]
void pp(int x) {
tree[x].siz = tree[ls].siz + tree[rs].siz + tree[x].sum;
}
void pd(int x) {
if (tree[x].lazy) {
swap(ls, rs);
tree[ls].lazy ^= 1;
tree[rs].lazy ^= 1;
tree[x].lazy ^= 1;
}
}
void connect(int x, int f, int s) {
tree[f].ch[s] = x;
tree[x].fa = f;
}
void rotate(int x) {
int f = tree[x].fa;
int ff = tree[f].fa;
int fs = tree[f].ch[1] == x;
int ffs = tree[ff].ch[1] == f;
connect(tree[x].ch[fs ^ 1], f, fs);
connect(x, ff, ffs);
connect(f, x, fs ^ 1);
pp(f);
pp(x);
}
void splay(int x, int top) {
if (!top) root = x;
while (tree[x].fa != top) {
int f = tree[x].fa;
int ff = tree[f].fa;
if (ff != top) (tree[f].ch[1] == x) ^ (tree[ff].ch[1] == f) ? rotate(x) : rotate(f);
rotate(x);
}
}
void newnode(int &x, int fa, int val) {
x = ++cnt;
tree[x].clear();
tree[x].fa = fa;
tree[x].val = val;
tree[x].siz = tree[x].sum = 1;
}
void ins(int &x, int fa, int val) {
if (!x) {
newnode(x, fa, val);
splay(x, 0);
} else if (val < tree[x].val) {
ins(ls, x, val);
} else if (val > tree[x].val) {
ins(rs, x, val);
} else {
tree[x].sum++;
splay(x, 0);
}
}
int getnum(int rank) {
int x = root;
while (x) {
pd(x);
int lsiz = tree[ls].siz;
if (lsiz + 1 <= rank && rank <= lsiz + tree[x].sum) {
splay(x, 0);
break;
}
if (lsiz < rank) {
rank -= lsiz + tree[x].sum;
x = tree[x].ch[1];
} else {
x = tree[x].ch[0];
}
}
return x;
}
void reverse(int l, int r) {
l = getnum(l - 1);
r = getnum(r + 1);
splay(l, 0);
splay(r, l);
tree[tree[r].ch[0]].lazy^=1;
}
void print(int x){
if(!x) return ;
pd(x);
print(ls);
if(tree[x].val>=1 && tree[x].val<=n) printf("%d ",tree[x].val);
print(rs);
}
int main() {
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n,q);
ins(root,0,-INF);
ins(root,0,INF);
for(int i=1;i<=n;i++) ins(root,0,i);
while(q--){
int l,r;
read(l,r);
reverse(l+1,r+1);
}
print(root);
return 0;
}
fhq treap代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=1e5+10;
struct node {
int l,r;
int val,key;
int size;
bool lazy;
} tree[N];
int cnt,root;
int newnode(int val) {
tree[++cnt].val=val;
tree[cnt].key=rand();
tree[cnt].size=1;
return cnt;
}
void update(int now) {
tree[now].size=tree[tree[now].l].size+tree[tree[now].r].size+1;
}
void pushdown(int now) {
if(tree[now].lazy) {
swap(tree[now].l,tree[now].r);
tree[tree[now].l].lazy^=1;
tree[tree[now].r].lazy^=1;
tree[now].lazy=false;
}
}
void split(int now,int siz,int &x,int &y) {
if(!now)x=y=0;
else {
pushdown(now);
if(tree[tree[now].l].size<siz) {
x=now;
split(tree[now].r,siz-tree[tree[now].l].size-1,tree[x].r,y);
} else {
y=now;
split(tree[now].l,siz,x,tree[y].l);
}
update(now);
}
}
int merge(int x,int y) {
if(!x||!y)
return x+y;
if(tree[x].key<tree[y].key) {
pushdown(x);
tree[x].r=merge(tree[x].r,y);
update(x);
return x;
} else {
pushdown(y);
tree[y].l=merge(x,tree[y].l);
update(y);
return y;
}
}
void reverse(int l,int r) {
int x,y,z;
split(root,l-1,x,y);
split(y,r-l+1,y,z);
tree[y].lazy^=1;
root=merge(merge(x,y),z);
}
void print(int now) {
if(!now)
return ;
pushdown(now);
print(tree[now].l);
cout<<tree[now].val<<" ";
print(tree[now].r);
}
int main() {
IOS;
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
root=merge(root,newnode(i));
while(m--) {
int l,r;
cin>>l>>r;
reverse(l,r);
}
print(root);
return 0;
}
