题意很是晦涩。
大意为:给出一个01串,有三种操作:
1.把区间[a, b]内的数全变为1;
2.把区间[a, b]内的数全变为0;
3.把区间[a, b]内的数全部取反。
基础的延迟更新操作。
关于离线操作,区间最好处理成左闭右开,否则对于[x0, x1]和[x1, x2]中的x1不好处理。
#include <algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; #define MAXN 1024010 #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 int sum[MAXN << 2]; int col[MAXN << 2], inv[MAXN << 2]; char s[MAXN], tmp[MAXN], op[4], o[MAXN][4]; int a[MAXN], b[MAXN], num[MAXN]; int p[MAXN << 1], ip[MAXN << 1]; int q, t, m, qq; void build(int l, int r, int rt) { col[rt] = inv[rt] = -1; if(l == r) { sum[rt] = num[l]; return ; } int m = (l + r) >> 1; build(lson); build(rson); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void rev(int rt) { if(~inv[rt]) inv[rt] = -1; else inv[rt] = 1; } void pushdown(int l, int r, int rt) { int m = (l + r) >> 1; if(~col[rt]) { inv[rt << 1] = inv[rt << 1 | 1] = -1; col[rt << 1] = col[rt << 1 | 1] = col[rt]; sum[rt << 1] = (p[m + 1] - p[l]) * col[rt]; sum[rt << 1 | 1] = (p[r + 1] - p[m + 1]) * col[rt]; col[rt] = -1; } if(~inv[rt]) { rev(rt << 1); rev(rt << 1 | 1); sum[rt << 1] = (p[m + 1] - p[l]) - sum[rt << 1]; sum[rt << 1 | 1] = (p[r + 1] - p[m + 1]) - sum[rt << 1 | 1]; inv[rt] = -1; } } void update(int L, int R, int val, int l, int r, int rt) { if(L <= l && r <= R) { col[rt] = val; inv[rt] = -1; sum[rt] = (p[r + 1] - p[l]) * val; return ; } pushdown(l, r, rt); int m = (l + r) >> 1; if(L <= m) update(L, R, val, lson); if(R > m) update(L, R, val, rson); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void change(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { rev(rt); sum[rt] = (p[r + 1] - p[l]) - sum[rt]; return ; } pushdown(l, r, rt); int m = (l + r) >> 1; if(L <= m) change(L, R, lson); if(R > m) change(L, R, rson); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } int query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) return sum[rt]; pushdown(l, r, rt); int m = (l + r) >> 1; int ret = 0; if(L <= m) ret += query(L, R, lson); if(R > m) ret += query(L, R, rson); return ret; } void put(int l, int r, int rt) { if(l == r) { cout << sum[rt] << ' '; return ; } pushdown(l, r, rt); int m = (l + r) >> 1; put(l, m, rt << 1); put(m + 1, r, rt << 1 | 1); } int main() { // freopen("UVa_11402.in", "r", stdin); scanf("%d", &t); for(int cas = 1; cas <= t; cas++) { scanf("%d", &m); int tot = 0, T; for(int i = 0; i < m; i++) { scanf("%d%s", &T, tmp); int len = strlen(tmp); for(int j = 0; j < T; j++) for(int k = 0; k < len; k++) s[tot++] = tmp[k]; } s[tot] = '\0'; // cout << s << endl; scanf("%d", &T); for(int i = 0; i < T; i++) { scanf("%s%d%d", o[i], &a[i], &b[i]); p[i << 1] = a[i]; p[i << 1 | 1] = ++b[i]; } sort(p, p + 2 * T); int cnt = 0; for(int i = 0; i < 2 * T; i++) if(p[i] != p[cnt]) p[++cnt] = p[i]; cnt++; //左闭右开 for(int i = 0; i < cnt - 1; i++) { int l = p[i], r = p[i + 1]; num[i] = 0; for(int j = l; j < r; j++) num[i] += s[j] - '0'; } for(int i = 0; i < cnt; i++) ip[p[i]] = i; int n = cnt - 2; build(0, n, 1); //put(0, n, 1); cout << endl; printf("Case %d:\n", cas); qq = 0; for(int i = 0; i < T; i++) { if(o[i][0] == 'F') update(ip[a[i]], ip[b[i]] - 1, 1, 0, n, 1); if(o[i][0] == 'E') update(ip[a[i]], ip[b[i]] - 1, 0, 0, n, 1); if(o[i][0] == 'I') change(ip[a[i]], ip[b[i]] - 1, 0, n, 1); if(o[i][0] == 'S') printf("Q%d: %d\n", ++qq, query(ip[a[i]], ip[b[i]] - 1, 0, n, 1)); } } return 0; }