套路的根号分治啊

我们设置一个值\(S\)

对于\(S\leq x\)的操作，我们直接暴力修改，显然这样只会修改\(\frac{n}{S}\)次，所以我们需要一个能够\(O(1)\)修改的数据结构，自然是首选分块

对于\(S>x\)的操作，我们对于每一个\(x\)维护一个块，我们维护这个块的前缀和就好了，复杂度是\(O(S)\)的

查询的时候先用分块查一下区间和，复杂度\(O(S+\frac{n}{S})\)，之后对于每一个\(x<S\)的块我们单独\(O(1)\)求一下，复杂度是\(O(S)\)

理论上自然是\(S=\sqrt{n}\)的时候取到了最优的复杂度，但是我们根据一些奇怪的常数原因，可以魔改一波块大小

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define re register#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int maxn=2e5+5;const int mod=1e9+7;int n,m,sz;int pr[500][500],sum[500];int pre[maxn],id[maxn],l[5000];inline int qm(int a) {return a>=mod?a-mod:a;}struct Block {    int a[maxn],tag[5000];    inline void change(int pos,int v) {        a[pos]=qm(a[pos]+v);        tag[id[pos]]=qm(tag[id[pos]]+v);    }    inline int ask(int x) {        int now=0;        for(re int i=1;i
         
          =sz) {while(y<=n) B.change(y,v),y+=x;continue;} sum[x]=(sum[x]+v)%mod; for(re int i=y;i<=x;i++) pr[x][i]=qm(pr[x][i]+v); } } return 0;}