萌新刚学分块0.01ms，求助站外题

Register_int @ 2022-07-25 08:34:50

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e4 + 10;
const int MAXM = 240;

int a[MAXN], t[MAXN];

int len, tot;

int lp[MAXM], rp[MAXM], pos[MAXN];

ll add[MAXM];

inline 
void build(int n) {
    len = sqrt(n);
    tot = n / len + !!(n % len);
    for (int i = 1; i <= tot; i++) {
        lp[i] = (i - 1) * len + 1;
        rp[i] = i * len;
    }
    rp[tot] = n;
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    for (int i = 1; i <= n; i++) t[i] = a[i];
    for (int i = 1; i <= tot; i++) sort(t + lp[i], t + rp[i] + 1);
}

inline 
void change(int l, int r, int k) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += k;
        return ;
    }
    for (int i = p + 1; i < q; i++) add[i] += k;
    for (int i = l; i <= rp[p]; i++) a[i] += k;
    for (int i = lp[q]; i <= r; i++) a[i] += k;
}

inline 
int query(int l, int r, int k) {
    int p = pos[l], q = pos[r];
    int ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) {
            if (a[i] + add[p] < k) ans++;
        }
        return ans;
    }
    for (int i = p + 1; i < q; i++) {
        ans += upper_bound(t + lp[i], t + rp[p] + 1, k - add[i]) - t - lp[i];
    }
    for (int i = l; i <= rp[p]; i++) {
        if (a[i] + add[p] < k) ans++;
    }
    for (int i = lp[q]; i <= r; i++) {
        if (a[i] + add[q] < k) ans++;
    }
    return ans;
}

int n;

int opt, l, r, c;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &opt, &l, &r, &c);
        if (opt) printf("%d\n", query(l, r, c * c));
        else change(l, r, c);
    }
}

by TernaryTree @ 2022-07-25 08:35:17

cjld，太卷了

by d0j1a_1701 @ 2022-07-25 08:45:38

cjld，太卷了

by sszcdjr @ 2022-07-25 09:18:59

LOJ Accepted：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e4 + 10;
const int MAXM = 240;

int a[MAXN], t[MAXN];

int len, tot;

int lp[MAXM], rp[MAXM], pos[MAXN];

ll add[MAXM];

inline 
void build(int n) {
    len = sqrt(n);
    tot = n / len + !!(n % len);
    for (int i = 1; i <= tot; i++) {
        lp[i] = (i - 1) * len + 1;
        rp[i] = i * len;
    }
    rp[tot] = n;
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    for (int i = 1; i <= n; i++) t[i] = a[i];
    for (int i = 1; i <= tot; i++) sort(t + lp[i], t + rp[i] + 1);
}

inline 
void change(int l, int r, int k) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += k;
        for(int i=lp[p];i<=rp[p];i++) t[i]=a[i];
        sort(t+lp[p],t+rp[p]+1);
        return ;
    }
    for (int i = p + 1; i < q; i++) add[i] += k;
    for (int i = l; i <= rp[p]; i++) a[i] += k;
    for (int i = lp[q]; i <= r; i++) a[i] += k;
    for(int i=lp[p];i<=rp[p];i++) t[i]=a[i];
    sort(t+lp[p],t+rp[p]+1);
    for(int i=lp[q];i<=rp[q];i++) t[i]=a[i];
    sort(t+lp[q],t+rp[q]+1);
}

inline 
int query(int l, int r, int k) {
    int p = pos[l], q = pos[r];
    int ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) {
            if (a[i] + add[p] < k) ans++;
        }
        return ans;
    }
    for (int i = p + 1; i < q; i++) {
        ans += lower_bound(t + lp[i], t + rp[i] + 1, k - add[i]) - t - lp[i];
    }
    for (int i = l; i <= rp[p]; i++) {
        if (a[i] + add[p] < k) ans++;
    }
    for (int i = lp[q]; i <= r; i++) {
        if (a[i] + add[q] < k) ans++;
    }
    return ans;
}

int n;

int opt, l, r, c;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &opt, &l, &r, &c);
        if (opt) printf("%d\n", query(l, r, c * c));
        else change(l, r, c);
    }
}

按自己码风改的，可能有点丑

问题一：修改后需要及时更新 t[i]。

问题二：lower_bound 而不是 upper_bound

另外楼上两位，这里不是灌水区。