/category/fk/ /archives/76/ 2016-11-15T15:39:00+08:00 ###Description 教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。 每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高） CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。 WD巨懒，于是他把这个回答的任务交给了你。 ###Input 第1行为两个整数N、Q。Q为问题数与教主的施法数总和。 第2行有N个正整数，第i个数代表第i个英雄的身高。 第3到第Q+2行每行有一个操作： （1）若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。 （2）若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。 ###Output 对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。 ###Sample Input 5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4 ###Sample Output 2 3 ###HINT 【输入输出样例说明】 原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。 【数据范围】 对30%的数据，N≤1000，Q≤1000。 对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。 ###Solution 分块可以做，然而花式分块更快。。 在每个操作的端点处划分，共分为最多4Q块，那么每个操作必会在一段连续块上 处理每块时，遍历所有包含它的操作，若为修改，则delta+=w，若为查询，则记录c-delta，然后将询问按c-delta排序 之后遍历该块中的数，二分+差分维护贡献 时间复杂度$$O(Q^2logQ+NlogQ)$$ ##Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) int n,m,h[1000001],q[3000][4],bl[12010],ans[3000],tmp[3000]; struct yjq { int x,id; inline bool operator 1; else l=(l+r)>>1; } tmp[l]++; } for(int j=fm-1,t=0;j>=0;j--) { t+=tmp[j]; ans[f[j].id]+=t; } } for(int i=0;i