一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 P3834 【【模板】可持久化线段树 1(主席树)】

posted on 2019-03-15 22:03:31 | under 题解 |

早就想发一篇纯分块的题解了, 因为各种事情耽误了几个月......

所以蒟蒻也就不多废话了, 直接进入正题:

值域分块在n sqrt(n)的时间内解决该问题

那么我们该怎样解决这个问题呢qwq?

我们先把数列分块, 再把值域分块, 然后维护两个数组cnt1, cnt2, cnt1(i, j)表示前i个数列块中第j个值域块的数值出现的次数和, cnt2(i, j)表示前i个块中j这个数字出现的次数。 这两个数组显然可以在n sqrt(n)的时间内处理完成。

那么接下来当我们求l r 区间的第k大的时候, 对于散块, 我们用两个临时数组san, san2 来记录和cnt1 cnt2一样的东西(只不过这个记录的是散块中的信息, 而不是前缀和), 然后对于整块, 因为我们已经处理出了前缀和, 所以可以直接从头开始扫值域块, 累加cnt1+san , 直到这个数量大于我们要查询的k, 这时候就能确定我们要查询的数值再哪一个值域块中了。 下面只要在扫一遍这个值域块中的每一个数, 通过cnt2和san2 就能知道具体要查询的是哪个数了qwqwq。

那么就没啥了啊qwqwq 如果有什么问题的话私信小蒟蒻就好啦qwqwq

那么代码如下

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio> 
#define maxn 200010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, k;
int sq, sq2;
int nw[maxn], a[maxn], b1[maxn], b2[maxn], cnt1[500][500], cnt2[480][maxn], q[maxn][4], z[maxn];
int san[500], san2[maxn];

inline void in(re int &x){
    x=0;int bl = 1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c == '-')
          bl = -1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x *= bl;
}

void out(re int a){
    if(a < 0) {
        putchar('-');
        a = -a;
    }
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

int get_val(int x, int y, int k) {
    int res = 0, pd = 0;
    FOR(i, x, min(y, b1[x]*sq))
      ++san[b2[nw[i]]], ++san2[nw[i]];
    if(b1[x] != b1[y])
      FOR(i, (b1[y]-1)*sq+1, y)
        ++san[b2[nw[i]]], ++san2[nw[i]];
    FOR(i, 1, b2[z[0]]) {
        int ld = cnt1[b1[y]-1][i]-cnt1[b1[x]][i];
        if(ld < 0) ld = 0;
        if(res+(ld+san[i]) < k) { 
            res += san[i];
            if(cnt1[b1[y]-1][i]-cnt1[b1[x]][i] > 0)
              res += cnt1[b1[y]-1][i]-cnt1[b1[x]][i];
        }
        else {
            pd = i; 
            break;
        }
    }
    int anss = -1;
    FOR(i, (pd-1)*sq2+1, pd*sq2) {
        res += san2[i];
        if(cnt2[b1[y]-1][i]-cnt2[b1[x]][i] > 0)
          res += cnt2[b1[y]-1][i]-cnt2[b1[x]][i];
        if(res >= k) {
            anss = z[i];
            break;
        }
    }
    FOR(i, x, min(y, b1[x]*sq))
      --san[b2[nw[i]]], --san2[nw[i]];
    if(b1[x] != b1[y])
      FOR(i, (b1[y]-1)*sq+1, y)
        --san[b2[nw[i]]], --san2[nw[i]];
    return anss;
}

int main() {
    in(n), in(m);
    sq = sqrt(n);
    FOR(i, 1, n)
      in(a[i]), b1[i] = (i-1)/sq+1, z[++z[0]] = a[i];
    FOR(i, 1, m) {
        in(q[i][1]),
        in(q[i][2]),
        in(q[i][3]);
    }
    sort(z+1, z+z[0]+1);
    z[0] = unique(z+1, z+z[0]+1)-z-1;
    sq2 = sqrt(z[0]);
    FOR(i, 1, z[0])
      b2[i] = (i-1)/sq2+1;
    FOR(i, 1, n) {
        nw[i] = lower_bound(z+1, z+z[0]+1, a[i])-z; //nw为a排序后的位置,处理cnt1, cnt2 
        ++cnt1[b1[i]][b2[nw[i]]];
        ++cnt2[b1[i]][nw[i]];
    }
    FOR(i, 1, b1[n]) { //处理前缀和 
        FOR(j, 1, b2[z[0]]) 
          cnt1[i][j] += cnt1[i-1][j];
        FOR(j, 1, z[0])
          cnt2[i][j] += cnt2[i-1][j];
    }
    FOR(i, 1, m) {
        out(get_val(q[i][1], q[i][2], q[i][3]));
        putchar(10);
    }
}