Bakser's Blog

我是逗比。

bzoj3196 树套树

| Comments

线段树套平衡树水过
此题没有必要启发式(bao li)合并每个平衡树,前驱后继直接找最后取个最值,k值用二分。
二分时可以在根节点的平衡树上二分,不过我懒就没写。。。。
1A还是比较爽的,耗时就比较逗比了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define N 60000
#define MAXN N*33
#define lson x<<1
#define rson x<<1|1
#define INF 0x7f7f7f7f
#define inf 100000001
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
struct seg_tree
{
    int root;
    seg_tree(){
        root=0;
    }
}tree[N<<2];
queue<int> pool;
int n,m,opt,a[N],tot,pos,L,R,old,now;
int size[MAXN],pre[MAXN],val[MAXN],son[MAXN][2],cnt[MAXN];
inline void newnode(int &x,int fa,int key)
{
    if(!pool.empty())x=pool.front(),pool.pop();
    else x=++tot;
    pre[x]=fa;
    val[x]=key;
    size[x]=cnt[x]=1;
    son[x][0]=son[x][1]=0;
}
inline void push_up(int x)
{
    size[x]=size[son[x][0]]+size[son[x][1]]+cnt[x];
}
inline void rotate(int x,int f)
{
    int y=pre[x];
    son[y][!f]=son[x][f];
    pre[son[x][f]]=y;
    if(pre[y])son[pre[y]][son[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    son[x][f]=y;
    pre[y]=x;
    push_up(y);
}
inline void splay(int &root,int x,int goal)
{
    while(pre[x]!=goal)
    {
        if(pre[pre[x]]==goal)rotate(x,son[pre[x]][0]==x);
        else
        {
            int y=pre[x],f=(son[pre[y]][0]==y);
            if(son[y][f]==x)rotate(x,!f);
            else rotate(y,f);
            rotate(x,f);
        }
    }
    push_up(x);
    if(!goal)root=x;
}
inline int find(int root,int key)
{
    int x=root;
    while(val[x]!=key)
    if(son[x][val[x]<key])x=son[x][val[x]<key];
    else break;
    return x;
}
inline void insert(int &root,int key)
{
    if(!root)newnode(root,0,key);
    else
    {
        int pos=find(root,key);
        if(val[pos]==key){cnt[pos]++;splay(root,pos,0);return;}
        newnode(son[pos][val[pos]<key],pos,key);
        splay(root,son[pos][val[pos]<key],0);
    }
}
inline void del(int &root,int key)
{
    int x=find(root,key);
    splay(root,x,0);
    if(cnt[x]>1){cnt[x]--;push_up(x);return;}
    if(!son[x][1]){root=son[x][0];pre[son[x][0]]=0;return;}
    int y=son[x][1];
    while(son[y][0])y=son[y][0];
    splay(root,y,x);
    son[y][0]=son[x][0];
    pre[son[x][0]]=y;
    root=y;
    pre[y]=0;
    pool.push(x);
    push_up(y);
}
inline int get_near(int &root,int key,int f)//0->pre 1->succ
{
    int x=find(root,key);
    if(val[x]==key)
    {
        splay(root,x,0);
        for(x=son[x][f];son[x][!f];x=son[x][!f]);
        return val[x];
    }
    while(((val[x]>key)^f&&val[x]!=key)&&pre[x])x=pre[x];
    if((val[x]>key)^f)return (opt-4)?INF:0;
    return val[x];
}
inline int get_rank(int &root,int key)
{
    int x=find(root,key);
    splay(root,x,0);
    return size[son[x][0]]+(val[x]<key?cnt[x]:0);
}
/*华丽丽的分割线*/
inline void build_tree(int x,int l,int r)
{
    for(int i=l;i<=r;i++)insert(tree[x].root,a[i]);
    if(l==r)return;
    int mid=l+r>>1;
    build_tree(lson,l,mid);
    build_tree(rson,mid+1,r);
}
inline void modify(int x,int l,int r)
{
    del(tree[x].root,old);
    insert(tree[x].root,now);
    if(l==r)return;
    int mid=l+r>>1;
    if(pos<=mid)modify(lson,l,mid);
    else modify(rson,mid+1,r);
}
inline int ask_rank(int x,int l,int r,int key)
{
    if(l>=L&&r<=R)return get_rank(tree[x].root,key);
    int mid=l+r>>1,res=0;
    if(L<=mid)res+=ask_rank(lson,l,mid,key);
    if(R>mid)res+=ask_rank(rson,mid+1,r,key);
    return res;
}
inline int ask_near(int x,int l,int r,int key)
{
    if(l>=L&&r<=R)return get_near(tree[x].root,key,opt-4);
    int mid=l+r>>1,tmp,res=(!(opt-4)?0:INF);
    if(L<=mid)tmp=ask_near(lson,l,mid,key),res=(!(opt-4)?(MAX(res,tmp)):MIN(res,tmp));
    if(R>mid)tmp=ask_near(rson,mid+1,r,key),res=(!(opt-4)?(MAX(res,tmp)):MIN(res,tmp));
    return res;
}
inline int ask_kth(int k)
{
    int l=0,r=inf;
    while(l+1<r)
    {
        int mid=l+r>>1,tmp=ask_rank(1,1,n,mid);
        if(tmp<k)l=mid;
        else r=mid;
    }
    return l;
}
int main()
{
    tot=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",a+i);
    build_tree(1,1,n);
    for(int i=0,x,y,z;i<m;i++)
    {
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==3)
        {
            pos=x;old=a[x];now=y;
            modify(1,1,n);
            a[x]=y;
            continue;     
        }
        scanf("%d",&z);
        L=x,R=y;
        if(opt==1)printf("%d\n",ask_rank(1,1,n,z)+1);
        else if(opt==2)printf("%d\n",ask_kth(z));
        else if(opt==4||opt==5)printf("%d\n",ask_near(1,1,n,z));
    }
    return 0;
}

Comments

comments powered by Disqus