星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P3380 【【模板】二逼平衡树(树套树)】

posted on 2017-12-06 21:34:47 | under 题解 |

大家好,我非常喜欢暴力数据结构,于是我就用分块过了这道题。

  1. 用一个原数组存储原值,另一个数组使得块内元素排序。O(nlogn)

  2. 对于1操作,边角暴力,块内二分。O(nsqrt(nlogn))。

  3. 对于3操作,原数组O(1)修改,排序数组修改后重新排序即可。 O(nsqrt(nlogn))

  4. 对于4操作,边角暴力,块内二分。 O(nsqrt(nlogn)) 。

  5. 对于5操作,边角暴力,块内二分。 O(nsqrt(nlogn)) 。

对于恶心到毁天灭地的2操作,外面套一个二分答案,边角暴力,块内二分,统计答案。

O(nlogssqrt(nlogn)) 。s在我的代码中为1e9,但实际上可以优化成查询区间的maximum-minimum。

总体上O(nlogssqrt(nlogn))。但因为毁天灭地的块内二分我一直写不出,导致12操作迫不得已使用了lower_bound和upper_bound,常数上也不小。大牛上最大点500ms,普通站70分。

P.S.为了维护dalao们的眼睛,我删去了调试部分代码,所以这上面并没有血的历史。为了这道题我奋斗了22天,尝试了各种各样的写法,把自己的代码在ftp、洛谷、mail上传来传去,找到了分块做区间第k大和树套树的两种std,加上几十次对拍,终于搞出了正解。如果大家有幸能够自己尝试用分块写这么一道题,会是一次非常磨砺身心而又具有充实感的挑战。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#define neko 50010
#define mid ((L+R)>>1)
#define midd ((LL+RR)>>1)
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
using std::stable_sort;
int bl[neko],Le[neko],Re[neko],a[neko],s[neko],n,m,blk;
template<typename T>
void read(T &x)
{
    char c=getchar();T p=1;x=0;
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c))
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }x*=p;
}
void split()
{
    int pre=1,prei=0;Le[1]=1;
    f(i,1,n)
    {
        s[i]=a[i],bl[i]=(i-1)/blk+1;
        if(bl[i]>pre)
        {
            stable_sort(s+prei,s+i);
            pre=bl[i],prei=i;
            Le[bl[i]]=i,Re[bl[i]-1]=i-1;
        }
    }Re[bl[n]]=n,stable_sort(s+prei,s+n+1);
}
int key(int l,int r,int x)
{
    int ans=1,L,R;
    f(i,l,chkmin(r,Re[bl[l]]))if(a[i]<x)++ans;
    f(i,bl[l]+1,bl[r]-1)ans+=std::lower_bound(s+Le[i],s+Re[i]+1,x)-(s+Le[i]);
    if(bl[l]!=bl[r])f(i,chkmax(l,Le[bl[r]]),r)if(a[i]<x)++ans;
    return ans;
}
int find(int l,int r,int x)
{
    int num,anss=1,L,R,LL=1,RR=1e9;
    while(LL<=RR)
    {
        num=0;
        f(i,l,chkmin(r,bl[l]*blk))if(a[i]<=midd)++num;
        f(i,bl[l]+1,bl[r]-1)num+=std::upper_bound(s+Le[i],s+Re[i]+1,midd)-(s+Le[i]);
        if(bl[l]!=bl[r])
            f(i,chkmax(l,Le[bl[r]]),r)
                if(a[i]<=midd)++num;
        if(num>=x)anss=midd,RR=midd-1;
        else LL=midd+1;
    }return anss;
}
void update(int pos,int x)
{
    a[pos]=x;int l=Le[bl[pos]],r=Re[bl[pos]];
    f(i,l,r)s[i]=a[i];
    stable_sort(s+l,s+r+1);
}
int lower(int l,int r,int x)
{
    int ans=-2147483647,L,R;
    f(i,l,chkmin(r,Re[bl[l]]))if(a[i]<x)ans=chkmax(ans,a[i]);
    f(i,bl[l]+1,bl[r]-1)
    {
        L=Le[i],R=Re[i];
        while(L<R)
        {
            if(s[mid]>=x)R=mid;
            else L=mid+1;
        }
        if(mid==Re[i])
        {
            if(s[mid]<x)ans=chkmax(ans,s[mid]);
            else ans=chkmax(ans,s[mid-1]);
        }else if(mid!=Le[i])ans=chkmax(ans,s[mid-1]);
    }
    f(i,chkmax(l,Le[bl[r]]),r)if(a[i]<x)ans=chkmax(ans,a[i]);
    return ans;
}
int upper(int l,int r,int x)
{
    int ans=2147483647,L,R;
    f(i,l,chkmin(r,Re[bl[l]]))if(a[i]>x)ans=chkmin(ans,a[i]);
    f(i,bl[l]+1,bl[r]-1)
    {
        L=Le[i],R=Re[i];
        while(L<R)
        {
            if(s[mid]>x)R=mid;
            else L=mid+1;
        }
        if(mid==Re[i]&&s[mid]<=x)continue;
        ans=chkmin(ans,s[mid]);
    }
    f(i,chkmax(l,Le[bl[r]]),r)if(a[i]>x)ans=chkmin(ans,a[i]);
    return ans;
}
int main()
{
    int opt,x,y,k;
    scanf("%d%d",&n,&m);
    f(i,1,n)read(a[i]);if(n==1)blk=1;else blk=sqrt(n);
    split();
    f(i,1,m)
    {
        read(opt),read(x),read(y);
        if(opt==1)read(k),printf("%d\n",key(x,y,k));
        if(opt==2)read(k),printf("%d\n",find(x,y,k));
        if(opt==3)update(x,y);
        if(opt==4)read(k),printf("%d\n",lower(x,y,k));
        if(opt==5)read(k),printf("%d\n",upper(x,y,k));
    }return 0;
}