mxqz 分块40pts

Dream_weavers @ 2022-08-09 11:49:38

by Cerisier @ 2022-08-09 11:55:03

@Dream_weavers 代码？我看不见，你好像没公开代码

by Dream_weavers @ 2022-08-09 11:55:56

@Cerisier 我放云剪贴板了

by Cerisier @ 2022-08-09 11:58:28

嗷嗷嗷

by Cerisier @ 2022-08-09 12:00:23

@Dream_weavers 你的t怎么是个数组，应该每个块都有一个吧

by Cerisier @ 2022-08-09 12:00:45

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

const int maxn = 1e6 + 10;

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch))
        X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
inline void write(int x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

struct block {
    int st, ed;
    int tag;
    vector<int> nums;
};
block b[maxn];
int blocksize, blockamt;
int bel[maxn];

int n, q;
int a[maxn];

void init() {
    blocksize = sqrt(n), blockamt = n / blocksize;
    for (int i = 1; i <= blockamt; i++) {
        b[i].st = b[i - 1].ed + 1;
        b[i].ed = b[i].st + blocksize - 1;
    }
    b[blockamt].ed = n;
    for (int i = 1; i <= blockamt; i++) {
        for (int j = b[i].st; j <= b[i].ed; j++) {
            bel[j] = i;
            b[i].nums.push_back(a[j]);
        }
        b[i].tag = 0;
        sort(b[i].nums.begin(), b[i].nums.end());
    }
}

void resetnums(int x) {
    b[x].nums.clear();
    for (int i = b[x].st; i <= b[x].ed; i++) {
        b[x].nums.push_back(a[i]);
    }
    sort(b[x].nums.begin(), b[x].nums.end());
    return;
}

void update(int l, int r, int v) {
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {
            a[i] += v;
        }
        resetnums(bel[l]);
    } else {
        for (int i = l; i <= b[bel[l]].ed; i++) {
            a[i] += v;
        }
        resetnums(bel[l]);
        for (int i = b[bel[r]].st; i <= r; i++) {
            a[i] += v;
        }
        resetnums(bel[r]);
        for (int i = bel[l] + 1; i < bel[r]; i++) {
            b[i].tag += v;
        }
    }
}
int query(int l, int r, int v) {
    int ans = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {
            if (a[i] + b[bel[i]].tag < v) {
                ans++;
            }
        }
    } else {
        for (int i = l; i <= b[bel[l]].ed; i++) {
            if (a[i] + b[bel[i]].tag < v) {
                ans++;
            }
        }
        for (int i = b[bel[r]].st; i <= r; i++) {
            if (a[i] + b[bel[i]].tag < v) {
                ans++;
            }
        }
        for (int i = bel[l] + 1; i < bel[r]; i++) {
            if (b[i].nums[0] >= v)
                continue;
            auto it =
                lower_bound(b[i].nums.begin(), b[i].nums.end(), v - b[i].tag);
            ans += (it - b[i].nums.begin());
        }
    }
    return (r - l + 1) - ans;
}

int main() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    init();
    while (q--) {
        char ch;
        int l, r, v;
        cin >> ch;
        l = read(), r = read(), v = read();
        if (ch == 'M') {
            update(l, r, v);
        }
        if (ch == 'A') {
            write(query(l, r, v));
            putchar('\n');
        }
    }
    return 0;
}

by Dream_weavers @ 2022-08-09 12:03:41

@Cerisier 我再去看看，谢谢

by Eric_cai @ 2022-08-09 13:40:25

@Dream_weavers 你build完了之后是不是每个块都要先sort一下

by youdu666 @ 2022-08-09 22:08:41

楼上说得对（还有一件事，为什么大家都在今天学分块）