5037 线段树练习4加强版
时间限制: 4 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
维护一个序列，要求支持下列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
0
3
2
2
1
2
数据范围及提示 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.
分析 Analysis
分块！
拿线段树练习4 的代码改了改就过了
模型和线段树练习4是一样的，只不过改了取模数的范围
代码 Code
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #define maxn 1000000 5 using namespace std; 6 7 char str[10]; 8 int block[maxn],k,mod[450][200010],size,arr[maxn],add[450],bdd[450],n,m; 9 10 void modify(){ 11 int a,b,c; 12 scanf("%d%d%d",&a,&b,&c); 13 a--,b--,c %= k; 14 if(!c) return; 15 16 if(block[a] == block[b]){ 17 for(int i = a;i <= b;i++){ 18 mod[block[i]][arr[i]]--; 19 arr[i] = (arr[i]+c)%k; 20 mod[block[i]][arr[i]]++; 21 } 22 }else{ 23 24 for(int i = a;i <= block[a]*size-1;i++) 25 mod[block[i]][arr[i]]--, 26 arr[i] = (arr[i]+c)%k, 27 mod[block[i]][arr[i]]++; 28 for(int i = (block[b]-1)*size;i <= b;i++) 29 mod[block[i]][arr[i]]--, 30 arr[i] = (arr[i]+c)%k, 31 mod[block[i]][arr[i]]++; 32 for(int i = block[a]+1;i < block[b];i++) 33 add[i] = (add[i]+c)%k, 34 bdd[i] = (bdd[i]-c+k)%k; 35 36 } 37 } 38 39 void count(){ 40 int a,b; 41 scanf("%d%d",&a,&b); 42 a--,b--; 43 int ans = 0; 44 45 if(block[a] == block[b]){ 46 for(int i = a;i <= b;i++) 47 ans += ((arr[i]+add[block[i]])%k)?0:1; 48 }else{ 49 50 for(int i = a;i <= block[a]*size-1;i++) 51 ans += ((arr[i]+add[block[i]])%k)?0:1; 52 for(int i = (block[b]-1)*size;i <= b;i++) 53 ans += ((arr[i]+add[block[i]])%k)?0:1; 54 for(int i = block[a]+1;i < block[b];i++) 55 ans += mod[i][bdd[i]]; 56 57 } 58 59 printf("%d ",ans); 60 } 61 62 void show(){ 63 for(int i = 0;i < n;i++){ 64 printf("%d ",arr[i]+add[block[i]]); 65 }cout << endl; 66 } 67 68 int main(){ 69 scanf("%d%d%d",&n,&m,&k); 70 size = (int)sqrt(n)+1; 71 for(int i = 0;i < n;i++) block[i] = i/size+1; 72 // for(int i = 0;i < n;i++) printf("#%d: block %d ",i,block[i]); 73 for(int i = 0;i < n;i++){ 74 scanf("%d",&arr[i]); 75 arr[i] %= k; 76 mod[block[i]][arr[i]]++; 77 } 78 // show(); 79 for(int i = 0;i < m;i++){ 80 scanf("%s",str); 81 if(str[0] == 'a') modify(); 82 else count(); 83 // show(); 84 } 85 86 return 0; 87 }