1135 - Count the Multiples of 3
2024-09-06 10:22:34
1135 - Count the Multiples of 3
| 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 else
108 {
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 else
181 {
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 }
最新文章
- 解决Xcode真机测试时ineligible devices的问题
- markdown小记
- ios 定位 监听是否跨入某个指定的区域
- (IOS)Swift2.0 Radio 程序分析
- Java编程思想（一）：大杂烩
- iOS NSString 和NSData 转换
- [HTTP2] HTTP1 probs and HTTP2 saves
- [Powershell] 检查IIS设置
- spring的官方文真不错
- Cocos2d-x 3.0 红孩儿私人义务教育 - 第一章 熟人Cocos2d-x 3.0project
- 在MyEclipse中运行tomcat报错 严重: Error starting static Resources
- Myeclipse详细使用教程
- Notes ： <Hands-on ML with Sklearn & TF> Chapter 3
- 2019省赛训练组队赛3.31周四-17fj
- phpmyadmin 安装
- 禅道迁移(windows_to_linux)
- 线程属性 pthread_attr_t
- git commit之后，想撤销commit
- mysql 事务队列 写入 幂等性 重复写入
- 关于ClickOnce的一些技术文章