LOJ #6278. 数列分块入门 2

题目链接

思路&&代码

区间修改+询问区间内小于某个值x的元素个数

还是先分块，分成\(\sqrt{n}\)个块，分的时候，每个块用一个\(vector\)来维护块内的值

每个块内排序，保证块内是有序的（便于用\(lower\_bound\)统计答案)，因为分好了这个块以后如果整体修改不会对块内元素造成影响，如果不是整个块修改的话，可以修改之后再顺便排序，覆盖之前这个块的值

统计答案的时候整个块用\(lower\_bound\)，局部直接暴力枚举，还是\(O(n\sqrt{n})\)

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int A = 1e5 + 11;

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    for ( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return x * f;
}

vector <int> v[500];

int n, m, a[A], L[A], R[A], add[A], pos[A];

void reset(int x) {
    v[x].clear();
    for(int i = L[x]; i <= R[x]; i++) v[x].push_back(a[i]);
    sort(v[x].begin(), v[x].end());
}

void change(int l, int r, int c) {
    int p = pos[l], q = pos[r];
    if(p == q) {
        for(int i = l; i <= r; i++) a[i] += c;
        reset(p); return;
    }
    for(int i = l; i <= R[p]; i++) a[i] += c; reset(p);
    for(int i = L[q]; i <= r; i++) a[i] += c; reset(q);
    for(int i = p + 1; i < q; i++) add[i] += c;
    
}

int ask(int l, int r, int c, int ans = 0) {
    int p = pos[l], q = pos[r];
    if(p == q) {
        for(int i = l; i <= r; i++) if(a[i] + add[p] < c) ans++;
        return ans;
    }
    for(int i = l; i <= R[p]; i++) if(a[i] + add[p] < c) ans++;
    for(int i = L[q]; i <= r; i++) if(a[i] + add[q] < c) ans++;
    for(int i = p + 1; i < q; i++) ans += lower_bound(v[i].begin(), v[i].end(), c - add[i]) - v[i].begin();
    return ans;
}

int main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    int t = sqrt(n);
    for(int i = 1; i <= t; i++) {
        L[i] = sqrt(n) * (i - 1) + 1;
        R[i] = sqrt(n) * i;
    }
    if(R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
    for(int i = 1; i <= t; i++) {
        for(int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            v[pos[j]].push_back(a[j]);
        }
    }
    for(int i = 1; i <= t; i++) sort(v[i].begin(), v[i].end());
    m = n;
    while(m--) {
        int opt = read(), l = read(), r = read(), c = read();
        if(opt == 0) change(l, r, c);
        else cout << ask(l, r, c * c) << '\n';
    }
    return 0;
}

LOJ #6278. 数列分块入门 2

原文：https://www.cnblogs.com/loceaner/p/12210381.html