之前學過 莫隊 算法，其運用了分塊思想；但是我居然是第一次寫純種的分塊題目。

題意

給你一個長度為 $n$ 的序列 $a$（一開始 $?a_i\in [1,1000]$）。要求執行 $q$ 次操作，操作有兩種，每次形如 $op,l,r,w/c$：

• $op$ 為 $\mathrm{M}$，將 $a_l,a_{l+1},?,a_r$ 分別加上 $w$；
• $op$ 為 $\mathrm{A}$，查詢 $a_l,a_{l+1},?,a_r$ 中，有多少個數大于 $c$。

$n\le 10^6,q\le 3000,w\le 1000,c\le 10^9$

思路

主席樹？是我早就不會打的。

如果我們把它變成一道分塊練習題呢？

考慮對序列 $a$ 分塊，對于每一塊內，使用輔助數組 $b$ 以保證塊內數有序。不妨設 $b{l}_t,b{r}_t$ 表示塊 $t$ 的左右端點，$be{l}_i$ 表示下標 $i$ 所在的塊的編號。

對于修改操作 $l,r,w$，如果 $?t,b{l}_t\le l<r\le b{r}_t$，即同一塊，$t=be{l}_l=be{l}_r$，如果其不在左右端點上，那么塊內的排序性質就會被破壞；反之如果它們不在同一塊，說明它們中間跨過了若干塊整塊的區間，我們發現被跨過的區間仍然保持有序。

那么我們得到一個初步的修改方法：

• 設左右端點所在的塊分別在 $lb=be{l}_l,rb=be{l}_r$，如果 $lb=rb$，就塊內暴力加 $w$ 并快排更新；
• 否則即 $lb<rb$，我們發現塊 $lb+1～rb?1$ 內仍然有序，那么不妨想線段樹引入懶惰標記一樣，我們搞一個加法標記，把整一塊 $t$ 內所有元素同時加的數，用 $ta{g}_t$ 記錄下來，等到查詢時再處理；只強制更新更新 $l～b{r}_{lb}$ 和 $b{l}_{rb}～r$ 的數據和塊 $lb,rb$。

這樣子大大減少了排序的次數，每次修改操作頂多 $2\times {\log }_{2}n$，瓶頸在于快排。

void modify(ll t)//更新t塊內數據
{for(int i=bl[t];i<=br[t];i++)b[i]=a[i];sort(b+bl[t],b+br[t]+1);
}
void add(ll ql,ll qr,ll x)//l,r,w
{ll lb=bel[ql],rb=bel[qr];//左右端所在塊if(lb==rb)//同一塊{for(int i=ql;i<=qr;i++)a[i]+=x;modify(lb);return;}//不同塊for(int i=ql;i<=br[lb];i++)a[i]+=x;for(int i=bl[rb];i<=qr;i++)a[i]+=x;modify(lb);modify(rb);for(int i=lb+1;i<rb;i++)//lb+1~rb-1塊打標記tag[i]+=x;
}

接下來就是查詢，其實就和修改所運用的思想差不多了。同樣討論 $l,r$ 在或不在同一塊的兩種情況。如果同一塊就直接 $ql～qr$ 掃過去（倒著枚舉提前 break 凹時間也行、甚至乎二分，反正塊上數組 $b$ 就是有序的），不同塊就搜左右兩邊 $l～b{r}_{rb}$ 和 $b{l}_{rb}～r$（這里不能二分，因為原數組并非有序），至于中間的整塊整塊的，按塊二分就好。

ll find(ll ql,ll qr,ll x)
{ll l=ql,r=qr;while(l<=r){ll mid=(l+r)>>1;if(b[mid]<x)l=mid+1;else r=mid-1;}return qr-l+1;
}
ll query(ll ql,ll qr,ll x)
{ll ret=0,lb=bel[ql],rb=bel[qr];if(lb==rb){ret+=find(ql,qr,x-tag[lb]);return ret;}for(int i=ql;i<=br[lb];i++)if(a[i]+tag[lb]>=x)ret++;for(int i=bl[rb];i<=qr;i++)if(a[i]+tag[rb]>=x)ret++;for(int i=lb+1;i<rb;i++)ret+=find(bl[i],br[i],x-tag[i]);return ret;
}

塊長 $\sqrt{n}$，修改一次是塊長+塊內排序，查詢是 塊內二分 或 塊長掃左右端+塊數*塊內二分，時間復雜度 $\Theta (m\sqrt{n}+m\sqrt{n}{\log }_2\sqrt{n})=\Theta (m\sqrt{n}{\log }_2\sqrt{n})$。

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+9;
ll n,q,a[N];
ll tag[N];//加法標記
ll bSize,cnt_b,bel[N],bl[N],br[N],b[N];
void init()
{bSize=sqrt(n);cnt_b=n/bSize;if(n%bSize)cnt_b++;for(int i=1;i<=n;i++){bel[i]=(i-1)/bSize+1;b[i]=a[i];}for(int i=1;i<=cnt_b;i++){bl[i]=(i-1)*bSize+1;br[i]=i*bSize;}br[cnt_b]=n;for(int i=1;i<=cnt_b;i++)sort(b+bl[i],b+br[i]+1);
}
void modify(ll t)//更新t塊內數據
{for(int i=bl[t];i<=br[t];i++)b[i]=a[i];sort(b+bl[t],b+br[t]+1);
}
void add(ll ql,ll qr,ll x)
{ll lb=bel[ql],rb=bel[qr];//左右端所在塊if(lb==rb)//同一塊{for(int i=ql;i<=qr;i++)a[i]+=x;modify(lb);return;}//不同塊for(int i=ql;i<=br[lb];i++)a[i]+=x;for(int i=bl[rb];i<=qr;i++)a[i]+=x;modify(lb);modify(rb);for(int i=lb+1;i<rb;i++)//lb+1~rb-1塊打標記tag[i]+=x;
}
ll find(ll ql,ll qr,ll x)
{ll l=ql,r=qr;while(l<=r){ll mid=(l+r)>>1;if(b[mid]<x)l=mid+1;else r=mid-1;}return qr-l+1;
}
ll query(ll ql,ll qr,ll x)
{ll ret=0,lb=bel[ql],rb=bel[qr];if(lb==rb){ret+=find(ql,qr,x-tag[lb]);return ret;}for(int i=ql;i<=br[lb];i++)if(a[i]+tag[lb]>=x)ret++;for(int i=bl[rb];i<=qr;i++)if(a[i]+tag[rb]>=x)ret++;for(int i=lb+1;i<rb;i++)ret+=find(bl[i],br[i],x-tag[i]);return ret;
}
int main()
{scanf("%lld%lld",&n,&q);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);init();while(q--){char op;ll l,r,x;cin>>op;scanf("%lld%lld%lld",&l,&r,&x);if(op=='M')add(l,r,x);else printf("%lld\n",query(l,r,x));}return 0;
}