mayoko’s diary

プロコンとかいろいろ。

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;
}