第一次写splay，还是写复杂一点吧，左旋右旋都写，不然过几天自己都看不懂了。。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
typedef long long ll;
using namespace std;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
const int N=500005;
int fa[N],c[N],ch[N][2],x,n,i,idn,ans,root;
void look(int i)
{
    if (i==0) return;
    look(ch[i][0]);
    printf("%d ",c[i]);
    look(ch[i][1]);
}
void zag(int x)
{
    int y=fa[x],z=fa[y];
    ch[y][1]=ch[x][0]; fa[ch[y][1]]=y;
    ch[x][0]=y; fa[y]=x;
    fa[x]=z;
    if (z)
        if (ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x;
}
void zig(int x)
{
    int y=fa[x],z=fa[y];
    ch[y][0]=ch[x][1]; fa[ch[y][0]]=y;
    ch[x][1]=y; fa[y]=x;
    fa[x]=z;
    if (z)
        if (ch[z][0]==y) ch[z][0]=x;else ch[z][1]=x;
}
void splay(int x)
{
    while(fa[x])
    {
        int y=fa[x],z=fa[y];
        if (!z)
            if (ch[y][0]==x) zig(x);else zag(x);
        else
        {
            if (ch[z][0]==y)
                if (ch[y][0]==x) zig(y),zig(x);
                else zag(x),zig(x);
            else
                if (ch[y][0]==x) zig(x),zag(x);
                else zag(y),zag(x);
        }
    }
    root=x;
}
void ins(int x,int v)
{
    int nxt;
    if (v<c[x]) nxt=0;else nxt=1;
    while(ch[x][nxt])
    {
        x=ch[x][nxt];
        if (v<c[x]) nxt=0;else nxt=1;
    }
    idn++; ch[x][nxt]=idn; fa[idn]=x; c[idn]=v;
    //look(1);
    splay(idn);
    //look(1);
}
int pre(int x)
{
    int tmp=ch[x][0];
    while(ch[tmp][1]) tmp=ch[tmp][1];
    return c[tmp];
}
int suc(int x)
{
    int tmp=ch[x][1];
    while(ch[tmp][0]) tmp=ch[tmp][0];
    return c[tmp];
}
int main()
{
    scanf("%d",&n);
    idn=1,c[1]=-2000000000; root=1;
    ins(root,2000000000);
    for (i=1;i<=n;i++)
    {
        if (scanf("%d",&x)==-1) x=0;
        if (i==1) ans+=x,ins(root,x);
        else ins(root,x),ans+=min(x-pre(root),suc(root)-x);
        //look(root);printf("\n");
    }
    printf("%d",ans);
}

终于学会了树链剖分，以前以为它很难，现在看来其实也挺简单的，就两个dfs+线段树维护一下嘛。第一次交忘记修改的是x对应的编号，WA了一次，修改后AC。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
const int N=30005;
int size[N],top[N],son[N],f[N],id[N],c[N],w[N],deep[N],n,i,q,tot,idn,x,y;
int base[N],vec[2*N],pre[2*N];
struct node{
    int sum,mx,l,r,mid;
}tr[4*N];
char chr[10];
bool vis[N];
void add(int x,int y)
{
    tot++;
    vec[tot]=y;  pre[tot]=base[x];  base[x]=tot;
}
void dfs1(int u)
{
    vis[u]=true;
    int now=base[u];
    size[u]=1;
    while(now)
    {
        int v=vec[now];
        if (!vis[v])
        {
            f[v]=u;
            deep[v]=deep[u]+1;
            dfs1(v);
            size[u]+=size[v];
            if (size[v]>size[son[u]]) son[u]=v;
        }
        now=pre[now];
    }
}
void dfs2(int u)
{
    idn++; id[u]=idn;
    vis[u]=true;
    int now=base[u];
    if (son[u]) top[son[u]]=top[u],dfs2(son[u]);
    while(now)
    {
        int v=vec[now];
        if (!vis[v]) top[v]=v,dfs2(v);
        now=pre[now];
    }
}
void build(int i,int l,int r)
{
    tr[i].l=l; tr[i].r=r; tr[i].mid=(l+r)/2;
    if (l==r){tr[i].sum=tr[i].mx=c[l];return;}
    build(i*2,l,tr[i].mid);
    build(i*2+1,tr[i].mid+1,r);
    tr[i].sum=tr[i*2].sum+tr[i*2+1].sum;
    tr[i].mx=max(tr[i*2].mx,tr[i*2+1].mx);
}
int querymax(int i)
{
    if (x<=tr[i].l&&tr[i].r<=y) return tr[i].mx;
    if (y<=tr[i].mid) return querymax(i*2);
    if (x>tr[i].mid) return querymax(i*2+1);
    return max(querymax(i*2),querymax(i*2+1));
}
int querysum(int i)
{
    if (x<=tr[i].l&&tr[i].r<=y) return tr[i].sum;
    if (y<=tr[i].mid) return querysum(i*2);
    if (x>tr[i].mid) return querysum(i*2+1);
    return querysum(i*2)+querysum(i*2+1);
}
void change(int i)
{
    if (tr[i].l==tr[i].r) {tr[i].sum=y;tr[i].mx=y;return;}
    if (x<=tr[i].mid) change(i*2);else change(i*2+1);
    tr[i].sum=tr[i*2].sum+tr[i*2+1].sum;
    tr[i].mx=max(tr[i*2].mx,tr[i*2+1].mx);
}
void slovemax(int a,int b)
{
    int f1=top[a]; int f2=top[b];int tmp=-50000;
    while(f1!=f2)
    {
        if (deep[f1]<deep[f2]) swap(f1,f2),swap(a,b);
        x=id[f1];y=id[a];
        tmp=max(tmp,querymax(1));
        a=f[f1]; f1=top[a];
    }
    if (deep[a]>deep[b]) swap(a,b);
    x=id[a]; y=id[b];
    tmp=max(tmp,querymax(1));
    printf("%d\n",tmp);
}
void slovesum(int a,int b)
{
    int f1=top[a]; int f2=top[b];int tmp=0;
    while(f1!=f2)
    {
        if (deep[f1]<deep[f2]) swap(f1,f2),swap(a,b);
        x=id[f1];y=id[a];
        tmp+=querysum(1);
        a=f[f1]; f1=top[a];
    }
    if (deep[a]>deep[b]) swap(a,b);
    x=id[a]; y=id[b];
    tmp+=querysum(1);
    printf("%d\n",tmp);
}
int main()
{
    scanf("%d",&n);
    for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for (i=1;i<=n;i++) scanf("%d",&w[i]);
    deep[1]=1; dfs1(1);
    memset(vis,0,sizeof(vis));
    top[1]=1; dfs2(1);
    for (i=1;i<=n;i++) c[id[i]]=w[i];
    build(1,1,n);
    scanf("%d",&q);
    for (i=1;i<=q;i++)
    {
        scanf("%s%d%d",chr,&x,&y);
        if (chr[1]=='M') slovemax(x,y);
        if (chr[1]=='H') x=id[x],change(1);
        if (chr[1]=='S') slovesum(x,y);
    }
}

第一次打BST，不会打便去网上搜模板，可是都写得好复杂，让刚入门C++的我很多看不懂。百度百科了一下，了解了思路，自己yy出了代码，原来很短啊。

#include<cstdio>
#include<cstring>
using namespace std;
int n,i,tot,x;
struct node{
    int l,r,v;
}a[100005];
bool first;
void ins(int t)
{
    if (a[t].v==0) {a[t].v=x;return;}
    if (x<=a[t].v)
    {
        if (a[t].l==0) {tot++; a[t].l=tot;}
        ins(a[t].l);
    }
    else
    {
        if (a[t].r==0) {tot++; a[t].r=tot;}
        ins(a[t].r);
    }
}
void print(int t)
{
    if (first) first=0,printf("%d",a[t].v);else printf(" %d",a[t].v);
    if (a[t].l) print(a[t].l);
    if (a[t].r) print(a[t].r);
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        tot=1;
        for (i=1;i<=n;i++)
        {
            scanf("%d",&x);
            ins(1);
        }
        first=1;
        print(1);
        printf("\n");
    }
}

