[bzoj] 1588 营业额统计 || Splay板子题

http://www.cnblogs.com/mrsheep/p/8110483.html
//太懒了……

#include
#include
#include
#define which(x) (ls[f[(x)]]==(x))
#define N 33000
using namespace std;
int n,v,root,ls[N],rs[N],val[N],f[N],idx,ans;
 
void Rotate(int u)
{
    int v=f[u],w=f[v],b=which(u)?rs[u]:ls[u],dir=which(v);
    which(u)?(rs[u]=v,ls[v]=b):(ls[u]=v,rs[v]=b);
    f[v]=u;f[b]=v;f[u]=w;
    if (w) dir?ls[w]=u:rs[w]=u;
}
 
int read()
{
    int ans=0,fu=1;
    char j=getchar();
    for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;
    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';
    return ans*fu;
}
 
void splay(int x,int y)
{
    while (f[x]!=y)
    {
    if (f[f[x]]!=y)
    {
        if (which(x)==which(f[x])) Rotate(f[x]);
        else Rotate(x);
    }
    Rotate(x);
    }
    if (!y) root=x;
}
 
void insert(int x)
{
    int u=root,v=0;
    while (u)
    {
    v=u;
    if (x