[LOJ] 分块九题 2

https://loj.ac/problem/6278

区间修改，查询区间第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
",query(x,y,z*z));
    }
    return 0;
}