1 /*此代码主要模仿了钟皓曦大佬的分块算法*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6  7 using namespace std; 8 const int MAXN = 1000005; 9 const int MAXP = 1005;10 int belong[MAXN],size[MAXP],sum[MAXP],add[MAXP];11 //    所属块        块的大小    块内计和  添加标记 12 int a[MAXN];13 int s,cnt;14 15 void init()16 {//初始化操作 17     s = sqrt(n);//每个块的大小 18     for(int i = 1;i <= n;i ++)19         belong[i] = (i-1)/s + 1;20     //每个数的所属块 21     cnt = belong[n];//块的数量 22     23     for(int i = 1;i <= cnt;i ++)24     {//记录块的大小 25         sum[i] = add[i] = 0;26         if(i == cnt)27         {28             if(n%s == 0)    size[i] = s;29             else    size[i] = n%s30         //求最后一个块的大小 31         }32         else size[i] = s;33     } 34 }35 36 int query(int l,int r)37 {//询问操作 38     int ans = 0;39     if(belong[l] == belong[r])40         ans += sum[belong[l]];41     //询问区间在一个块里的情况42      43     while(belong[l] == belong[l - 1])44     {//询问区间在整块左侧的情况 45         ans += a[l] + add[belong[l]];46         l ++; 47     }48     while(belong[r] == belong[r + 1])49     {//询问区间在整块右侧的情况 50         ans += a[r] + add[belong[r]];51         r --;52     }53     for(int i = belong[l];i <= belong[r];i ++)54     //对整块进行求和操作 55         ans += sum[i];56     return ans; 57 }58 59 void modify(int l,int r,int k)60 {//修改（增减值）操作 61     if(belong[l] == belong[r])62     {//修改区间在一个块内的情况 63         for(int i = l;i <= r;i ++)64             a[i] += v;65         return;66     }67     while(belong[l] == belong[l - 1])68     {//修改区间在整块左侧的情况 69         a[l] += v;70         l ++;71     }72     while(belong[r] == belong[r + 1])73     {//修改区间在整块右侧的情况 74         a[r] += v;75         r --;76     }77     for(int i = belong[l];i <= belong[r];i ++)78     {//对整块进行增减操作 79         add[i] += v;//标记一个块 80         sum[i] += size[i]*v;81     }82 }