Lucky Queries https://codeforces.com/problemset/problem/145/E
感觉是很简单的区间合并, 但是好像我写的比较麻烦.
- #include<bits/stdc++.h>
- #define LL long long
- #define fi first
- #define se second
- #define mk make_pair
- #define PLL pair<LL, LL>
- #define PLI pair<LL, int>
- #define PII pair<int, int>
- #define SZ(x) ((int)x.size())
- #define ull unsigned long long
- using namespace std;
- const int N = 1e6 + 7;
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- const int mod = 1e9 + 7;
- const double eps = 1e-8;
- #define lson l, mid, rt <<1
- #define rson mid + 1, r, rt << 1 | 1
- struct info {
- int up[2][2];
- int dn[2][2];
- } a[N << 2];
- info operator + (const info& a, const info& b) {
- info ans;
- ans.up[0][0] = a.up[0][0] + b.up[0][0];
- ans.up[0][1] = max(a.up[0][0] + max(b.up[1][1], b.up[0][1]), a.up[0][1] + b.up[1][1]);
- ans.up[1][1] = a.up[1][1] + b.up[1][1];
- ans.dn[1][1] = a.dn[1][1] + b.dn[1][1];
- ans.dn[1][0] = max(a.dn[1][1] + max(b.dn[0][0], b.dn[1][0]), a.dn[1][0] + b.dn[0][0]);
- ans.dn[0][0] = a.dn[0][0] + b.dn[0][0];
- return ans;
- }
- int lazy[N << 2];
- void change(int rt) {
- swap(a[rt].up[0][0], a[rt].dn[1][1]);
- swap(a[rt].up[1][1], a[rt].dn[0][0]);
- swap(a[rt].up[0][1], a[rt].dn[1][0]);
- }
- void push(int rt) {
- if(lazy[rt]) {
- change(rt << 1); change(rt << 1 | 1);
- lazy[rt << 1] ^= 1;
- lazy[rt << 1 | 1] ^= 1;
- lazy[rt] = 0;
- }
- }
- void build(int l, int r, int rt) {
- if(l == r) {
- int x; scanf("%1d", &x);
- if(x == 4) {
- a[rt].up[0][0] = 1;
- a[rt].up[0][1] = 0;
- a[rt].up[1][1] = 0;
- a[rt].dn[0][0] = 1;
- a[rt].dn[1][0] = 0;
- a[rt].dn[1][1] = 0;
- }
- else {
- a[rt].up[0][0] = 0;
- a[rt].up[0][1] = 0;
- a[rt].up[1][1] = 1;
- a[rt].dn[0][0] = 0;
- a[rt].dn[1][0] = 0;
- a[rt].dn[1][1] = 1;
- }
- return;
- }
- int mid = l + r>> 1;
- build(lson); build(rson);
- a[rt] = a[rt <<1] + a[rt << 1 | 1];
- }
- void update(int L, int R, int l, int r, int rt) {
- if(l>= L && r <= R) {
- lazy[rt] ^= 1;
- change(rt);
- return;
- }
- int mid = l + r>> 1;
- push(rt);
- if(L <= mid) update(L, R, lson);
- if(R> mid) update(L, R, rson);
- a[rt] = a[rt << 1] + a[rt << 1 | 1];
- }
- int n, m;
- char s[10];
- int main() {
- scanf("%d%d", &n, &m);
- build(1, n, 1);
- while(m--) {
- scanf("%s", s);
- if(s[0] == 'c') {
- printf("%d\n", max(a[1].up[0][0], max(a[1].up[0][1], a[1].up[1][1])));
- } else {
- int L, R;
- scanf("%d%d", &L, &R);
- update(L, R, 1, n, 1);
- }
- }
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2959776.html