Monk and Otakuland
解法
mayokoex.hatenablog.com
これとほとんど同じです。
struct ST { vector<int> seg, lazy; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(size * 2); lazy.resize(size * 2); } void push(int k, int l, int r) { if (lazy[k] != 0) { seg[k] = (r - l) - seg[k]; if (r - l > 1) { lazy[k * 2 + 1] ^= lazy[k]; lazy[k * 2 + 2] ^= lazy[k]; } lazy[k] = 0; } } int merge(int x, int y) { return x + y; } void update(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[k] = 1; push(k, l, r); } else { update(a, b, k * 2 + 1, l, (l + r) / 2); update(a, b, k * 2 + 2, (l + r) / 2, r); seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]); } } void update(int a, int b) { return update(a, b, 0, 0, size); } int query(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; int x = query(a, b, k * 2 + 1, l, (l + r) / 2); int y = query(a, b, k * 2 + 2, (l + r) / 2, r); return merge(x, y); } int query(int a, int b) { return query(a, b, 0, 0, size); } }; int main() { int N, M; cin >> N >> M; ST seg(N-1); string s; cin >> s; for (int i = 0; i < N-1; i++) { if (s[i] == '<') seg.update(i, i+1); } for (int i = 0; i < M; i++) { int q; scanf("%d", &q); if (q==1) { int l, r; scanf("%d %d", &l, &r); l--; r--; seg.update(l, r); } else { int f, t; scanf("%d %d", &f, &t); int ans = -1; f--; t--; if (f < t) { ans = seg.query(f, t); } else { ans = f-t - seg.query(t, f); } printf("%d\n", ans); } } return 0; }