P2801 教主的魔法 (分块）

喜欢ヅ旅行 2021-10-19 04:48 262阅读 0赞

[题目传送][Link 1]

长度为\\(n(n\\le 1000000)\\)的数组，\\(q(q\\le 3000)\\) 次操作。修改操作即将某个区间的值增加某个不大于1000的值，查询操作即查询某个区间比C大于等于的数有多少个

我们用一个数组\\(add\[i\]\\)来表示第\\(i\\)段增量，如果查询区间完全包含第\\(i\\)段，那么就相当于是在原数组中查找大于等于\\(C-add\[i\]\\)的数，怎么找？排序后二分找。而对于左右不完整的那部分，直接暴力查询就可以。

对于修改操作。整段的直接增加增量，不完整的直接修改原数组，然后重新排序即可。

假设一段长度为\\(t\\) 则复杂度\\(O(C(t+\{nlog(t)\\over t\}))\\)

#include <bits/stdc++.h> using namespace std; const int N = 1000010; int a[N],b[N],be[N],L[N],R[N],add[N]; char op[3]; int l,r,x; int n,m; void change(int l,int r,int x){ int p = be[l],q = be[r]; if(p == q){ for(int i=l;i<=r;i++)a[i] += x; for(int i=L[p];i<=R[p];i++)b[i] = a[i]; sort(b+L[p],b+R[p]+1); } else{ for(int i=p+1;i<=q-1;i++)add[i] += x; for(int i=l;i<=R[p];i++)a[i] += x; for(int i=L[p];i<=R[p];i++)b[i] = a[i]; sort(b+L[p],b+R[p]+1); for(int i=L[q];i<=r;i++)a[i] += x; for(int i=L[q];i<=R[q];i++)b[i] = a[i]; sort(b+L[q],b+R[q]+1); } } void solve(int l,int r,int x){ int res = 0; int p = be[l],q = be[r]; if(p == q){ for(int i=l;i<=r;i++){ if(a[i] + add[p] >= x)res++; } printf("%d\n",res);return; } else{ for(int i=p+1;i<=q-1;i++){ res += (R[i]-L[i]+1) - (lower_bound(b+L[i],b+R[i]+1,x-add[i]) - (b+L[i])); } for(int i=l;i<=R[p];i++)if(a[i] + add[p] >= x)res++; for(int i=L[q];i<=r;i++)if(a[i] + add[q] >= x)res++; printf("%d\n",res);return ; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i] = a[i]; int t = sqrt(n); for(int i=1;i<=t;i++){ L[i] = (i - 1) * t + 1; R[i] = i * t; } if(R[t] < n)t++,L[t] = R[t-1] + 1,R[t] = n; for(int i=1;i<=t;i++)for(int j=L[i];j<=R[i];j++)be[j] = i; for(int i=1;i<=t;i++){ sort(b+L[i],b+R[i]+1); } while(m--){ scanf("%s%d%d%d",op,&l,&r,&x); if(op[0] == 'M')change(l,r,x); else solve(l,r,x); } return 0; }

转载于:https://www.cnblogs.com/1625--H/p/11329576.html

[Link 1]: https://www.luogu.org/problem/P2801