XXI Open Cup GP of China -- Problem G

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;

class SegTree {
    private:
        // Store
        //  Value:
        //      historic sum
        //      current sum (= number of ON elements)
        //      time since last operation
        //  Tag:
        //      current time of operation
        //      total time spent in TOGGLE state
        //      current toggle status of operation

        struct Tag {
            int cur_t = 0;
            int flip_t = 0;
            bool flip = 0;

            Tag() {}
            Tag(int ct, bool f) { cur_t = ct, flip = f; }
        };
        struct Node {
            ll hist_sum = 0;
            int cur_zero = 0;
            int cur_one = 0;
            int cur_t = 0;
        };

        vector<Node> seg;
        vector<Tag> tag;
        int global_t = 0;
        int h = 1;

        void apply(int i, const Tag& t) {
            int dt = t.cur_t - seg[i].cur_t;
            int dt_0 = dt - t.flip_t;
            int dt_1 = t.flip_t;

            seg[i].hist_sum += (ll)seg[i].cur_one * dt_0 + (ll)seg[i].cur_zero * dt_1;
            if (t.flip) swap(seg[i].cur_zero, seg[i].cur_one);
            seg[i].cur_t = t.cur_t;

            if (i < h) {
                tag[i].flip_t += (tag[i].flip ? dt_0 : dt_1);
                tag[i].flip ^= t.flip;
                tag[i].cur_t = t.cur_t;
            }
        }
        void push(int i) {
            apply(2*i, tag[i]);
            apply(2*i+1, tag[i]);
            tag[i].flip_t = 0;
            tag[i].flip = 0;
        }
        void update(int i) {
            seg[i].cur_zero = seg[2*i].cur_zero + seg[2*i+1].cur_zero;
            seg[i].cur_one = seg[2*i].cur_one + seg[2*i+1].cur_one;
            seg[i].hist_sum = seg[2*i].hist_sum + seg[2*i+1].hist_sum;
        }

        ll recGet(int a, int b, int i, int ia, int ib) {
            if (ib <= a || b <= ia) return 0;
            if (a <= ia && ib <= b) return seg[i].hist_sum;
            push(i);
            int im = (ia + ib) >> 1;
            return recGet(a, b, 2*i, ia, im) + recGet(a, b, 2*i+1, im, ib);
        }
        void recApply(int a, int b, const Tag& t, int i, int ia, int ib) {
            if (ib <= a || b <= ia) return;
            if (a <= ia && ib <= b) apply(i, t);
            else {
                push(i);
                int im = (ia + ib) >> 1;
                recApply(a, b, t, 2*i, ia, im);
                recApply(a, b, t, 2*i+1, im, ib);
                update(i);
            }
        }
    public:
        SegTree(int n) {
            while(h < n) h *= 2;
            seg.resize(2*h);
            for (int i = h; i < h + n; ++i) seg[i].cur_zero = 1;
            for (int i = h-1; i > 0; --i) update(i);
            tag.resize(h);
        }

        ll rangeSum(int a, int b) {
            // cerr << "RangeSum(" << a << ' '<< b << ")\n";
            return recGet(a, b+1, 1, 0, h);
        }

        void rangeToggle(int a, int b) {
            // cerr << "RangeToggle(" << a << ' '<< b << ")\n";
            recApply(a, b+1, Tag(global_t, 1), 1, 0, h);
            ++global_t;
            recApply(0, h, Tag(global_t, 0), 1, 0, h);
        }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> as(n);
    for (int& a : as) {
        cin >> a;
        --a;
    }

    vector<int> lst(n, n);
    vector<int> nxt(n, n);
    for (int i = n-1; i >= 0; --i) {
        nxt[i] = lst[as[i]];
        lst[as[i]] = i;
    }

    int q;
    cin >> q;
    vector<ll> ans(q, 0);
    vector<vector<pair<int, int>>> qs(n);
    for (int qi = 0; qi < q; ++qi) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        qs[a].emplace_back(b, qi);
    }

    SegTree seg(n);
    for (int i = n-1; i >= 0; --i) {
        seg.rangeToggle(i, nxt[i] - 1);
        for (auto& pr : qs[i]) {
            int j = pr.first;
            ans[pr.second] = seg.rangeSum(i, j);
        }
    }

    for (ll& v : ans) cout << v << '\n';
}