首页 > 代码库 > 1135 - Count the Multiples of 3
1135 - Count the Multiples of 3
1135 - Count the Multiples of 3
| PDF (English) | Statistics | Forum |
| Time Limit: 3 second(s) | Memory Limit: 64 MB |
You have an array with n elements which is indexed from 0 to n - 1. Initially all elements are zero. Now you have to deal with two types of operations
- Increase the numbers between indices i and j (inclusive) by 1. This is represented by the command ‘0 i j‘.
- Answer how many numbers between indices i and j (inclusive) are divisible by 3. This is represented by the command ‘1 i j‘.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form ‘0 i j‘ or ‘1 i j‘ where i, j are integers and 0 ≤ i ≤ j < n.
Output
For each case, print the case number first. Then for each query in the form ‘1 i j‘, print the desired result.
Sample Input | Output for Sample Input |
1 10 9 0 0 9 0 3 7 0 1 4 1 1 7 0 2 2 1 2 4 1 8 8 0 5 8 1 6 9 | Case 1: 2 3 0 2 |
Note
Dataset is huge, use faster i/o methods.
Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
思路：线段树+lazy标记区间更新
线段数维护的是mod3为0，1，2的个数，然后lazy标记区间更新就可以了，复杂度（n*log(n)^2）;
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<stdlib.h> 6 #include<queue> 7 #include<math.h> 8 #include<vector> 9 using namespace std; 10 typedef struct node 11 { 12 int mod1; 13 int mod2; 14 int mod3; 15 int val; 16 node() 17 { 18 val = 0; 19 } 20 } tr; 21 tr tree[4*200005]; 22 void build(int l,int r,int k); 23 void mov(int k); 24 void in(int l,int r,int k,int nn,int mm); 25 void up(int k); 26 int query(int l,int r,int k,int nn,int mm); 27 int main(void) 28 { 29 int i,j; 30 int T; 31 int __ca = 0; 32 scanf("%d",&T); 33 while(T--) 34 { 35 int n,m; 36 scanf("%d %d",&n,&m); 37 memset(tree,0,sizeof(tree)); 38 build(0,n-1,0); 39 printf("Case %d:\n",++__ca); 40 while(m--) 41 { 42 int val ,x,y; 43 scanf("%d%d%d",&val,&x,&y); 44 if(val) 45 { 46 printf("%d\n",query(x,y,0,0,n-1)); 47 } 48 else 49 { 50 in(x,y,0,0,n-1); 51 } 52 } 53 } 54 return 0; 55 } 56 void build(int l,int r,int k) 57 { 58 if(l==r) 59 { 60 tree[k].mod3 = 1; 61 tree[k].mod1 = 0; 62 tree[k].mod2 = 0; 63 tree[k].val = 0; 64 return ; 65 } 66 tree[k].val = 0; 67 build(l,(l+r)/2,2*k+1); 68 build((l+r)/2+1,r,2*k+2); 69 tree[k].mod1 = tree[2*k+1].mod1 + tree[2*k+2].mod1; 70 tree[k].mod2 = tree[2*k+1].mod2 + tree[2*k+2].mod2; 71 tree[k].mod3 = tree[2*k+1].mod3 + tree[2*k+2].mod3; 72 } 73 void mov(int k) 74 { 75 int x = tree[k].mod1; 76 tree[k].mod1 = tree[k].mod3; 77 tree[k].mod3 = tree[k].mod2; 78 tree[k].mod2 = x; 79 return ; 80 } 81 void in(int l,int r,int k,int nn,int mm) 82 { 83 if(l > mm||r < nn) 84 { 85 return ; 86 } 87 else if(l <= nn&& r>=mm) 88 { 89 tree[k].val++; 90 tree[k].val%=3; 91 int x = tree[k].val; 92 tree[k].val = 0; 93 if(x) 94 { 95 tree[2*k+1].val += x; 96 tree[2*k+2].val +=x; 97 tree[2*k+1].val%=3; 98 tree[2*k+2].val%=3; 99 while(x)100 {101 mov(k);102 x--;103 }104 }105 up(k);106 }107 else108 {109 int x= tree[k].val;110 tree[2*k+1].val = (tree[2*k+1].val + x)%3;111 tree[2*k+2].val = (tree[2*k+2].val + x)%3;112 tree[k].val = 0;113 in(l,r,2*k+1,nn,(nn+mm)/2);114 in(l,r,2*k+2,(nn+mm)/2+1,mm);115 }116 }117 void up(int k)118 {119 if(k == 0)120 return ;121 while(k)122 {123 k = (k-1)/2;124 int xll = 2*k+1;125 int xrr = 2*k+2;126 if(tree[xll].val)127 {128 int x = tree[xll].val;129 {130 tree[xll].val = 0;131 tree[2*xll+1].val = (tree[2*xll+1].val + x)%3;132 tree[2*xll+2].val = (tree[2*xll+2].val + x)%3;133 while(x)134 {135 mov(xll);136 x--;137 }138 }139 }140 if(tree[xrr].val)141 {142 int x= tree[xrr].val;143 tree[2*xrr+1].val = (tree[2*xrr+1].val+x)%3;144 tree[2*xrr+2].val = (tree[2*xrr+2].val+x)%3;145 tree[xrr].val = 0;146 while(x)147 {148 mov(xrr);149 x--;150 }151 }152 tree[k].mod1 = tree[2*k+1].mod1+tree[2*k+2].mod1;153 tree[k].mod2 = tree[2*k+1].mod2+tree[2*k+2].mod2;154 tree[k].mod3 = tree[2*k+1].mod3+tree[2*k+2].mod3;155 }156 }157 int query(int l,int r,int k,int nn,int mm)158 {159 if(l > mm||r < nn)160 {161 return 0;162 }163 else if(l <=nn&&r>=mm)164 {165 if(tree[k].val)166 {167 int x= tree[k].val;168 tree[k].val = 0;169 tree[2*k+1].val = (tree[2*k+1].val+x)%3;170 tree[2*k+2].val = (tree[2*k+2].val+x)%3;171 while(x)172 {173 mov(k);174 x--;175 }176 }177 up(k);178 return tree[k].mod3;179 }180 else181 {182 if(tree[k].val)183 {184 int x = tree[k].val;185 tree[k].val = 0;186 tree[2*k+1].val = (tree[2*k+1].val+x)%3;187 tree[2*k+2].val = (tree[2*k+2].val+x)%3;188 }189 int nx = query(l,r,2*k+1,nn,(nn+mm)/2);190 int ny = query(l,r,2*k+2,(nn+mm)/2+1,mm);191 return nx+ny;192 }193 }
1135 - Count the Multiples of 3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。