[LOJ] 分块九题 2

区间修改，查询区间第k大。
块内有序（另存），块内二分。
还是用vector吧，数组拷贝排序，下标搞不来。。
//Stay foolish,stay hungry,stay young,stay simple

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<vector>

using namespace std;

const int MAXN=500005;

vector<int> b[1000];

inline int read_d(){

    int ret=0,f=1;char c;

    while(c=getchar(),!isdigit(c)) f=c=='-'?-1:1;

    while(isdigit(c)){

        ret*=10;ret+=c-'0';

        c=getchar();

    }

    return f*ret;

}

int n;

int a[MAXN],inc[MAXN],l[MAXN],

    r[MAXN],bl[MAXN];

int block,num;

void reset(int id){

    b[id].clear();

    for(int i=l[id];i<=r[id];i++) b[id].push_back(a[i]);

    sort(b[id].begin(),b[id].end());

} 

void build(){

    block=sqrt(n);

    block>>=1;

    num=n/block;

    if(n%block) num++;

    for(int i=1;i<=num;i++)

        l[i]=(i-1)*block+1,

        r[i]=i*block;

    r[num]=n;

    for(int i=1;i<=n;i++)

        bl[i]=(i-1)/block+1;

    for(int i=1;i<=num;i++) reset(i);

}

void updata(int x,int y,int w){

    if(bl[x]==bl[y]){

        for(int i=x;i<=y;i++)

            a[i]+=w;

        reset(bl[x]);

        return;

    }

    for(int i=x;i<=r[bl[x]];i++)

        a[i]+=w;

    reset(bl[x]);

    for(int i=bl[x]+1;i<=bl[y]-1;i++)

        inc[i]+=w;

    for(int i=l[bl[y]];i<=y;i++)

        a[i]+=w;

    reset(bl[y]);

}

int query(int x,int y,int w){

    int ret=0;

    if(bl[x]==bl[y]){

        for(int i=x;i<=y;i++)

            ret+=(a[i]+inc[bl[i]]<w);

        return ret;

    }

    for(int i=x;i<=r[bl[x]];i++)

        ret+=(a[i]+inc[bl[i]]<w);

    for(int i=l[bl[y]];i<=y;i++)

        ret+=(a[i]+inc[bl[i]]<w);

    int flag=0;

    for(int i=bl[x]+1;i<=bl[y]-1;i++){

        int tar=w-inc[i];

        ret+=lower_bound(b[i].begin(),b[i].end(),tar)-b[i].begin();

    }

    return ret;

}

int main(){

    n=read_d();

    for(int i=1;i<=n;i++) a[i]=read_d();

    build();

    for(int i=1;i<=n;i++){

        int q,x,y,z;

        q=read_d();

        x=read_d();

        y=read_d();

        z=read_d();

        if(q==0) updata(x,y,z);

        else printf("%d\n",query(x,y,z*z));

    }

    return 0;

}
巴特西

[LOJ] 分块九题 2

最新文章

热门文章
