• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# dmopc17c4p6 err

a guest Feb 18th, 2020 139 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. typedef double D;
5. typedef vector<int> VI;
6. typedef set<int> SI;
7. typedef map<int, int> MII;
8. typedef pair<int,int> PII;
9.
10. #define MP make_pair
11. #define A first
12. #define B second
13.
14. #define PB push_back
15. #define FR(i, a, b) for(int i=(a); i<(b); i++)
16. #define FOR(i, n) FR(i, 0, n)
17. #define EACH(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)
18.
19. template <typename T> inline void SetMin(T &a, T b) {if(b < a) a = b;}
20. template <typename T> inline void SetMax(T &a, T b) {if(b > a) a = b;}
21.
22. const D EPS = 1e-9;
23. int EQ(D a, D b) {return fabs(a - b) < EPS;}
24.
25. typedef complex<D> P;
26. #define X real
27. #define Y imag
28. P GetPoint() {  D x, y; cin >> x >> y; return P(x, y);}
29. void ShowPoint(P p) {cout << X(p) << "," << Y(p) << "\n";}
30. D Cross(P a, P b) {return Y(conj(a) * b);}
31. D Dot(P a, P b) {return X(conj(a) * b);}
32.
33. const LL M = 1000000007LL;
34. void Add(LL &a, LL b) {a = (a + b) % M;}
35. void Mul(LL &a, LL b) {a = (a * b) % M;}
36. LL Sum(LL a, LL b) {return (a + b) % M;}
37. LL Prod(LL a, LL b) {return (a * b) % M;}
38.
39. namespace IO {
40.    const int BUF = 32768;
41.    FILE *in = stdin;
42.    int ipos = BUF;
43.    char inbuf [BUF];
44.    inline void init (const char *namein) {
45.        in = fopen (namein, "r");
46.    }
47.
48.    inline char nextc (bool adv = true) {
49.        if (ipos == BUF) {
50.            fread (inbuf, sizeof (char), BUF, in);
51.            ipos = 0;
52.        }
53.        return inbuf [adv ? ipos++ : ipos];
54.    }
55.
56.    inline void read (int &num) {
57.        while (nextc (false) != '-' && (nextc (false) < '0' || nextc (false) > '9')) {
58.            ipos++;
59.        }
60.
61.        bool neg = false;
62.        if (nextc (false) == '-') {
63.            neg = true;
64.            ipos++;
65.        }
66.
67.        for (num = 0; nextc (false) >= '0' && nextc (false) <= '9';) {
68.            num = num * 10 + nextc () - '0';
69.        }
70.
71.        if (neg) num = -num;
72.    }
73.
74.    inline void readch (char &ch) {
75.        while (nextc (false) < 'A' || nextc (false) > 'Z') {
76.            ipos++;
77.        }
78.
79.        ch = nextc();
80.
81.    }
82.
83. }
84.
85. struct node{
86.   int m, a, k, i, ma, ak, ki, mak, aki, maki;
87.   node() {
88.     m = a = k = i = ma = ak = ki = mak = aki = maki = 0;
89.   }
90. };
91.
92. const int DEP = 18;
93. const int SIZ = 1<<DEP;
94.
95. node tree[SIZ * 2];
96. int len[SIZ * 2];
97. char marked[SIZ * 2];
98.
99. int n, q;
100.
101. void MarkRange(int p, char ch) {
102.   tree[p] = node();
103.   if(ch == 'M') tree[p].m = len[p];
104.   if(ch == 'A') tree[p].a = len[p];
105.   if(ch == 'K') tree[p].k = len[p];
106.   if(ch == 'I') tree[p].i = len[p];
107.   marked[p] = ch;
108. }
109.
110. void Down(int p) {
111.   if(marked[p] != 0) {
112.     MarkRange(p * 2, marked[p]);
113.     MarkRange(p * 2 + 1, marked[p]);
114.     marked[p] = 0;
115.   }
116. }
117.
118. inline void Moo(int &res, int &a, int &b) {
119.   int k = min(a, b);
120.   res += k;
121.   a -= k;
122.   b -= k;
123. }
124.
125. void Merge(node &res, node a, node b) {
126.   res = node();
127.   Moo(res.maki, a.mak, b.i);
128.   Moo(res.maki, a.ma, b.ki);
129.   Moo(res.maki, a.m, b.aki);
130.   Moo(res.mak, a.ma, b.k);
131.   Moo(res.mak, a.m, b.ak);
132.   Moo(res.aki, a.ak, b.i);
133.   Moo(res.aki, a.a, b.ki);
134.   Moo(res.ak, a.a, b.k);
135.   Moo(res.ki, a.k, b.i);
136.   Moo(res.ma, a.m, b.a);
137.   res.m += a.m + b.m;
138.   res.a += a.a + b.a;
139.   res.k += a.k + b.k;
140.   res.i += a.i + b.i;
141.   res.ma += a.ma + b.ma;
142.   res.ak += a.ak + b.ak;
143.   res.ki += a.ki + b.ki;
144.   res.mak += a.mak + b.mak;
145.   res.aki += a.aki + b.aki;
146.   res.maki += a.maki + b.maki;
147. }
148.
149. node Query(int p, int l, int r, int l1, int r1) {
150.   if(l == l1 && r == r1) {
151.     return tree[p];
152.   } else {
153.     node res;
154.     Down(p);
155.     int mid = (l + r) / 2;
156.     if(r1 <= mid) res = Query(p * 2, l, mid, l1, r1);
157.     else if(mid < l1) res = Query(p * 2 + 1, mid + 1, r, l1, r1);
158.     else {
159.       Merge(res, Query(p * 2, l, mid, l1, mid), Query(p * 2 + 1, mid + 1, r, mid + 1, r1));
160.     }
161.     return res;
162.   }
163. }
164.
165.
166. void SetRange(int p, int l, int r, int l1, int r1, char ch) {
167.   if(l == l1 && r == r1) {
168.     MarkRange(p, ch);
169.   } else {
170.     int mid = (l + r) / 2;
171.     Down(p);
172.     if(r1 <= mid) SetRange(p * 2, l, mid, l1, r1, ch);
173.     else if(mid < l1) SetRange(p * 2 + 1, mid + 1, r, l1, r1, ch);
174.     else {
175.       SetRange(p * 2, l, mid, l1, mid, ch);
176.       SetRange(p * 2 + 1, mid + 1, r, mid + 1, r1, ch);
177.     }
178.     Merge(tree[p], tree[p * 2], tree[p * 2 + 1]);
179.   }
180. }
181.
182. int main() {
183.   memset(marked, 0, sizeof(marked));
184.   FOR(i, SIZ) {
185.     len[SIZ + i] = 1;
186.   }
187.   for(int i = SIZ - 1; i > 0; --i) {
188.     len[i] = len[i * 2] + len[i * 2 + 1];
189.   }
192.   FOR(i, q) {
193.     int cmd, l, r;
197. //printf("%d %d %d\n", cmd, l, r); fflush(stdout);
198.     if(cmd == 2) {
199.       printf("%d\n", Query(1, 1, SIZ, l, r).maki);
200.     } else {
201.       char ch;