【bzoj3678】wangxz与OJ

2015.03.19 19:04 Thu | 20次阅读 | 旧日oi | 固定链接 | 源码

Description

某天,wangxz神犇来到了一个信息学在线评测系统(Online Judge)。由于他是一位哲♂学的神犇,所以他不打算做题。他发现这些题
目呈线性排列,被标记为1~n号,每道题都有一个难度值(可以<=0)。他决定与这些题目玩♂耍。
1、他可以在某个位置插♂入一些难度值特定的题目。
2、他可以吃♂掉(删除)一段题目。
3、他可以查询某个位置的题目的难度值。
维护一个初始有n个元素的序列(标记为1~n号元素),支持以下操作:
0 p a b (0<=p<=当前序列元素个数) (a<=b) 在p位置和p+1位置之间插入整数:a,a+1,a+2,...,b-1,b。若p为0,插在序列最前面;
1 a b (1<=a<=b<=当前序列元素个数) 删除a,a+1,a+2,...,b-1,b位置的元素;
2 p (1<=p<=当前序列元素个数) 查询p位置的元素。

Input

输入第一行包括两个正整数n(1<=n<=20000),m(1<=m<=20000),代表初始序列元素个数和操作个数。
接下来n个整数,为初始序列元素。
接下来m行,每行第一个为整数sym,
若sym=0,接下来有一个非负整数p,两个整数a,b;
若sym=1,接下来有两个正整数a,b;
若sym=2,接下来有一个正整数p;
p、x、y的含义及范围见题目描述。
在任何情况下,保证序列中的元素总数不超过100000。
保证题目涉及的所有数在int内。

Output

对每个sym=2,输出一行,包括一个整数,代表询问位置的元素。

Sample Input

5 3
1 2 3 4 5
0 2 1 4
1 3 8
2 2

Sample Output

2

题解

这是今天考试题,由于题目总量会达到10^9次方,所以一般的splay肯定会挂掉(任何一种存题目的数据结构都不行)。
考虑到插入的时候有一个特殊的性质,就是题目的难度是连续的,所以这启发我们可以将一段题目序列缩成两个点,记录一下长度以及初值和末值
开始的节点正常插入就行了,接下来每次插入一个点,看他是否被其它点包含,如果不包含,直接建立新点,否则要把原来的点拆成3个点,也就是将原有区间分成3段,这是可以实现的。
删除的时候也是如此,找到要删除的两个端点的前驱和后继,判断是否需要拆点(这个判断对于前驱和后继是不一样的,坑了我好久)。
查询比较水,不说了
bzoj刷了一发rank3,,第一次上榜!!!

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 100010
#define lson son[x][0]
#define rson son[x][1]
#define is(x) (son[fa[x]][1]==x)
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int a[maxn];
int root,cnt;
int size[maxn],son[maxn][2],num[maxn],l[maxn],r[maxn],fa[maxn];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void update(int x)
{
    size[x]=size[lson]+size[rson]+num[x];
}
void newnode(int &pos,int a,int b,int f)
{
    pos=++cnt;
    num[pos]=b-a+1;l[pos]=a;r[pos]=b;fa[pos]=f;
}
void link(int x,int y,int d)
{
    fa[x]=y;
    son[y][d]=x;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],i=is(x),t=son[x][!i];
    link(t,y,i);link(x,z,is(y));link(y,x,!i);
    son[0][0]=son[0][1]=0;fa[0]=0;
    update(y);update(x);
}
void splay(int x,int k)
{
    int y,z;
    while(fa[x]!=k)
    {
        y=fa[x];z=fa[y];
        if(z==k) rotate(x);
        else rotate(is(y)==is(x)?y:x),rotate(x);
    }
    if(!k) root=x;
}
void build(int &x,int l,int r,int f)
{
    if(l>r) return ;
    int mid=(l+r)>>1;
    newnode(x,a[mid],a[mid],f);
    if(mid==0||mid==n+1) size[x]=1;
    build(lson,l,mid-1,x);
    build(rson,mid+1,r,x);
    update(x);
}
void init()
{
    for(int i=1;i<=n;i++)
    a[i]=read();
    build(root,0,n+1,0);
}
void insert(int k,int a,int b)
{
    int x,t,f;
    for(x=root;;)
    if(size[lson]>=k) x=lson;
    else if(size[lson]+num[x]>=k) break;
    else k-=size[lson]+num[x],x=rson;
    k-=size[lson];
    splay(x,0);
    if(k<num[x])
    {
        newnode(t,l[x]+k,r[x],f);
        r[x]=l[x]+k-1;num[x]=r[x]-l[x]+1;
        link(rson,t,1);link(t,x,1);update(t);
    }
    newnode(t,a,b,f);
    link(rson,t,1);link(t,x,1);
    update(t);update(x);
}
void del(int a,int b)
{
    int x=root,k=a,t,f;
    for(k=a;;)
    {
        if(size[lson]>=k) x=lson;
        else if(size[lson]+num[x]>=k) break;
        else k-=size[lson]+num[x],x=rson;
    }
    k-=size[lson];
    if(k<num[x])
    {
        newnode(t,l[x]+k,r[x],f);
        r[x]=l[x]+k-1;num[x]=r[x]-l[x]+1;
        link(rson,t,1);link(t,x,1);
        update(t);update(x);
    }
    splay(x,0);
    for(x=root,k=b;;)
    {
        if(size[lson]>=k) x=lson;
        else if(size[lson]+num[x]>=k) break;
        else k-=size[lson]+num[x],x=rson;
    }
    k-=size[lson];
    if(k>1)
    {
        newnode(t,l[x]+k-1,r[x],f);
        r[x]=l[x]+k-2;num[x]=r[x]-l[x]+1;
        link(rson,t,1);link(t,x,1);
        update(t);update(x);
        splay(t,root);
        son[t][0]=0;
        update(t);update(root);
    }
    else
    {
        splay(x,root);
        son[x][0]=0;
        update(x);update(root);
    }
}
int get_ans(int p)
{
    for(int x=root;;)
    {
        if(size[lson]>=p) x=lson;
        else if(size[lson]+num[x]>=p) return l[x]+p-size[lson]-1;
        else p-=size[lson]+num[x],x=rson;
    }
}
int main()
{
    n=read();m=read();init();
    for(int opt,p,a,b,i=1;i<=m;i++)
    {
        opt=read();
        if(opt==0)
        {
            p=read();a=read();b=read();
            insert(p+1,a,b);
        }
        else if(opt==1)
        {
            a=read();b=read();
            del(a,b+2);
        }
        else
        {
            p=read();
            printf("%d\n",get_ans(p+1));
        }
    }
    return 0;
}```