htw学长用线段树做这道，一直RE，后来发现是没有考虑子节点越界。我看这道题很像扫描线，离散化后用堆维护当前最靠前的海报，1A.

代码可比线段树短多了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
struct line{
    bool operator< (const line &a)const
    {
        return no<a.no;
    }
    int x,y;
    int no;
}a[10005];
bool cmpq(line a,line b){return a.no<b.no;}
bool cmp(int i,int j){return a[i].x<a[j].x;}
int n,i,j,t,ans,tot;
int c[50005],node[10005];
bool b[10005];
void lisan()
{
    sort(c+1,c+tot+1);
    int now=1;
    for (i=2;i<=tot;i++)
      if (c[i]>c[now]) c[++now]=c[i];
    tot=now;
}
void init()
{
    ans=0; tot=0;
    memset(b,0,sizeof(b));
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y),a[i].no=i,node[i]=i;
            c[++tot]=a[i].x; c[++tot]=a[i].x+1;
            c[++tot]=a[i].y; c[++tot]=a[i].y+1;
        }
        sort(node+1,node+n+1,cmp);
        lisan();
        j=1;
        priority_queue<line>q;
        for (i=1;i<=tot;i++)
        {
            while(!q.empty()&&q.top().y<c[i]) q.pop();
            while(j<=n&&a[node[j]].x<=c[i]) q.push(a[node[j]]),j++;
            if (!q.empty()) b[q.top().no]=1;
        }
        for (i=1;i<=n;i++) if (b[i]) ans++;
        printf("%d\n",ans);
    }
}

