LOJ 分块入门2

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 5e4 + 10, M = 1e3 + 10;
int n;
int v[M][M];
int id[N], len;
int a[N], tag[M];
void modify(int l, int r, int x) {
    int lid = id[l], rid = id[r];

    if (lid == rid) {
        for (int i = l; i <= r; i++)
            a[i] += x, v[lid][i - lid * len + 1] += x;

        sort(v[lid] + 1, v[lid] + len + 1);
        return ;
    }

    for (int i = l; i <= lid * len; i++)
        a[i] += x, v[lid][i - lid * len + 1] += x;

    for (int i = (rid - 1) * len + 1; i <= r; i++)
        a[i] += x, v[rid][i - (rid - 1) * len] += x;

    for (int i = lid + 1; i < rid; i++)
        tag[i] += x;

    sort(v[lid] + 1, v[lid] + len + 1), sort(v[rid] + 1, v[rid] + len + 1);
}
int query(int l, int r, int x) {
    int lid = id[l], rid = id[r];
    int ans = 0;

    if (lid == rid) {
        for (int i = l; i <= r; i++)
            ans += ((a[i] + tag[lid]) < x);

        return ans;
    }

    for (int i = l; i <= lid * len; i++)
        ans += ((a[i] + tag[lid]) < x);

    for (int i = (rid - 1) * len + 1; i <= r; i++)
        ans += ((a[i] + tag[rid]) < x);

    for (int i = lid + 1; i < rid; i++)
        ans += lower_bound(v[i] + 1, v[i] + len + 1, x - tag[i]) - v[i] - 1;

    return ans;
}
signed main() {
    cin >> n;
    len = sqrt(n);

    for (int i = 1; i <= n; i++)
        cin >> a[i], id[i] = (i - 1) / len + 1, v[id[i]][i - id[i] * len + 1] = a[i];

    for (int i = 1; i <= (n - 1) / len + 1; i++)
        sort(v[i] + 1, v[i] + len + 1);

    for (int i = 1; i <= n; i++) {
        int opt, l, r, x;
        cin >> opt >> l >> r >> x;

        if (!opt)
            modify(l, r, x);
        else
            cout << query(l, r, x * x) << endl;
    }

    return 0;
}/*
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2

1 2 2 3
2 3 3 3

*/