思路：正常分块，然后多开一个数组 b 复制 a，但是不同的是 b 数组中的每一块都是有序的。每一次更新之后，都需要对 b 中的改变的块都重新排序（若是完整的块就不需要），然后查询的时候，不完整的块暴力找，完整的块用lower_bound，注意lower_bound的是 c - tag[i]
Code：
#include<bits/stdc++.h> #define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl #define pii pair<int,int> #define clr(a,b) memset((a),b,sizeof(a)) #define rep(i,a,b) for(int i = a;i < b;i ++) #define pb push_back #define MP make_pair #define LL long long #define ull unsigned LL #define ls i << 1 #define rs (i << 1) + 1 #define fi first #define se second #define CLR(a) while(!(a).empty()) a.pop() using namespace std; const int maxn = 5e4 + 10; int l[maxn],r[maxn],num,n; int belong[maxn],block; int a[maxn],b[maxn],tag[maxn]; void build(){ block = sqrt(n); num = n / block; if(n % block) ++ num; rep(i,1,num + 1){ l[i] = (i - 1) * block + 1; r[i] = i * block; } r[num] = n; rep(i,1,n + 1) belong[i] = (i - 1) / block + 1; } void ReSort(int id){ int x = l[id],y = r[id]; for(int i = x;i <= y;++ i){ a[i] += tag[id]; b[i] = a[i]; } sort(b + x,b + y + 1); tag[id] = 0; } void update(int x,int y,int c){ if(belong[x] == belong[y]){ for(int i = x;i <= y;++ i) a[i] += c; ReSort(belong[x]); return ; } for(int i = x;i <= r[belong[x]];++ i) a[i] += c; ReSort(belong[x]); for(int i = belong[x] + 1;i < belong[y];++ i) tag[i] += c; for(int i = l[belong[y]];i <= y;++ i) a[i] += c; ReSort(belong[y]); } int query(int x,int y,int c){ int ans = 0; if(belong[x] == belong[y]){ for(int i = x;i <= y;++ i) if(a[i] + tag[belong[i]] < c) ++ ans; return ans; } for(int i = x;i <= r[belong[x]];++ i) if(a[i] + tag[belong[x]] < c) ++ ans; for(int i = belong[x] + 1;i < belong[y];++ i){ int pos = lower_bound(b + l[i],b + r[i] + 1,c - tag[i]) - b - l[i]; ans += pos; } for(int i = l[belong[y]];i <= y;++ i) if(a[i] + tag[belong[y]] < c) ++ ans; return ans; } int main() { scanf("%d",&n); rep(i,1,n + 1) scanf("%d",&a[i]); build(); rep(i,1,num + 1) ReSort(i); while(n --){ int op,x,y,c; scanf("%d%d%d%d",&op,&x,&y,&c); if(!op) update(x,y,c); else printf("%d\n",query(x,y,c * c)); } return 0; }