这题先把边按起点排序，再把询问排序，从大到小处理询问，并且不断加入需要的边，保存终点的最大值和次大值，询问点-次大值就是该询问的答案。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
#include<vector>
using namespace std;
int team[5],tail,i,j,n,q,m,node[50005],a[50005],ans[50005];
struct rec
{
    int x,y;
}edg[50005];
bool cmp1(int i,int j){return a[i]<a[j];}
bool cmp2(rec a,rec b){return a.x<b.x;}
void add(int i)
{
    if (tail==0){team[++tail]=edg[i].y;return;}
    if (tail==1)
    {
        team[++tail]=edg[i].y;
        if (team[2]<team[1]){int t=team[1]; team[1]=team[2];team[2]=t;}
        return;
    }
    if (edg[i].y<team[2]) team[2]=edg[i].y;
    if (team[2]<team[1]){int t=team[1]; team[1]=team[2];team[2]=t;}
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&q))
    {
        for (i=1;i<=m;i++) scanf("%d%d",&edg[i].x,&edg[i].y);
        for (i=1;i<=q;i++) scanf("%d",&a[i]),node[i]=i;
        sort(node+1,node+q+1,cmp1);
        sort(edg+1,edg+m+1,cmp2);
        j=m; tail=0; memset(ans,0,sizeof(ans));
        for (i=q;i>=1;i--)
        {
            int now=a[node[i]];
            while(j>=0&&edg[j].x>=now) add(j),j--;
            while(tail>0&&team[tail]>now) tail--;
            if (tail==2) ans[node[i]]=now-team[tail];
        }
        for (i=1;i<=q;i++) printf("%d\n",ans[i]);
    }
}

除了0是fail，其他都是win，然而我是蒙的，如何推导并不会。（好恶心的题X233）

#include<cstdio>
int n,i;
int a[]={1,0,1,0,1,1,0};
int main()
{
    while(~scanf("%d",&n))
    {
        if (n) printf("win\n");else printf("fail\n");
    }
}

http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=363

比赛一开始，发现好多人过了B题，我也点开看，博弈论？！然后怎么想都想不出解法。我尝试找规律，结果爆搜打错规律找错WA了。在尝试了各种规律一小时后，直觉告诉我，除了0，答案都是win！然后AC了。。。。。（为什么别人都能看出来，而我却如此SB）

再看来看去好像H题可做，先是想了一下树状数组维护区间和+二分答案，复杂度O（nlognlogn），有点心动了，可是感觉好麻烦，再想想，又发现只要维护最小值和次小值即可，一个不等号打反了，WA了一次，改回来AC。（后来得知可以线段树二分查询，这个解法也不错）

然而我卡了一个多小时在J题上，我的代码能力真的好差啊。思路不清晰+难以实现代码，最后无力调，弃疗了。

rank1做了11题啊，而我只做了2题，人与人的差距怎么那么大。。。

zxj说多做cf，做了一些题感觉很有启发，继续努力吧。ACMer不回头，菜鸟也能变大牛！