很好的一道题，用了三天多的时间，终于知道了我为什么T的原因，也知道了在Splay的同时该怎样子的节约时间，因为Splay本身就是大常数的O（N*logN），我们如果不在各种细节上节约时间，很容易就会造成T的是因为我们制造了一个同样的大常数。
先讲解一下题意：有两种操作，一个是一段区间内的值翻转，另一个是讲[a, b]裁剪下来，然后将这段区间贴到剩下的元素的第c位后面。
然后讲一下Splay翻转的几个要点，还有就是可能的T的点，我们要做到的翻转的操作自然不是太过于难想，很多人都能想到的就是lazy标记的下推，然后改变相对应的值即可。同样的，区间的裁剪再贴到最后也不是那么的难想到，就是裁剪[l, r]这样的区间，我们只需要找到Kth(l-1)和Kth(r+1)，然后裁剪下来他们的中间区域，（这里记得要先pushup(r+1)，然后pushup(l-1)也就是根节点）然后再去寻找到第c大的，还有c+1大的，我们将值放在（c+1）大的左子树那块即可。思路就是这样子的，但是代码总是T，我一开始还写了快速读入，还以为能卡时间，但是很显然，时间不在于输入处，而是Splay的时候，翻转过于浪费时间，那么具体是哪里浪费时间了呢，我们慢慢看。
现在开始讲解Splay会T的一些原因，Splay的操作主要就是在Splay()这个函数，所以当T的时候，我们应该先考虑一下是不是在翻转Splay()的时候有一些可以去掉的大常数，譬如说，我将pushup()还有pushdown()这两个函数写在了Rotate()函数里面，那么我们就不必要再在Splay()函数里面写pushup()和pushdown()了，这里就是可以优化掉一个大常数（这是我到最后发现的TLE的最最最关键的原因）。
当然，我们裁剪掉一部分pushup()以及pushdown()的同时，还需要保证留下足够的对应的返回更新和下放懒标记的函数才行，这里给出哪里必需要放置这两个函数：
inline void pushup(int x) { t[x].siz = t[t[x].ch[]].siz + t[t[x].ch[]].siz + ; }pushup
inline void pushdown(int x)
{
if(t[x].lazy)
{
t[t[x].ch[]].lazy ^= ;
t[t[x].ch[]].lazy ^= ;
swap(t[x].ch[], t[x].ch[]);
t[x].lazy = ;
}
}
pushdown
然后接下去说说看哪几处地方一定是要放这两个函数的：
void Rotate(int x)
{
int y = t[x].ff, z = t[y].ff;
pushdown(y); pushdown(x);
int k = t[y].ch[] == x;
t[z].ch[t[z].ch[] == y] = x;
t[x].ff = z;
t[y].ch[k] = t[x].ch[k^];
t[t[x].ch[k^]].ff = y;
t[x].ch[k^] = y;
t[y].ff = x;
pushup(y); pushup(x);
}
Rotate
在Rotate的时候是一定要加上这两个函数的，因为我们在旋转的同时我们会改变节点，所以首先就需要pushdown()，然后，最后需要pushup()。
inline void build_Splay_tree(int &rt, int l, int r, int fa)
{
if(l > r) return;
int mid = HalF;
new_node(rt, fa, mid);
build_Splay_tree(t[rt].ch[], l, mid-, rt);
build_Splay_tree(t[rt].ch[], mid + , r, rt);
pushup(rt);
}
build_Splay_tree
在建Splay树的时候，我们就需要pushup()来得到size的传递。
int Kth(int k)
{
int u = root;
if(t[u].siz < k) return ;
while(true)
{
pushdown(u);
int y = t[u].ch[];
if(k > t[y].siz + )
{
k -= t[y].siz + ;
u = t[u].ch[];
}
else
{
if(t[y].siz >= k) u = y;
else return u; //找到对应的节点编号了
}
}
}
Kth
我们要找第K个数的时候，也需要pushdown()，因为我们的左右子树的size是不一定相同的，我们要改变翻转的懒标记，然后同时改变左右的子树的位置。
inline void Cut(int l, int r, int pos)
{
int las = Kth(l), nex = Kth(r + );
Splay(las, ); Splay(nex, las);
int del = t[nex].ch[];
t[nex].ch[] = ;
pushup(nex);
pushup(root);
int u = Kth(pos + ), v = Kth(pos + );
Splay(u, ); Splay(v, u);
t[t[root].ch[]].ch[] = del;
t[del].ff = v;
pushup(v);
pushup(u);
}
Cut
我们cut下来的时候，就需要一次的pushup()，因为此时的两个节点的size都改变了，然后在接下去，我们接上去的时候也需要pushup()，这时候这两个节点就有更多的size了，也是需要更新了。
inline void _OUT(int u)
{
pushdown(u);
if(t[u].ch[]) _OUT(t[u].ch[]);
if(t[u].val >= && t[u].val <= N) { cnt++; printf("%d%c", t[u].val, cnt == N ? '\n' : ' '); }
if(t[u].ch[]) _OUT(t[u].ch[]);
}
OUT
输出的操作当然是要pushdown()的呀，毕竟要对应的找左右嘛，所谓的中序遍历。
好了，上面的所有的情况都考虑到了，基本就能A了吧，也祝愿大家都能过美美哒过这题，不像我……卡了好几天…… (*≧ω≦)
FLIP
CUT
FLIP
CUT
ans:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 3e5 + ;
int N, M, root, tot;
struct node
{
int ff, val, siz, ch[], lazy;
node() { ff = val = siz = ch[] = ch[] = lazy = ; }
}t[maxN];
inline void new_node(int &x, int fa, int val)
{
x = ++tot;
t[x].ff = fa;
t[x].val = val;
t[x].siz = ;
t[x].ch[] = t[x].ch[] = t[x].lazy = ;
}
inline void pushdown(int x)
{
if(t[x].lazy)
{
t[t[x].ch[]].lazy ^= ;
t[t[x].ch[]].lazy ^= ;
swap(t[x].ch[], t[x].ch[]);
t[x].lazy = ;
}
}
inline void pushup(int x) { t[x].siz = t[t[x].ch[]].siz + t[t[x].ch[]].siz + ; }
void Rotate(int x)
{
int y = t[x].ff, z = t[y].ff;
pushdown(y); pushdown(x);
int k = t[y].ch[] == x;
t[z].ch[t[z].ch[] == y] = x;
t[x].ff = z;
t[y].ch[k] = t[x].ch[k^];
t[t[x].ch[k^]].ff = y;
t[x].ch[k^] = y;
t[y].ff = x;
pushup(y); pushup(x);
}
void Splay(int x, int goal)
{
while(t[x].ff != goal)
{
int y = t[x].ff, z = t[y].ff;
if(z != goal) (t[z].ch[] == y) ^ (t[y].ch[] == x) ? Rotate(x) : Rotate(y);
Rotate(x);
}
if(!goal) root = x;
}
inline void insert(int x)
{
int u = root, ff = ;
while(u && t[u].val != x)
{
ff = u;
u = t[u].ch[x > t[u].val];
}
new_node(u, ff, x);
if(ff) t[ff].ch[x > t[ff].val] = u;
Splay(u, );
}
inline void build_Splay_tree(int &rt, int l, int r, int fa)
{
if(l > r) return;
int mid = HalF;
new_node(rt, fa, mid);
build_Splay_tree(t[rt].ch[], l, mid-, rt);
build_Splay_tree(t[rt].ch[], mid + , r, rt);
pushup(rt);
}
int Kth(int k)
{
int u = root;
if(t[u].siz < k) return ;
while(true)
{
pushdown(u);
int y = t[u].ch[];
if(k > t[y].siz + )
{
k -= t[y].siz + ;
u = t[u].ch[];
}
else
{
if(t[y].siz >= k) u = y;
else return u; //找到对应的节点编号了
}
}
}
inline void Ex_change(int l, int r)
{
int las = Kth(l), nex = Kth(r + );
Splay(las, ); Splay(nex, las);
t[t[nex].ch[]].lazy ^= ;
}
inline void Cut(int l, int r, int pos)
{
int las = Kth(l), nex = Kth(r + );
Splay(las, ); Splay(nex, las);
int del = t[nex].ch[];
t[nex].ch[] = ;
pushup(nex);
pushup(root);
int u = Kth(pos + ), v = Kth(pos + );
Splay(u, ); Splay(v, u);
t[t[root].ch[]].ch[] = del;
t[del].ff = v;
pushup(v);
pushup(u);
}
int cnt;
inline void _OUT(int u)
{
pushdown(u);
if(t[u].ch[]) _OUT(t[u].ch[]);
if(t[u].val >= && t[u].val <= N) { cnt++; printf("%d%c", t[u].val, cnt == N ? '\n' : ' '); }
if(t[u].ch[]) _OUT(t[u].ch[]);
}
inline void init()
{
tot = root = cnt = ;
t[].siz = t[].ch[] = t[].ch[] = ;
build_Splay_tree(root, , N + , );
}
char op[];
int main()
{
while(scanf("%d%d", &N, &M) != EOF)
{
if(N < || M < ) break;
init();
int a, b, c;
while(M--)
{
scanf("%s", op);
if(op[] == 'C')
{
scanf("%d%d%d", &a, &b, &c);
Cut(a, b, c);
}
else
{
scanf("%d%d", &a, &b);
Ex_change(a, b);
}
//cnt = 0;
//_OUT(root);
}
_OUT(root);
}
return ;
}
/*
5 4
FLIP 2 4
CUT 2 3 3
FLIP 2 5
CUT 1 3 1
ans:5 1 3 4 2
*/
完整代码