「题解」教主的魔法

教主最近学会了一种神奇的魔法，能够使人长高……

一 题目

原题链接

描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、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行每行有一个操作：
（1） 若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
（2） 若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

输出

对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。

---

二 题解

元素的区间排名问题。使用分块解决，不过相比于模板问题，有一个地方需要稍微改动一下。

因为题目中让求“有多少英雄的身高大于等于C”，但是模板中lower_bound()找出来的是小于C的元素个数，假设这个值为$k$，那么在整块累加答案的时候应该加上的是$bcnt-k$（$bcnt$为块的大小同时也是块数）。
但是还需要注意一个细节：最后一个块的大小不一定恰好等于块数。所以需要特判（详见代码）。

最后一个点是这题卡vector，会T一个点，如果用普通数组就没有问题。但是我懒得改代码了，所以吸O2过了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

#define LL long long
const int CN=1e6+5;
const int CB=1e3+3;
 
//v define
int n,q;
LL hg[CN];

int sqr(int x){
    for(int k=1;;k++)
        if(k*k > x) return k;
}

//hzwer tql
int bel[CN],bcnt=0;
LL tag[CB];
vector<int>s[CB];

void updata(int pos){
    s[pos].clear();
    for(int i=(pos-1)*bcnt+1; i<=pos*bcnt; i++)
        s[pos].push_back(hg[pos]);
    sort(s[pos].begin(),s[pos].end());
}
void build(){
    bcnt=sqr(n);
    for(int i=1;i<=n;i++){
        bel[i] = (i-1)/bcnt+1;
        s[bel[i]].push_back(hg[i]);
    }
    for(int i=1;i<=bcnt;i++)
        sort(s[i].begin(),s[i].end());
}
void modify(int l,int r,LL c){
    for(int i=l; i<=min(bel[l]*bcnt, r); i++)
        hg[i] += c;
    updata(bel[l]);
    if(bel[l] != bel[r]){
        for(int i=(bel[r]-1)*bcnt+1; i<=r; i++)
            hg[i] += c;
        updata(bel[r]);
    }
    for(int i=bel[l]+1; i<bel[r]; i++)
        tag[i] += c;
}
LL query(int l,int r,LL c){
    LL ans=0;
    for(int i=l; i<=min(bel[l]*bcnt, r); i++)
        if(hg[i]+tag[bel[i]] >= c)
            ans++;
    if(bel[l] != bel[r])
        for(int i=(bel[r]-1)*bcnt+1; i<=r; i++)
            if(hg[i]+tag[bel[i]] >= c)
                ans++;
    for(int i=bel[l]+1; i<bel[r]; i++){
        int x=c-tag[i];
        vector<int>::iterator it=lower_bound(s[i].begin(),s[i].end(),x);
        int sum=bcnt;
        if(i == bcnt) //最后一个块可能不为整 
            sum = min(n-((i-1)*bcnt), bcnt);
        ans += sum-(it-s[i].begin());
    }
    return ans;
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%lld",&hg[i]);
    build();
    
    while(q--){
        char m;
        int l,r;
        LL c;
        cin>>m;
        scanf("%d%d%lld",&l,&r,&c);
        if(m == 'M') modify(l,r,c);
        if(m == 'A') printf("%lld\n",query(l,r,c));
    }
    
    return 0;
}