QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#263446#186. Street LampsCamillusCompile Error//C++206.1kb2023-11-24 20:54:012023-11-24 20:54:02

Judging History

你现在查看的是最新测评结果

  • [2023-11-24 20:54:02]
  • 评测
  • [2023-11-24 20:54:01]
  • 提交

answer

#include "bits/stdc++.h"

using ll = long long;
using namespace std;

pair<int, ll> operator+(const pair<int, ll> &A, const pair<int, ll> &B) {
    return {A.first + B.first, A.second + B.second};
}

namespace implicit_st {
    struct node {
        int cnt = 0;
        ll sum = 0;

        int left = 0, right = 0;
    };

    vector<node> tree = { node() };

    int new_node() {
        tree.emplace_back();
        return (int)tree.size() - 1;
    }

    void add(int l, int r, int v, int x, int lx, int rx) {
        assert(x != 0);

        if (l <= lx && rx <= r) {
            tree[x].cnt += 1;
            tree[x].sum += v;
            return;
        }

        int mx = (lx + rx) / 2;

        if (r <= mx) {
            if (!tree[x].left) {
                tree[x].left = new_node();
            }
            add(l, r, v, tree[x].left, lx, mx);
        }

        if (l >= mx) {
            if (!tree[x].right) {
                tree[x].right = new_node();
            }
            add(l, r, v, tree[x].right, mx, rx);
        }
    }

    pair<int, ll> get(int i, int x, int lx, int rx) {
        if (x == 0) {
            return {0, 0ll};
        }

        pair<int, ll> cur(tree[x].cnt, tree[x].sum);

        if (rx - lx == 1) {
            return cur;
        }

        int mx = (lx + rx) / 2;

        if (i < mx) {
            return get(i, tree[x].left, lx, mx) + cur;
        } else {
            return get(i, tree[x].right, mx, rx) + cur;
        }
    }

    struct st {
        int root;
        int n;

        st(int n) : n(n) {
            root = new_node();
        }

        void add(int l, int r, int v) const {
            implicit_st::add(l, r, v, root, 0, n);
        }

        pair<int, ll> get(int i) const {
            return implicit_st::get(i, root, 0, n);
        }
    };
} // namespace implicit_st

struct main_st {
    vector<implicit_st::st> tree;
    int n;

    main_st(int n) : n(n) {
        tree.assign(4 * n, implicit_st::st(0));
        for (auto &item : tree) {
            item = implicit_st::st(n + 1);
        }
    }

    void add(pair<int, int> lefts, pair<int, int> rights, int time) {
        add(lefts.first, lefts.second + 1, rights.first, rights.second + 1, time, 0, 0, n);
    }

    pair<int, ll> get(int a, int b) {
        return get(a, b, 0, 0, n);
    }

private:
    void add(int lq, int rq, int l, int r, int v, int x, int lx, int rx) {
        if (lq <= lx && rx <= rq) {
            tree[x].add(l, r, v);
            return;
        }

        if (lq >= rx || lx >= rq) {
            return;
        }

        add(lq, rq, l, r, v, x * 2 + 1, lx, (lx + rx) / 2);
        add(lq, rq, l, r, v, x * 2 + 2, (lx + rx) / 2, rx);
    }

    pair<int, ll> get(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            return tree[x].get(v);
        }

        int mx = (lx + rx) / 2;

        if (i < mx) {
            return tree[x].get(v) + get(i, v, x * 2 + 1, lx, mx);
        } else {
            return tree[x].get(v) + get(i, v, x * 2 + 2, mx, rx);
        }
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    main_st B(n), E(n);
    set<pair<int, int>> S;

    string s;
    cin >> s;

    for (int i = 0; i < n; ) {
        if (s[i] == '1') {
            int l = i, r = i;

            while (s[i] == '1') {
                r = i + 1;
                i++;
            }

            for (int j = l; j < r; j++) {
                B.add(make_pair(j, j), make_pair(j + 1, r), 0);
            }

            S.emplace(l, r);
        } else {
            i++;
        }
    }

    debug(S);

    for (int t = 1; t <= q; t++) {
        string type;
        cin >> type;

        if (type == "query") {
            int a, b;
            cin >> a >> b;

            a--, b--;

            auto x = B.get(a, b);
            auto y = E.get(a, b);

            ll ans = y.second - x.second;

            if (x.first != y.first) {
                ans += t;
            }

            cout << ans << '\n';
        } else {
            int i;
            cin >> i;

            i--;

            if (s[i] == '1') {
                s[i] = '0';

                auto it = prev(S.upper_bound(make_pair(i, i)));

                int l = it->first;
                int r = it->second;

                E.add(make_pair(l, i), make_pair(i + 1, r), t);

                S.erase(it);

                if (l < i) {
                    S.emplace(l, i);
                }

                if (i + 1 < r) {
                    S.emplace(i + 1, r);
                }
            } else {
                s[i] = '1';

                if ((i - 1 >= 0 && s[i - 1] == '0') && (i + 1 < n && s[i + 1] == '0')) {
                    B.add(make_pair(i, i), make_pair(i + 1, i + 1), t);
                } else if (!(i - 1 >= 0 && s[i - 1] == '0') && (i + 1 < n && s[i + 1] == '0')) {
                    auto it = S.upper_bound(make_pair(i, i));

                    int r = it->second;
                    S.erase(it);

                    S.emplace(i, r);

                    B.add(make_pair(i, i), make_pair(i + 1, r), t);
                } else if ((i - 1 >= 0 && s[i - 1] == '0') && !(i + 1 < n && s[i + 1] == '0')) {
                    auto it = prev(S.upper_bound(make_pair(i, i)));

                    int l = it->first;
                    S.erase(it);

                    S.emplace(l, i + 1);

                    B.add(make_pair(l, i), make_pair(i + 1, i + 1), t);
                } else {
                    auto it = S.upper_bound(make_pair(i, i));
                    int r = it->second;
                    S.erase(it);

                    it = prev(S.upper_bound(make_pair(i, i)));
                    int l = it->first;
                    S.erase(it);

                    S.emplace(l, r);

                    B.add(make_pair(l, i), make_pair(i + 1, r), t);
                }
            }
        }
    }
    return 0;
}

详细

answer.code: In function ‘int main()’:
answer.code:170:5: error: ‘debug’ was not declared in this scope
  170 |     debug(S);
      |     ^~~~~