Splayテンプレートcodevs 1296&&codevs 1286うっとうしい

先にボードを保存(完全にテストされていません)

#include<cstdio>
#include<algorithm>
using namespace std;

struct Node{
    int key;//size
    Node *l,*r,*f;//left,right,father
};
class SplayTree{
public:
    void Init(){rt=NULL;}
    void Zag(Node *x){//left rotate
        Node *y=x->f;//y is the father of x
        y->r = x->l;
        if (x->l)x->l->f = y;//if x has left child
        x->f =y->f;
        if (y->f){//y is not root
            if (y==y->f->l)y->f->l=x;//y if left child
            else y->f->r=x;//y is right child
        }
        y->f=x;
        x->l=y;
    }

    void Zig(Node *x){//right rotate
        Node *y=x->f;//y is the father of x
        y->l = x->r;
        if (x->r)x->r->f=y;
        x->f = y->f;
        if (y->f){
            if (y==y->f->l)y->f->l=x;
            else y->f->r=x;
        }
        y->f=x;
        x->r=y;
    }

    void Splay(Node *x){
        while (x->f){
            Node *p=x->f;
            if (!p->f){
                if (x==p->l)Zig(x);
                else Zag(x);
            }else if (x==p->l){
                if (p==p->f->l){Zig(p);Zig(x);}
                else {Zig(x);Zag(x);}
            }else {//x==p->r
                if (p==p->f->r){Zag(p);Zag(x);}
                else {Zag(x);Zig(x);}
            }
        }
        rt=x;
    }

    Node *Find(int x){
        Node *T=rt;
        while (T){
            if (T->key==x){Splay(T);return T;}
            else if (x<T->key)T=T->l;
            else T=T->r;
        }
        return T;
    }

    void Insert(int x){
        Node *T=rt,*fa=NULL;
        while (T){
            fa=T;
            if (x<T->key)T=T->l;
            else if(x>T->key)T=T->r;
            else return ;//two the same keys
        }
        T=(Node*)malloc(sizeof(Node));
        T->key=x;
        T->l=T->r=NULL;
        T->f=fa;
        if (fa){
            if (fa->key>x)fa->l=T;
            else fa->r=T;
        }
        Splay(T);
    }

    void Delete(int x){
        Node *T=Find(x);
        if (NULL==T)return ;//error
        rt=Join(T->l,T->r);
    }

    Node *Maxnum(Node *t){
        Node *T=t;
        while (T->r)T=T->r;
        Splay(T);
        return T;
    }

    Node *Minnum(Node *t){
        Node *T=t;
        while (T->l)T=T->l;
        Splay(T);
        return T;
    }

    Node *Last(int x){
        Node *T=Find(x);
        T=T->l;
        return (Maxnum(T));
    }

    Node *Next(int x){
        Node *T=Find(x);
        T=T->r;
        return (Minnum(T));
    }

    Node *Join(Node *t1,Node *t2){
        if (NULL==t1)return t2;
        if (NULL==t2)return t1;
        Node *T=Maxnum(t1);
        T->l=t2;
        return T;
    }

    void Split(int x,Node *&t1,Node *&t2){
        Node *T=Find(x);
        t1=T->l;
        t2=T->r;
    }

    void Inorder(Node *T){
        if (NULL==T)return ;
        Inorder(T->l);
        printf("%d->",T->key);
        Inorder(T->r);
    }

    void _Delete(){Delete(rt);}
    void Delete(Node *T){
        if (NULL==T)return ;
        Delete(T->l);
        Delete(T->r);
        free(T);
    }

private:
    Node *rt;//root
};

int main(){
    return 0;
}

[HNOI 2002]売上統計codevs 1296本題頭を使わず

/* Author : cww97 Problem: p1296   CodeVs */
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=0xfffffff;
int ans;
struct Node{
    int key;
    Node *l,*r,*f;//left,right,father
};

class SplayTree{
public:
    void Init(){
        rt=NULL;
        int x;scanf("%d",&x);
        ans=x;
        Insert(x);
    }
    void Zag(Node *x){//left rotate
        Node *y=x->f;//y is the father of x
        y->r = x->l;
        if (x->l)x->l->f = y;//if x has left child
        x->f =y->f;
        if (y->f){//y is not root
            if (y==y->f->l)y->f->l=x;//y if left child
            else y->f->r=x;//y is right child
        }
        y->f=x;
        x->l=y;
    }
    void Zig(Node *x){//right rotate
        Node *y=x->f;//y is the father of x
        y->l = x->r;
        if (x->r)x->r->f=y;
        x->f = y->f;
        if (y->f){
            if (y==y->f->l)y->f->l=x;
            else y->f->r=x;
        }
        y->f=x;
        x->r=y;
    }
    void Splay(Node *x){
        while (x->f){
            Node *p=x->f;
            if (!p->f){
                if (x==p->l)Zig(x);
                else Zag(x);
            }else if (x==p->l){
                if (p==p->f->l){Zig(p);Zig(x);}
                else {Zig(x);Zag(x);}
            }else {//x==p->r
                if (p==p->f->r){Zag(p);Zag(x);}
                else {Zag(x);Zig(x);}
            }
        }
        rt=x;
    }

