#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>
#define rep(i) for (int i=0; i<n; i++)
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
const int N = 100005, inf = 0x3f3f3f3f;
typedef struct Splay* node;
struct Splay {
node pre, ch[2];
ll value, lazy, max, sum;
int size, rev;
void init(int _value) {
pre = ch[0] = ch[1] = NULL;
max = value = sum = _value;
lazy = rev = 0;
size = 1;
}
}tr[N];
int idx,top;
node S[N];
node root;
inline int getsize(node &x) {
return x ? x->size : 0;
}
void push_down(node &x) {
if (!x) return;
if (x->lazy) {
ll w = x->lazy;
x->value += w;
if (x->ch[0]) {
x->ch[0]->lazy += w;
x->ch[0]->max += w;
x->ch[0]->sum += w * getsize(x->ch[0]);
}
if (x->ch[1]) {
x->ch[1]->lazy += w;
x->ch[1]->max += w;
x->ch[1]->sum += w * getsize(x->ch[1]);
}
x->lazy = 0;
}
if (x->rev) {
node t = x->ch[0];
x->ch[0] = x->ch[1];
x->ch[1] = t;
x->rev = 0;
if (x->ch[0]) x->ch[0]->rev ^= 1;
if (x->ch[1]) x->ch[1]->rev ^= 1;
}
}
void pushup(node &x) {
if (!x) return;
x->size = 1;
x->max = x->value;
x->sum = x->value;
if (x->ch[0]) {
x->sum += x->ch[0]->sum;
x->max = max(x->max, x->ch[0]->max);
x->size += x->ch[0]->size;
}
if (x->ch[1]) {
x->sum += x->ch[1]->sum;
x->max = max(x->max, x->ch[1]->max);
x->size += x->ch[1]->size;
}
}
void rotate(node &x, int d) {
node y = x->pre;
push_down(y);
push_down(x);
push_down(x->ch[d]);
y->ch[!d] = x->ch[d];
if (x->ch[d] != NULL) x->ch[d]->pre = y;
x->pre = y->pre;
if (y->pre != NULL)
if (y->pre->ch[0] == y) y->pre->ch[0] = x; else y->pre->ch[1] = x;
x->ch[d] = y;
y->pre = x;
pushup(y);
if (y == root) root = x;
}
void splay(node &src, node &dst) {
push_down(src);
while (src != dst) {
if (src->pre == dst) {
if (dst->ch[0] == src) rotate(src,1); else rotate(src,0);
break;
}
else {
node y = src->pre, z = y->pre;
if (z->ch[0] == y) {
if (y->ch[0] == src) {
rotate(y,1);
rotate(src,1);
}else {
rotate(src,0);
rotate(src,1);
}
}
else {
if (y->ch[1] == src) {
rotate(y,0);
rotate(src,0);
}else {
rotate(src,1);
rotate(src,0);
}
}
if (z == dst) break;
}
pushup(src);
}
pushup(src);
}
void select(int k, node &f) {
int tmp;
node t = root;
while (true) {
push_down(t);
tmp = getsize(t->ch[0]);
if (k == tmp + 1) break;
if (k <= tmp) t = t->ch[0];
else {
k -= tmp + 1;
t = t->ch[1];
}
}
push_down(t);
splay(t, f);
}
inline void SelectSegment(int l, int r) {
select(l,root);
select(r + 2,root->ch[1]);
}
node Newnode(int value){
node t;
if (top){
t = S[top--];
}
else t = &tr[idx++];
t->init(value);
return t;
}
node build(int l,int r,node fa,int *a){
int mid = l + r >> 1;
node t = Newnode(a[mid]);
t->pre = fa;
if (l < mid) t->ch[0] = build(l,mid - 1,t,a);
if (r > mid) t->ch[1] = build(mid + 1,r,t,a);
pushup(t);
return t;
}
void insert(int pos, int value) { //在pos位置后面插入一个新值value
SelectSegment(pos + 1, pos);
node t;
node x = root->ch[1];
push_down(root);
push_down(x);
t = Newnode(value);
t->ch[1] = x;
x->pre = t;
root->ch[1] = t;
t->pre = root;
splay(x, root);
}
void insert(int pos, int* a,int len) { //在pos位置后面插入长度为len的数组
SelectSegment(pos + 1, pos);
node x = root->ch[1];
push_down(root);
push_down(x);
root->ch[1]->ch[0] = build(1,len,root->ch[1],a);
splay(x, root);
}
void add(int a,int b, int value) { //区间[a,b]中的数都加上value
SelectSegment(a, b);
node x = root->ch[1]->ch[0];
push_down(x);
pushup(x);
x->max += value;
x->lazy += value;
splay(x, root);
}
void reverse(int a, int b) { //区间[a,b]中的数翻转
SelectSegment(a, b);
root->ch[1]->ch[0]->rev ^= 1;
node x = root->ch[1]->ch[0];
splay(x, root);
}
void revolve(int a, int b, int t) { //区间[a,b]中的数向后循环移t位
node p1, p2;
SelectSegment(a, b);
select(b + 1 - t, root->ch[1]->ch[0]);
p1 = root->ch[1]->ch[0];
push_down(p1);
p2 = p1->ch[1];
p1->ch[1] = NULL;
select(a + 1, root->ch[1]->ch[0]);
p1 = root->ch[1]->ch[0];
push_down(p1);
p1->ch[0] = p2;
p2->pre = p1;
splay(p2, root);
}
ll getmax(int a, int b) { //取[a,b]中最大的值
SelectSegment(a, b);
node x = root->ch[1];
push_down(x);
x = x->ch[0];
push_down(x);
pushup(x);
return x->max;
}
ll getsum(int a, int b) {
SelectSegment(a, b);
node x = root->ch[1];
push_down(x);
x = x->ch[0];
push_down(x);
pushup(x);
return x->sum;
}
void CutandMove(int a, int b, int c)//移动区间[l,r]到位置c后
{
SelectSegment(a,b);
node CutRoot = root->ch[1]->ch[0];
CutRoot->pre = NULL;
root->ch[1]->size -= CutRoot->size;
root->ch[1]->ch[0] = NULL;
SelectSegment(c + 1, c);
CutRoot->pre = root->ch[1];
root->ch[1]->ch[0] = CutRoot;
root->ch[1]->size += CutRoot->size;
//切树操作的话,就先选择要切的区间,然后断开根的右子结
//点和其左子结点的联系,把要接上的节点旋转到根的右子结点出并清空其左子
//结点,再把切下来的子树接上去即可。
}
void recycle(node x){
S[++top] = x;
if (x->ch[0]) recycle(x->ch[0]);
if (x->ch[1]) recycle(x->ch[1]);
}
void cut(int a,int b)//删除区间[l.r]
{
SelectSegment(a, b);
node CutRoot = root->ch[1]->ch[0];
CutRoot->pre = NULL;
root->size -= CutRoot->size;
root->ch[1]->size -= CutRoot->size;
recycle(CutRoot);
CutRoot = NULL;
}
vector<int> ans;
void get_ans(node x)
{
if (!x) return;
push_down(x);
get_ans(x->ch[0]);
if (x->value != -inf) ans.push_back(x->value);
get_ans(x->ch[1]);
}
void InitSplay(int *a, int n) {
idx = top = 0;
root = Newnode(-inf);
root->ch[1] = Newnode(-inf);
root->ch[1]->pre = root;
root->ch[1]->ch[0] = build(1,n,root->ch[1],a);
pushup(root->ch[1]);
pushup(root);
}
/*----------Splay Template Over----------*/
int a[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
// cin >> a[i];
a[i] = i;
}
InitSplay(a, n);
while (m--) {
int x,y;
cin >> x >> y;
reverse(x,y);
}
get_ans(root);
for(auto k : ans) cout << k << ' ';
return 0;
}
更多推荐
Splay维护序列个人模板
发布评论