【luogu P2801】 教主的魔法
传送门：https://www.luogu.org/problemnew/show/P2801
这道题刚看到的时候感觉就是线段树的两种操作嘛，维护一棵线段树就好了。然并卵我忘记线段树怎么写了。然后就想到打暴力水过数据点，就花了十来分钟打暴力，搞过了样例。但是。。。。最后得了0分，其他巨佬同样写了暴力拿到了100分（果然是我太菜了）。
后来改题的时候看了眼题解，说是要用分块（早已遗忘了分块），然后就花了挺长时间写了分块，在洛谷上提交还是tle了一个点，但是算了一下复杂度是O(msqrt(nlogn))，并没有超数据范围（咱也不知道，咱也不敢问QAQ）最后开了o2，那个点就过了（玄学）。。。
#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<queue> #include<vector> #include<cstring> typedef long long ll; using namespace std; const int maxn = 1000005; int n, m, block; int v[maxn], bel[maxn], tag[maxn]; vector<int>vec[10005]; void reset(int x) { vec[x].clear(); for(int i = (x - 1) * block + 1; i <= min(x * block,n); i++) vec[x].push_back(v[i]); sort(vec[x].begin(),vec[x].end()); } ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void add(int a, int b, int c) { for(int i = a; i <= min(bel[a] * block,b); i++) v[i] += c; reset(bel[a]); if(bel[a] != bel[b]) { for(int i = (bel[b] - 1) * block + 1; i <= b; i++) v[i] += c; reset(bel[b]); } for(int i = bel[a]+ 1; i <= bel[b] - 1; i++) tag[i] += c; } int query(int a, int b, int c) { int ans = 0; for(int i = a; i <= min(bel[a] * block,b); i++) if(v[i] + tag[bel[a]] < c) ans++; if(bel[a] != bel[b]) { for(int i = (bel[b] - 1) * block + 1; i <= b; i++) if(v[i] + tag[bel[b]] < c) ans++; } for(int i = bel[a] + 1; i <= bel[b] - 1; i++) { int x = c - tag[i]; ans += lower_bound(vec[i].begin(),vec[i].end(),x) - vec[i].begin(); } return ans; } int main() { n = read(), m = read(); block = sqrt(n); for(int i = 1; i <= n; i++) v[i] = read(); for(int i = 1; i <= n; i++) { bel[i] = (i - 1) / block + 1; vec[bel[i]].push_back(v[i]); } for(int i = 1; i <= bel[n]; i++) sort(vec[i].begin(),vec[i].end()); for(int i = 1; i <= m; i++) { char f[5]; scanf("%s", f); int a = read(), b = read(), c = read(); if(f[0] == 'M') add(a,b,c); else printf("%d ",b - a + 1 - query(a,b,c)); } return 0; }