-
Notifications
You must be signed in to change notification settings - Fork 0
/
12895BOJ_brilliant_village.cpp
66 lines (60 loc) · 1.5 KB
/
12895BOJ_brilliant_village.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
struct Node
{
int bit, lazy;
Node(){
bit = 1;
lazy = 0;
}
};
Node tree[404040];
void prop(int x, int s, int e){
if (!tree[x].lazy) return;
tree[x].bit = tree[x].lazy;
if (s^e){
tree[x<<1].lazy = tree[x].lazy;
tree[x<<1|1].lazy = tree[x].lazy;
}
tree[x].lazy = 0;
}
void update(int l, int r, int s, int e, int k, int x = 1){
prop(x,s,e);
if (e < l || r < s) return;
if (l <= s && e <= r) {
tree[x].lazy = 1<<(k-1);
prop(x,s,e); return;
}
int mid = s + e >> 1;
update(l, r, s, mid, k, x<<1); update(l, r, mid+1, e, k, x<<1|1);
tree[x].bit = tree[x<<1].bit | tree[x<<1|1].bit;
}
int query(int l, int r, int s, int e, int x = 1){
prop(x, s, e);
if (e < l || r < s) return 0;
if (l <= s && e <= r) return tree[x].bit;
int mid = s+e>>1;
return query(l, r, s, mid, x<<1) | query(l, r, mid+1, e, x<<1|1);
}
int main()
{
fastio
int n,T,Q; cin >> n >> T >> Q;
while (Q--){
char op; int x,y,z; cin >> op >> x >> y;
if (x > y) swap(x,y);
if (op == 'C'){
cin >> z;
update(x,y,1,n,z);
} else{
int bit = query(x,y,1,n);
int ret = 0;
for (int i=T; i--;){
ret += bit&1;
bit>>=1;
}
cout << ret << '\n';
}
}
} // namespace std;