题意：长度为N的区间，有N次操作，每次操作是区间加上一个数，以及查询区间小于x的数的个数。
直接分块维护数列，然后对于那些不完整块，需要额外加，于是加完之后sort一下即可。
5 1 1 1 1 1 1 1 5 2 0 1 5 3 1 1 5 2 0 1 5 1 1 2 3 3 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define eps 1e-6 #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 5e4 + 7; int N, Q, len, s; struct node { int val, id; node(int a=0, int b=0):val(a), id(b) {} friend bool operator < (node e1, node e2) { return e1.val < e2.val; } }a[maxN]; struct K { int l, r, sum; K(int a=0, int b=0, int c=0):l(a), r(b), sum(c) {} }t[maxN]; inline void update(int ql, int qr, int w) { int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { for(int i=t[st].l; i<=t[st].r; i++) { if(a[i].id >= ql && a[i].id <= qr) a[i].val += w; } sort(a + t[st].l, a + t[st].r + 1); return; } for(int i=t[st].l; i<=t[st].r; i++) { if(a[i].id >= ql && a[i].id <= qr) a[i].val += w; } sort(a + t[st].l, a + t[st].r + 1); for(int i=t[ed].l; i<=t[ed].r; i++) { if(a[i].id >= ql && a[i].id <= qr) a[i].val += w; } sort(a + t[ed].l, a + t[ed].r + 1); for(int i=st + 1; i <= ed - 1; i++) t[i].sum += w; } inline int query(int ql, int qr, ll x) { int ans = 0, add; ll tmp; int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { tmp = x - t[st].sum; for(int i=t[st].l; i<=t[st].r; i++) { if(a[i].val >= tmp) break; if(a[i].id >= ql && a[i].id <= qr) ans++; } return ans; } tmp = x - t[st].sum; for(int i=t[st].l; i<=t[st].r; i++) { if(a[i].val >= tmp) break; if(a[i].id >= ql && a[i].id <= qr) ans++; } tmp = x - t[ed].sum; for(int i=t[ed].l; i<=t[ed].r; i++) { if(a[i].val >= tmp) break; if(a[i].id >= ql && a[i].id <= qr) ans++; } node now = node((int)tmp, 0); for(int i=st + 1; i <= ed - 1; i++) { tmp = x - t[i].sum; now = node((int)tmp, 0); add = (int)(lower_bound(a + t[i].l, a + t[i].r + 1, now) - a - t[i].l); ans += add; } return ans; } int main() { scanf("%d", &N); Q = N; len = sqrt(N); s = N / len + (N % len == 0 ? 0 : 1); for(int i=1; i<=N; i++) { scanf("%d", &a[i].val); a[i].id = i; } for(int i=1; i<=s; i++) { t[i].l = (i - 1) * len + 1; t[i].r = i * len; } t[s].r = N; for(int i=1; i<=s; i++) sort(a + t[i].l, a + t[i].r + 1); int op, l, r; ll c; while(Q--) { scanf("%d%d%d%lld", &op, &l, &r, &c); if(op) { printf("%d\n", query(l, r, c * c)); } else { update(l, r, (int)c); } } return 0; }
