分块大法好！

dingshengyang · 2022-02-26 10:19:26 · 题解

块内排序加二分。

首先读入各数，然后用 block_{b,j} 保存第 b 块第 j 个数。

读入后 sort 一下。

然后每次二分查找。懒癌患者用 lower_bound。

然后是修改。先修改数组 A，然后在块内找到合适位置插入（类似于插入排序）。

没什么好讲的了，顺便说一下，块长本来应该取 \sqrt{n}，但是取 4096 可以卡常（>>12，编译器应该已经自动优化了，最优解 rank 4）。

好，上代码！

#include<algorithm>
using namespace std;

const int maxn = 300000 + 10;
const int SIZE = 4096;

int n,m,u,A[maxn],block[maxn/SIZE+1][SIZE];
void init(){
    scanf("%d%d%d",&n,&m,&u);
    int b = 0,j = 0;
    for(int i = 0;i < n;i ++){
        scanf("%d",&A[i]);
        block[b][j] = A[i];
        if(++j == SIZE){
            b++;j = 0;
        }
    }
    for(int i = 0;i < b;i ++)sort(block[i],block[i]+SIZE);
    if(j) sort(block[b],block[b]+j);
    return;
}

int query(int L,int R,int v){
    int lb = L/SIZE,rb = R/SIZE;
    int k = 0;
    if(lb == rb){
        for(int i = L;i <= R;i ++)
            if(A[i] < v)
                k ++;
    } else{
        for(int i = L;i < (lb+1)*SIZE;i ++)
            if(A[i] < v)
                k ++;
        for(int i = rb*SIZE;i <= R;i ++)
            if(A[i] < v)
                k ++;
        for(int b = lb+1;b < rb;b ++)
            k += lower_bound(block[b],block[b]+SIZE,v)-block[b];
    }
    return k;
}

void change(int p,int x){
    if(A[p] == x)return;
    int old = A[p],pos = 0,*B = &block[p/SIZE][0];
    A[p] = x;
    while(B[pos] < old)pos ++;B[pos] = x;
    if(x > old){
        while(pos < SIZE-1 && B[pos] > B[pos+1]){
            swap(B[pos+1],B[pos]);
            pos++;
        }
    }qq

    else{
        while(pos > 0 && B[pos] < B[pos-1]){
            swap(B[pos-1],B[pos]);
            pos--;
        }
    }

    return;
}

int main(){
    init();
    while(m--){
        int L,R,v,p;
        scanf("%d%d%d%d",&L,&R,&v,&p);L--;R--;p--;
        int k = query(L,R,v);
        change(p,(long long)u*k/(R-L+1));
    }
    for(int i = 0;i < n;i ++)
        printf("%d\n",A[i]);
    return 0;
}