link

分块裸题，但令人不解的是，当 $block = \sqrt{n}$ 时会被卡，$block = \sqrt{n}+1$ 就能过。

可是 $block$ 不是只会影响时间复杂度的吗，为什么还会影响代码正确性？

有事踢我

具体代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#define min(a,b) ((a)<(b)?(a):(b))
#define int long long
#define pb emplace_back
using namespace std;
const int N=1e6+7;
char c; int n,q,l,r,k;
int fr[N],a[N],up[N],sum[N],bl;
vector<int> kuai[N];
inline void init(){
  bl=(int)sqrt(n)+1;//如果是sqrt(n)，就会 WA 80
  for(int i=1,la=bl,cnt=1;i<=n;i++){
    fr[i]=cnt;
    if(i==la) la+=bl,cnt++;
  }
}
inline void solve_kuai(int x){
  sort(kuai[x].begin(),kuai[x].end(),
    [](int &a,int &b){return a>b;});
}
inline void change(int l,int r,int k){
  kuai[fr[l]].clear();
  for(int i=l;i<=min(bl*fr[l],r);i++)
    a[i]+=k,sum[i]+=k,kuai[fr[l]].pb(a[i]);
  solve_kuai(fr[l]);
  if(fr[l]!=fr[r]){
    kuai[fr[r]].clear();
    for(int i=bl*(fr[r]-1)+1;i<=r;i++)
      a[i]+=k,sum[i]+=k,kuai[fr[r]].pb(a[i]);
    solve_kuai(fr[r]);
  }
  for(int i=fr[l]+1;i<fr[r];i++)
    sum[i]+=bl*k,up[i]+=k;
}
inline int query(int l,int r,int k){
  int ret=0;
  for(int i=l;i<=min(bl*fr[l],r);i++)
    if(a[i]+up[fr[i]]>=k) ret++;
  if(fr[l]!=fr[r])
    for(int i=bl*(fr[r]-1)+1;i<=r;i++)
      if(a[i]+up[fr[i]]>=k) ret++;
  for(int i=fr[l]+1;i<fr[r];i++){
    int l=0,r=kuai[i].size()-1,mid;
    while(l<r){
      mid=(l+r+1)>>1;
      if(kuai[i][mid]+up[i]>=k) l=mid;
      else r=mid-1;
    }
    ret+=l+1;
  }
  return ret;
}
signed main(){
  ios::sync_with_stdio(false),cin.tie(0);
  cin>>n>>q;
  init();
  for(int i=1;i<=n;i++)
    cin>>a[i],sum[fr[i]]+=a[i],
      kuai[fr[i]].pb(a[i]);
  for(int i=1;!kuai[i].empty();i++)
    solve_kuai(i);
  while(q--){
    cin>>c;
    if(c=='A')
      cin>>l>>r>>k,cout<<query(l,r,k)<<'\n';
    if(c=='M')
      cin>>l>>r>>k,change(l,r,k); 
  }
  return 0;
}