Codeves-5037线段树4加强版（线段树？。。。分块)

维护一个序列，要求支持下列2种操作：

add a b c:区间[a,b]中每个数加上c

count a b:查询区间[a,b]中有多少数是k的倍数（k为给定常数）

输入描述 Input Description

第一行三个数n,m,k,分别表示序列长度、操作数和count中的k

接下来一行n个整数，表示原始序列

接下来m行，每行是题面中的操作之一

输出描述 Output Description

对于每个count操作，输出一行答案

样例输入 Sample Input

10 10 5

5 5 8 3 5 6 7 8 3 0

add 2 7 1

count 3 4

add 2 5 4

count 1 5

count 2 6

count 1 3

add 4 8 3

count 3 7

add 4 8 2

count 1 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

10%:n,m<=10,k<=10000;

另外的20%:n,m<=100000,k<=10;

另外的20%:n,m<=50000,k<=100;

100%:n,m<=200000,k<=200000.

题解：这题，题目说线段树。。。我觉得线段树不可做，，，自己太菜了QWQ。我用的分块的思想；

对于块内维护，对于L~R完整的块，我们只需记录所加的数x,然后统计块内对K取模后值为看k-x%k的数的数量的和，对于两边不完整的块，暴力即可(最坏2*√n));

参考代码为：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<cstdlib>
  6 #include<algorithm>
  7 #include<queue>
  8 #include<stack>
  9 #include<set>
 10 #include<vector>
 11 #include<map>
 12 using namespace std;
 13 typedef long long LL;
 14 const int INF=0x3f3f3f3f;
 15 const LL inf=0x3f3f3f3f3f3f3f3fLL;
 16 const int maxn=2e5+10;
 17 const int block=800;
 18 int n,q,k,a[maxn],x,y,z,seg[255],v[255][maxn];
 19 char str[10];
 20 
 21 inline void read(int &x)
 22 {
 23     char c;int sign = 1;x = 0;
 24     do { c = getchar(); if(c == '-') sign = -1; } while(!isdigit(c));
 25     do { x = x * 10 + c - '0'; c = getchar(); } while(isdigit(c));
 26     x *= sign;
 27 }
 28 
 29 int main()
 30 {
 31     memset(seg,0,sizeof seg);
 32     read(n),read(q),read(k);
 33     for(int i=1;i<=n;i++)
 34     {
 35         read(a[i]);
 36         if(a[i]>=k) a[i]%=k;
 37         v[(i-1)/block+1][a[i]]++;    
 38     } 
 39     
 40     while(q--)
 41     {
 42         scanf("%s",str);
 43         read(x),read(y);
 44         int l=(x-1)/block+2,r=(y-1)/block;
 45         if(str[0]=='a')
 46         {
 47             read(z);
 48             if(l<=r)
 49             {
 50                 for(int i=l;i<=r;i++)
 51                 {
 52                     seg[i]+=z;
 53                     if(seg[i]>=k) seg[i]%=k;
 54                 }
 55                 for(int i=x;i<=(l-1)*block;i++)
 56                 {
 57                     v[l-1][a[i]]--;
 58                     a[i]+=z;
 59                     if(a[i]>=k) a[i]%=k;
 60                     v[l-1][a[i]]++;
 61                 }
 62                 for(int i=r*block+1;i<=y;i++)
 63                 {
 64                     v[r+1][a[i]]--;
 65                     a[i]+=z;
 66                     if(a[i]>=k) a[i]%=k;
 67                     v[r+1][a[i]]++;
 68                 }
 69             }
 70             else
 71             {
 72                 for(int i=x;i<=y;i++)
 73                 {
 74                     v[(i-1)/block+1][a[i]]--;
 75                     a[i]+=z;
 76                     if(a[i]>=k) a[i]%=k;
 77                     v[(i-1)/block+1][a[i]]++;
 78                 }
 79             }
 80         }
 81         else 
 82         {
 83             int ans=0;
 84             if(l<=r)
 85             {
 86                 for(int i=l;i<=r;i++)
 87                 {
 88                     int temp=0;
 89                     if(k<seg[i]) temp=k-seg[i]%k;
 90                     else temp=k-seg[i];
 91                     if(temp==k) temp=0;
 92                     ans+=v[i][temp];
 93                 }
 94                 for(int i=x;i<=(l-1)*block;i++)
 95                     if(a[i]+seg[l-1]==k || a[i]+seg[l-1]==0) ans++;
 96                 for(int i=r*block+1;i<=y;i++)
 97                     if(a[i]+seg[r+1]==k || a[i]+seg[r+1]==0) ans++;    
 98             }
 99             else
100             {
101                 for(int i=x;i<=y;i++)
102                     if(a[i]+seg[(i-1)/block+1]==k || a[i]+seg[(i-1)/block+1]==0) ans++;
103             }
104             printf("%d
",ans);
105         }
106     }
107     return 0;
108  }

View Code

Codeves-5037线段树4加强版（线段树？ 。。。分块)

Codeves-5037线段树4加强版（线段树？。。。分块)