absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] NFLJ OJ 1124 解题报告
[破碎的状态] Gym 100960G

[破碎的状态] BZOJ 1503 郁闷的出纳员(Splay版)

absi2011 posted @ Apr 21, 2016 01:07:56 PM in 刷题记录 with tags 小高考 Splay bzoj , 535 阅读

注意delete_node的时候有时候可能会写炸了

void delete_node(node * &x,int y)
{
    x->size--;
    if (x->val==y)
    {
        //xxx
        rotate(x,c);
        delete_node(x->ch[!c],y);
    }
    else
    {
        //xxx
    }
}

所以整体代码如下

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int val;
    int size;
    node * father;
    node * ch[2];
};
node * null;
node * root;
node * new_node(int x=0)
{
    static node a[100005];
    static int top=0;
    node * t=&a[top++];
    t->val=x;
    t->size=1;
    t->father=null;
    t->ch[0]=null;
    t->ch[1]=null;
    return t;
}
void insert_node(node * &x,node * y)
{
    if (x==null)
    {
        x=y;
        return;
    }
    x->size++;
    int c;
    if (y->val>x->val) c=1; else c=0;
    y->father=x;
    insert_node(x->ch[c],y);
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]->father=x;
    y->ch[!c]=x;
    y->size=x->size;
    y->father=x->father;
    x->size=x->ch[0]->size+x->ch[1]->size+1;
    x->father=y;
    x=y;
}
int get_up(node * x)
{
    if (x->father->ch[0]==x) return 0;
    if (x->father->ch[1]==x) return 1;
    return -1;
}
void splay(node * x)
{
    for (;;)
    {
        int t1=get_up(x);
        int t2=get_up(x->father);
        int t3=get_up(x->father->father);
        if (t1==-1)
        {
            root=x;
            return;
        }
        else if (t2==-1)
        {
            rotate(root,t1);
            return;
        }
        else if (t3==-1)
        {
            if (t1==t2)
            {
                rotate(root,t2);
                rotate(root,t1);
            }
            else
            {
                rotate(root->ch[t2],t1);
                rotate(root,t2);
            }
        }
        else
        {
            if (t1==t2)
            {
                x=x->father->father->father;
                rotate(x->ch[t3],t2);
                rotate(x->ch[t3],t1);
                x=x->ch[t3];
            }
            else
            {
                x=x->father->father;
                rotate(x->ch[t2],t1);
                x=x->father;
                rotate(x->ch[t3],t2);
                x=x->ch[t3];
            }
        }
    }
}
int find_kth(node * x,int y)
{
    if (x->ch[0]->size>=y) return find_kth(x->ch[0],y);
    if (x->ch[0]->size+1==y) return x->val;
    return find_kth(x->ch[1],y-x->ch[0]->size-1);
}
void delete_node(node * &x,int y)
{
    x->size--;
    if (x->val==y)
    {
        int c=-1;
        if (x->ch[0]!=null) c=0;
        if (x->ch[1]!=null) c=1;
        if (c==-1)
        {
            x=null;
            return;
        }
        rotate(x,c);
        delete_node(x->ch[!c],y);
    }
    else
    {
        if (y>x->val)
        {
            delete_node(x->ch[1],y);
        }
        else
        {
            delete_node(x->ch[0],y);
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    int sum=0;
    null=new_node();
    null->ch[0]=null;
    null->ch[1]=null;
    null->father=null;
    null->size=0;
    root=null;
    int ufo=0;
    for (i=0;i<n;i++)
    {
        static char a[5];
        scanf("%s",a);
        int x;
        scanf("%d",&x);
        if (a[0]=='I')
        {
            if (x<m) continue;
            node * t=new_node(x-sum);
            insert_node(root,t);
            if (rand()&1) splay(t);
        }
        else if (a[0]=='A')
        {
            sum+=x;
        }
        else if (a[0]=='S')
        {
            sum-=x;
            for (;;)
            {
                if (root->size==0) break;
                int t=find_kth(root,1);
                if (t+sum>=m) break;
                delete_node(root,t);
                ufo++;
            }
        }
        else
        {
            if (root->size<x)
            {
                printf("-1\n");
                continue;
            }
            printf("%d\n",find_kth(root,root->size-x+1)+sum);
        }
    }
    printf("%d\n",ufo);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter