#include <cstdio>
const int Maxn=;
inline void Get_Int(int & x)
{
char ch=getchar(); x=;
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
}
//========================================
char str[];
int n,m,u,v;
struct Node;
inline void Swap(Node *&x,Node *&y);
struct Node
{
Node * pre,* ch[];
int rev;
inline int d() {return pre->ch[]==this;}
inline void Rev() {Swap(ch[],ch[]),rev^=;}
inline void setc(Node * r,int d) {ch[d]=r; r->pre=this;}
};
Node Memory[Maxn],* Port=Memory,* null,* S[Maxn],* t[Maxn];
inline void Swap(Node *&x,Node *&y) {Node * t=x;x=y;y=t;}
inline void Init() {null=Port++; null->rev=; null->pre=null->ch[]=null->ch[]=null;}
inline Node * NewNode(){Node * Ret=Port++; Ret->rev=; Ret->pre=Ret->ch[]=Ret->ch[]=null; return Ret;}
inline bool IsRoot(Node * x) {return x->pre==null || (x->pre->ch[]!=x && x->pre->ch[]!=x);}
inline bool Push_Down(Node * x)
{
if (x->rev)
{
x->rev=;
x->ch[]->Rev();
x->ch[]->Rev();
}
}
inline void Rotate(Node * x)
{
Node * y=x->pre; int d=x->d();
Push_Down(y); Push_Down(x);
if (IsRoot(y)) x->pre=y->pre; else y->pre->setc(x,y->d());
y->setc(x->ch[!d],d);
x->setc(y,!d);
}
inline void Splay(Node * x)
{
Push_Down(x);
while (!IsRoot(x))
if (IsRoot(x->pre)) Rotate(x); else
(x->pre->d()==x->d()) ? (Rotate(x->pre),Rotate(x)) : (Rotate(x),Rotate(x));
}
inline void Access(Node * f)
{
Node * c=null;
while (f!=null)
{
Splay(f);
f->ch[]=c;
c=f;
f=f->pre;
}
}
inline void Make_Root(Node * x)
{
Access(x),Splay(x),x->Rev();
}
inline void Link(Node * x,Node * y)
{
Make_Root(x),x->pre=y;
}
inline void Cut(Node * x,Node * y)
{
Access(x),Splay(x),Splay(y);
if (y->pre!=x) Swap(x,y);
Access(x),Splay(x),Splay(y);
y->pre=null;
}
inline Node * Find(Node * x)
{
while (x->pre!=null) x=x->pre; return x;
}
inline bool Check(Node * x,Node * y)
{
if (Find(x)==Find(y)) return true; else return false;
}
int main()
{
Init();
Get_Int(n),Get_Int(m);
for (int i=;i<=n;i++) t[i]=NewNode();
for (int i=;i<=m;i++)
{
scanf("%s",str); Get_Int(u),Get_Int(v);
if (str[]=='C') Link(t[u],t[v]);
if (str[]=='D') Cut(t[u],t[v]);
if (str[]=='Q') puts(Check(t[u],t[v])?"Yes":"No");
}
return ;
}
BZOJ 2409
#include <cstdio>
inline void Get_Int(int &x)
{
x=; register char ch=getchar(); int f=;
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;
}
inline void Put_Int(int x)
{
char ch[]; register int top=;
if (x<) putchar('-'),x=-x;
if (x==) ch[++top]='';
while (x) ch[++top]=x%+'',x/=;
while (top) putchar(ch[top--]); putchar('\n');
}
inline int Min(int x,int y) {return x>y?y:x;}
//===============================================
const int Maxn=;
int n,m,k[Maxn],x,y,Type;
struct Node
{
Node * pre,* ch[];
int size,rev;
inline int d() {return pre->ch[]==this;}
inline void setc(Node * r,int d) {ch[d]=r; r->pre=this;}
};
Node Memory[Maxn],* port=Memory,* t[Maxn],* null,* S[Maxn];
inline void Swap(Node *&x,Node *&y) {Node * t=x;x=y;y=t;}
inline void Init() {null=port++; null->rev=; null->size=;null->pre=null->ch[]=null->ch[]=null;}
inline Node * NewNode(){Node * Ret=port++; Ret->ch[]=Ret->ch[]=Ret->pre=null;Ret->size=;Ret->rev=; return Ret;}
inline void Push_Up(Node * x) {x->size=x->ch[]->size+x->ch[]->size+;}
inline void Push_Down(Node * x)
{
if (x->rev)
{
x->ch[]->rev^=;
x->ch[]->rev^=;
x->rev=;
Swap(x->ch[],x->ch[]);
}
}
inline bool IsRoot(Node * x) {return x->pre==null || (x->pre->ch[]!=x && x->pre->ch[]!=x);} inline void Rotate(Node * x)
{
Node * y=x->pre; int d=x->d();
if (IsRoot(y)) x->pre=y->pre; else y->pre->setc(x,y->d());
y->setc(x->ch[!d],d);
x->setc(y,!d);
Push_Up(y),Push_Up(x);
}
inline void Splay(Node * x)
{
int s=; S[]=x; Node * r=x;
while (!IsRoot(r->pre)) S[++s]=r=r->pre;
while (s) Push_Down(S[s--]); while (!IsRoot(x))
if (IsRoot(x->pre)) Rotate(x); else
(x->pre->d()==x->d()) ? (Rotate(x->pre),Rotate(x)) : (Rotate(x),Rotate(x));
Push_Up(x);
} inline void Access(Node * f)
{
Node * c=null;
while (f!=null)
{
Splay(f);
f->ch[]=c;
c=f;
f=f->pre;
}
}
inline void Make_Root(Node * r)
{
Access(r),Splay(r),r->rev^=;
}
inline void Link(Node * x,Node * y)
{
Make_Root(x);x->pre=y;
}
inline void Cut(Node * x,Node * y)
{
Access(x),Splay(y);
if (y->pre!=x) Swap(x,y);
Access(x),Splay(y);
y->pre=null;
}
int main()
{
// freopen("c.in","r",stdin);
Init();
Get_Int(n);
for (int i=;i<=n+;i++) t[i]=NewNode();
for (int i=;i<=n;i++)
Get_Int(x),k[i]=Min(i+x,n+),Link(t[i],t[k[i]]);
Get_Int(m); Make_Root(t[n+]);
for (int i=;i<=m;i++)
{
Get_Int(Type);
if (Type==)
{
Get_Int(x); x++;
Make_Root(t[n+]);
Access(t[x]),Splay(t[x]);
Put_Int(t[x]->size-);
}
if (Type==)
{
Get_Int(x),Get_Int(y); x++;
Cut(t[x],t[k[x]]);
k[x]=Min(n+,x+y);
Link(t[x],t[k[x]]);
}
}
return ;
}
BZOJ 2002
调了好久，明天在做几题。
8.17
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
inline void Get_Int(int &x)
{
x=; char ch=getchar();
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
}
inline int Max(int x,int y) {return x>y?x:y;}
inline int Min(int x,int y) {return x>y?y:x;}
//===========================================
const int Maxn=;
struct Node
{
Node * pre,* ch[]; int Rev,Key,v;
inline int d() {return pre->ch[]==this;}
inline void setc(Node * x,int d) {ch[d]=x; x->pre=this;}
};
Node Memory[Maxn<<],* port=Memory,* null,* Nd[Maxn];
int u,v,n,m,x,Type;
inline bool IsRoot(Node * x) {return x->pre==null || (x->pre->ch[]!=x && x->pre->ch[]!=x);}
inline void Swap(Node *&x,Node *&y) {Node * T=x;x=y;y=T;}
inline Node * NewNode(int v) {Node * Ret=port++; Ret->v=Ret->Key=v; Ret->Rev=; Ret->pre=Ret->ch[]=Ret->ch[]=null; return Ret;}
inline void Init() {null=port++; null->pre=null->ch[]=null->ch[]=null; null->Rev=null->Key=null->v=;}
inline void Get_Rev(Node * x)
{
if (x==null) return;
x->Rev^=; Swap(x->ch[],x->ch[]);
}
inline void Push_Down(Node * x)
{
if (x->Rev)
{
x->Rev=;
Get_Rev(x->ch[]);
Get_Rev(x->ch[]);
}
}
inline void Push_Up(Node * x)
{
x->v=x->ch[]->v^x->ch[]->v^x->Key;
}
inline void Rotate(Node * x)
{
Node * y=x->pre; int d=x->d();
Push_Down(y),Push_Down(x);
if (IsRoot(y)) x->pre=y->pre; else y->pre->setc(x,y->d());
y->setc(x->ch[!d],d);
x->setc(y,!d);
Push_Up(y),Push_Up(x);
}
inline void Splay(Node * x)
{
Push_Down(x);
while (!IsRoot(x))
if (IsRoot(x->pre)) Rotate(x); else
(x->d()==x->pre->d())?(Rotate(x->pre),Rotate(x)):(Rotate(x),Rotate(x));
Push_Up(x);
}
inline void Access(Node * f)
{
Node * x=null;
while (f!=null)
{
Splay(f);
f->ch[]=x;
x=f;
f=f->pre;
}
}
inline void Make_Root(Node * x)
{
Access(x); Splay(x); Get_Rev(x);
}
inline void Link(Node * x,Node * y)
{
Make_Root(x),x->pre=y;
}
inline void Cut(Node * x,Node * y)
{
Access(x),Splay(x),Splay(y);
if (y->pre!=x) Swap(x,y);
Access(x),Splay(x),Splay(y);
y->pre=null;
}
inline Node * Find(Node * x)
{
while (x->pre!=null) x=x->pre; return x;
}
inline bool Check(int p,int q)
{
if (Find(Nd[p])==Find(Nd[q])) return true; return false;
}
//==================================
inline void Query()
{
Get_Int(u),Get_Int(v);
Make_Root(Nd[u]),Access(Nd[v]),Splay(Nd[v]);
printf("%d\n",Nd[v]->v);
}
inline void Connect()
{
Get_Int(u),Get_Int(v);
if (Check(u,v)) return;
Link(Nd[u],Nd[v]);
}
inline void Delete()
{
Get_Int(u),Get_Int(v);
if (!Check(u,v)) return;
Cut(Nd[u],Nd[v]);
}
inline void Modify()
{
Get_Int(u),Get_Int(v);
Make_Root(Nd[u]); Nd[u]->Key=v; Push_Up(Nd[u]);
}
int main()
{
Get_Int(n),Get_Int(m); Init();
for (int i=;i<=n;i++) Get_Int(x),Nd[i]=NewNode(x);
for (int i=;i<=m;i++)
{
Get_Int(Type);
if (Type==) Query();
if (Type==) Connect();
if (Type==) Delete();
if (Type==) Modify();
}
return ;
}
BZOJ 3282