    Node *Find(int x,int &d){
        Node *T=rt;
        while (T){
            if (T->key==x){Splay(T);d=0;return T;}
            else if (x < T->key){d=min(d,T->key-x);T=T->l;}
            else {d=min(d,x-T->key);T=T->r;}
        }
        return T;
    }
    void Insert(int x){
        Node *T=rt,*fa=NULL;
        while (T){
            fa=T;
            if (x<T->key)T=T->l;
            else if(x>T->key)T=T->r;
            else return ;//two the same keys
        }
        T=(Node*)malloc(sizeof(Node));
        T->key=x;
        T->l=T->r=NULL;
        T->f=fa;
        if (fa){
            if (fa->key>x)fa->l=T;
            else fa->r=T;
        }
        Splay(T);
    }

    void Work(int x){
        int d=INF;
        Node *T=Find(x,d);
        if (T)return;
        ans+=d;
        Insert(x);
    }

    void _Delete(){Delete(rt);}
    void Delete(Node *T){
        if (NULL==T)return ;
        Delete(T->l);
        Delete(T->r);
        free(T);
    }

private:
    Node *rt;//root
};

int main(){
    int n,x;scanf("%d",&n);
    SplayTree T;
    T.Init();
    for (n--;n--;){
        scanf("%d",&x);
        T.Work(x);
    }
    printf("%d
",ans);
    T._Delete();
    return 0;
}

[NOI 2004]うっとうしい出納員codevs 1286この問題は大体sizeドメインを複数維持してk番目の値を計算することであり、書くのはうっとうしい、、、次のコード、、、やはりWAの状態、、、うるさい、うるさい、夏休みは振り返ってみよう

#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=0x7ffffff;
int m,d,ans;
struct Node{
    int key,s;//size
    Node *l,*r,*f;//left,right,father
};

class SplayTree{
public:
    void Init(){rt=NULL;}
    int S(Node *T){return (NULL==T)?0:T->s;}
    void Zag(Node *x){//left rotate
        Node *y=x->f;//y is the father of x
        y->r = x->l;
        if (x->l)x->l->f = y;//if x has left child
        x->f =y->f;
        if (y->f){//y is not root
            if (y==y->f->l)y->f->l=x;//y if left child
            else y->f->r=x;//y is right child
        }
        y->f=x;
        x->l=y;
        y->s=S(y->l)+S(y->r)+1;
        x->s=S(x->l)+S(x->r)+1;
    }
    void Zig(Node *x){//right rotate
        Node *y=x->f;//y is the father of x
        y->l = x->r;
        if (x->r)x->r->f=y;
        x->f = y->f;
        if (y->f){
            if (y==y->f->l)y->f->l=x;
            else y->f->r=x;
        }
        y->f=x;
        x->r=y;
        y->s=S(y->l)+S(y->r)+1;
        x->s=S(x->l)+S(x->r)+1;
    }
    void Splay(Node *x){
        while (x->f){
            Node *p=x->f;
            if (!p->f){
                if (x==p->l)Zig(x);
                else Zag(x);
            }else if (x==p->l){
                if (p==p->f->l){Zig(p);Zig(x);}
                else {Zig(x);Zag(x);}
            }else {//x==p->r
                if (p==p->f->r){Zag(p);Zag(x);}
                else {Zag(x);Zig(x);}
            }
        }
        rt=x;
    }

    int Findkth(Node *T,int k){//find the K-th biggest number
        //printf("T=%d,??l%d
",T->key,S(T->r));
        if (k<=S(T->r))return Findkth(T->r,k);
        if (k==S(T->r)+1)return T->key;
        return Findkth(T->l,k-S(T->r)-1);
    }

    void Insert(int x){
        Node *T=rt,*fa=NULL;
        while (T){
            fa=T;
            T->s++;
            if (x<T->key)T=T->l;
            else {T=T->r;}
        }
        T=(Node*)malloc(sizeof(Node));
        T->key=x;
        T->l=T->r=NULL;
        T->f=fa;
        T->s=1;
        if (fa){
            if (fa->key>x)fa->l=T;
            else fa->r=T;
        }
        Splay(T);
    }

    int Goaway(Node *&T,Node *fa){
        if (NULL==T)return 0;
        int go;
        if (T->key+d<m){
            go=Goaway(T->r,T)+S(T->l)+1;
            //printf("go=%d
",go);
            if (T==rt&&NULL==T->r){rt=NULL;return go;}
            //else fa->l=NULL;
            //Delete(T);
            if (T->r){
                T->r->s=T->s-go;
                T=T->r;T->f=fa;
            }
        }else{
            go=Goaway(T->l,T);
            T->s-=go;
        }
        return go;
    }

    void Work(char ch,int x){
        //printf("%c %d
",ch,x);
        if (ch=='I'&&x>=m)Insert(x-d);
        if (ch=='A')d+=x;
        if (ch=='S'){d-=x;ans+=Goaway(rt,NULL);}
        if (ch=='F'){
            if (S(rt) < x)puts("-1");
            else printf("%d
",Findkth(rt,x)+d);
        }
        //Inorder(rt);printf("d=%d,ans=%d
",d,ans);
    }

    void Inorder(Node *T){
        if (NULL==T)return ;
        Inorder(T->l);
        if (rt==T)printf("!");
        printf("%d(%d)->",T->key,T->s);
        Inorder(T->r);
    }

    void _Delete(){Delete(rt);}
    void Delete(Node *T){
        if (NULL==T)return ;
        Delete(T->l);
        Delete(T->r);
        free(T);
    }

private:
    Node *rt;//root
};

int main(){
    freopen("fuck.in","r",stdin);
    SplayTree T;
    T.Init();
    int n,x;
    char ch;
    scanf("%d%d
",&n,&m);
    for (;n--;){
        scanf("%c %d
",&ch,&x);
        T.Work(ch,x);
    }
    printf("%d
",ans);
    return 0;
}