P2801 教主的魔法
题目描述
教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 \(N\) 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 \(1, 2, \ldots, N\)。
每个人的身高一开始都是不超过 \(1000\) 的正整数。教主的魔法每次可以把闭区间 \([L, R]\)（\(1≤L≤R≤N\)）内的英雄的身高全部加上一个整数 \(W\)。（虽然 \(L=R\) 时并不符合区间的书写规范，但我们可以认为是单独增加第 \(L(R)\) 个英雄的身高）
CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 \([L, R]\) 内有多少英雄身高大于等于 \(C\)，以验证教主的魔法是否真的有效。
WD 巨懒，于是他把这个回答的任务交给了你。
输入格式
第 \(1\) 行为两个整数 \(N, Q\)。\(Q\) 为问题数与教主的施法数总和。
第 \(2\) 行有 \(N\) 个正整数，第 \(i\) 个数代表第 \(i\) 个英雄的身高。
第 \(3\) 到第 \(Q+2\) 行每行有一个操作：
-
若第一个字母为
M，则紧接着有三个数字 \(L, R, W\)。表示对闭区间 \([L, R]\) 内所有英雄的身高加上 \(W\)。 -
若第一个字母为
A，则紧接着有三个数字 \(L, R, C\)。询问闭区间 \([L, R]\) 内有多少英雄的身高大于等于 \(C\)。
输出格式
对每个 A 询问输出一行，仅含一个整数，表示闭区间 \([L, R]\) 内身高大于等于 \(C\) 的英雄数。
【数据范围】
对于 \(100\%\) 的数据，\(N≤10^6\)，\(Q≤3000\)，\(1≤W≤1000\)，\(1≤C≤10^9\)。
Solution:
分块练手题，发现 \(Q≤3000\) 。意味着我们单次操作可以拥有 \(\sqrt n\times\log n\) 的复杂度的。
我们先对原序列分块，然后再对块内排序，得到数组 \(b_i\) 。每次更新时在整块上打 tag ，然后暴力重构散块。代价为 \(O(\sqrt n+ \sqrt n\times\log \sqrt n)\)
然后是询问：对于整块，直接在排序后的数组 \(b_i\) 上二分，然后在散块上暴力计数。时间复杂度为\(O(\sqrt n\times\log \sqrt n+\sqrt n)\)
总复杂度 \(O(Q\times\sqrt n\times\log)\) 然后这题就做完了。
Code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int B=1e3+5;
int len,cnt,n,m,ans;
int tag[N],l[B],r[B],belong[N],a[N],b[N];
void build()
{len=sqrt(n);cnt=n/len+((n%len!=0));for(int i=1;i<=n;i++){b[i]=a[i];belong[i]=(i-1)/len+1;}for(int i=1;i<=cnt;i++){l[i]=(i-1)*len+1,r[i]=i*len;}r[cnt]=n;for(int i=1;i<=cnt;i++)sort(b+l[i],b+r[i]+1);//[l,r)
}
void rebuild(int id)
{for(int i=l[id];i<=r[id];i++)b[i]=a[i];sort(b+l[id],b+r[id]+1);
}
void upd(int ll,int rr,int w)
{if(belong[ll]==belong[rr]){for(int i=ll;i<=rr;i++)a[i]+=w;rebuild(belong[ll]);return;}for(int i=ll;i<=r[belong[ll]];i++)a[i]+=w;rebuild(belong[ll]);for(int i=l[belong[rr]];i<=rr;i++)a[i]+=w;rebuild(belong[rr]);for(int i=belong[ll]+1;i<belong[rr];i++)tag[i]+=w;
}int calc(int id,int val)
{int ll=l[id],rr=r[id],mid;while(ll<=rr){mid=(ll+rr>>1);if(b[mid]<val)ll=mid+1;else rr=mid-1;}return r[id]-ll+1;
}int query(int ll,int rr,int val)
{int res=0;if(belong[ll]==belong[rr]){for(int i=ll;i<=rr;i++)res+=(a[i]+tag[belong[i]]>=val);return res;}for(int i=ll;i<=r[belong[ll]];i++)res+=(a[i]+tag[belong[i]]>=val);for(int i=l[belong[rr]];i<=rr;i++)res+=(a[i]+tag[belong[i]]>=val);for(int i=belong[ll]+1;i<belong[rr];i++)res+=calc(i,val-tag[i]);return res;
}char c[10];
void work()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&a[i]);build();for(int i=1,ll,rr,k;i<=m;i++){scanf("%s",c);scanf("%d%d%d",&ll,&rr,&k);if(c[0]=='M'){upd(ll,rr,k);}else{ans=query(ll,rr,k);printf("%d\n",ans);}}
}
int main()
{//freopen("P2801_1.in","r",stdin);//freopen("civilization.out","w",stdout);work();return 0;
}