Submission #75820034

---

Source Code Expand

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;

struct Node {
    int l, sum, hs, pt, pl, st, sl;
};
template<typename Node> struct SegTree {
    int n, size;
    Node e; // 항등원
    vector<Node> tree;
    function<Node(Node, Node)> func;
    SegTree(int n, const Node& e, auto func) : n(n), size(1<<(__lg(n)+1)), e(e), tree(size<<1, e), func(func) {}
    SegTree(const vector<Node>& v, const Node& e, auto func) : n(sz(v)), size(1<<(__lg(n)+1)), e(e), tree(size<<1, e), func(func) {
        for (int i = 0; i < n; i++) tree[i+size] = v[i];
        for (int i = size-1; i > 0; i--) tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
    }
    Node query(int i) { return tree[i + size]; }
    Node query(int l, int r) {
        Node L = e, R = e;
        for (l += size, r += size; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) L = func(L, tree[l++]);
            if (~r & 1) R = func(tree[r--], R);
        }
        return func(L, R);
    }
};
int main() {
    fastio; int N, Q; cin >> N >> Q;
    string s; cin >> s;
    vector<Node> v(N);
    for (int i = 0; i < N; i++) {
        int t = 0;
        if (s[i] == 'R') t = 1;
        else if (s[i] == 'G') t = 2;
        else if (s[i] == 'B') t = 3;
        if (t == 0) v[i] = { 1, 0, 0, 0, 0, 0, 0 };
        else v[i] = { 1, 1, 0, t, 1, t, 1 };
    }
    SegTree<Node> sg(v, { 0, 0, 0, 0, 0, 0, 0 }, [](Node a, Node b) {
        Node res;
        res.l = a.l + b.l;
        res.sum = a.sum + b.sum;
        res.hs = a.hs + b.hs;
        if (a.st == b.pt && a.st != 0) {
            if (a.sl%2 && b.pl%2) res.hs++;
        }
        if (a.l == a.pl) {
            res.pl = a.l + (a.st == b.pt && a.st != 0 ? b.pl : 0);
        }
        else res.pl = a.pl;
        res.pt = a.pt;
        if (b.l == b.sl) {
            res.sl = b.l + (a.st == b.pt && a.st != 0 ? a.sl : 0);
        }
        else res.sl = b.sl;
        res.st = b.st;
        return res;
    });
    for (int q = 0; q < Q; q++) {
        int l, r; cin >> l >> r; l--; r--;
        auto res = sg.query(l, r);
        cout << res.hs << "\n";
    }
    return 0;
}

Submission Info

Judge Result