http://www.lydsy.com/JudgeOnline/problem.php?id=3282
复习了下lct，发现两个问题。。
1：一开始我以为splay那里直接全部rot(x)就好了，然后改了好几题lct的题，都过了且速度和原版一样。。然后怀疑了下。。。。。。后来请教神犇，他说这样不行。。（这是单旋了？时间复杂度不保证，，但是我还不知道反例）
2：findroot操作里不要使用makeroot后再找root。。。。。。。。。。。。。。。。。。。。。。多么的sb啊。。。。。。。。
然后就是裸的lct。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=300005;
struct node *null;
struct node {
int v, rev, w;
node *ch[2], *fa;
node(const int _v=0) : v(_v), rev(0), w(0) { ch[0]=ch[1]=fa=null; }
bool d() { return fa->ch[1]==this; }
bool check() { return fa->ch[0]!=this && fa->ch[1]!=this; }
void setc(node* c, int d) { ch[d]=c; c->fa=this; }
void pushup() { w=ch[0]->w^ch[1]->w^v; }
void pushdown() {
if(rev) {
ch[0]->rev^=1;
ch[1]->rev^=1;
swap(ch[0], ch[1]);
rev=0;
}
}
}*t[N];
void rot(node* x) {
node* fa=x->fa; bool d=x->d();
fa->pushdown(); x->pushdown();
if(!fa->check()) fa->fa->setc(x, fa->d());
else x->fa=fa->fa;
fa->setc(x->ch[!d], d);
x->setc(fa, !d);
fa->pushup();
}
void fix(node* x) {
if(!x->check()) fix(x->fa);
x->pushdown();
}
void splay(node* x) {
fix(x);
while(!x->check())
if(x->fa->check()) rot(x);
else x->d()==x->fa->d()?(rot(x->fa), rot(x)):(rot(x), rot(x));
x->pushup();
}
node* access(node* x) {
node* y=null;
for(; x!=null; y=x, x=x->fa) {
splay(x);
x->ch[1]=y;
}
return y;
}
void mkroot(node* x) { access(x)->rev^=1; splay(x); }
void link(node* x, node* y) { mkroot(x); x->fa=y; }
void cut(node* x, node* y) {
mkroot(x); access(y); splay(y);
y->ch[0]->fa=null; y->ch[0]=null;
}
node* findrt(node* x) {
access(x); splay(x);
while(x->ch[0]!=null) x=x->ch[0];
return x;
}
void init() { null=new node; null->ch[0]=null->ch[1]=null->fa=null; }
int n, m; int main() {
init();
read(n); read(m);
for1(i, 1, n) t[i]=new node(getint());
rep(i, m) {
int c=getint(), x=getint(), y=getint();
if(c==0) { mkroot(t[x]); access(t[y]); splay(t[y]); printf("%d\n", t[y]->w); }
else if(c==1) { if(findrt(t[x])!=findrt(t[y])) link(t[x], t[y]); }
else if(c==2) { if(findrt(t[x])==findrt(t[y])) cut(t[x], t[y]); }
else if(c==3) { mkroot(t[x]); t[x]->v=y; t[x]->pushup(); }
}
return 0;
}
Description
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
Input
第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。
第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。
Output
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
Sample Input
3 3
1
2
3
1 1 2
0 1 2
0 1 1
1
2
3
1 1 2
0 1 2
0 1 1
Sample Output
3
1
1
HINT
１＜＝Ｎ，Ｍ＜＝３０００００