Submission #1102700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102700		Requiem	Street Lamps (APIO19_street_lamps)	C++17	Compilation error	0 ms	0 KiB

street_lamps

#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "streetlamp"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Street lamp:

Có n trạm dừng kết nối n + 1 cái stop.
ta biết trạng thái của cái stop

Ta có q truy vấn:
- query a b: Từ 1 đến i, ta, tổng các thời điểm mà ta có thể đi từ a b
- toggle i: lật ngược vị trí i

subtask 1: n <= 100, q <= 100. Chạy n * q^2.

subtask 2: b = a + 1.
Tức là ta chỉ quan tâm vị trí i được bật bao nhiêu lần.
cái này bỏ vào prefix sum.

subtask 3: Khi bật nút i, nó sẽ luôn bật.
Nó là bài toán dsu điển hình, tức là 2 đỉnh sẽ không bao giờ bị disconnect.

subtask 4:
Ta toggle trước xong mới đến các truy vấn.
Giả sử ta dsu rollback, khi ta thêm 1 cạnh vào, nó
sẽ liên kết các tplt bên trong đó.

Giả sử nó nối đoạn [1...3] với [4..5] thì ta thêm hình chữ nhật [1...3], [4...5]
với trọng số là thời gian t.

Khi này ta sẽ tính offline bằng sweepline. Giả sử ta cần truy vấn a, b: thì ta chỉ cần truy vấn đoạn [a, b].
Ta có n log n sự kiện thì có tối đa n log n hình chữ nhật,

subtask 5:
Bây giờ ta cần phải xử lý online. Làm thế nào cơ chứ.
Nếu ta cắm BIT2D vào thì nó cũng vẫn sẽ là N log ^ 3 N.
Ta chia các hcn thành 2 loại:
- Đã kết thúc
- Còn thời gian.
**/

const int MAXN = 3e5 + 9;
int n, q, u, v;
char lamp[MAXN];

struct query{
    string type;
    int l, r, u;
} Query[MAXN];

struct DSU{
    struct DSUnode{
        int par;
        int sz;
        int mn;
        int mx;
    };
    vector<DSUnode> D;
    vector<array<int, 6>> changes;
    int small_to_large, path_compression, roll_back;
    DSU(int sz = 0, int _small_to_large = 1, int _path_compression = 1, int _roll_back = 0){
        D.resize(sz + 9);
        small_to_large = _small_to_large;
        path_compression = _path_compression;
        roll_back = _roll_back;
        FOR(i, 0, D.size() - 1){
            D[i].par = i;
            D[i].sz = 1;
            D[i].mn = D[i].mx = i;
        }
    }

    void rollback(){
        if (changes.size() == 0) return;
        array<int, 6> tp = changes.back();
        int u = tp[0];
        int v = tp[1];
        D[u].sz -= D[v].sz;
        D[v].par = v;
        D[u].mn = tp[2], D[u].mx = tp[3];
        D[v].mn = tp[4], D[v].mx = tp[5];
        changes.pop_back();
    }
    int root(int u){
        if (D[u].par == u) return u;
        else {
            int p = root(D[u].par);
            if (path_compression) D[u].par = p;
            return p;
        }
    }

    bool unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
            if (small_to_large and D[u].sz < D[v].sz) swap(u, v);
            D[u].sz += D[v].sz;
            D[v].par = u;
            if (roll_back) changes.pb({u, v, D[u].mn, D[u].mx, D[v].mn, D[v].mx});;

            D[u].mx = max(D[u].mx, D[v].mx);
            D[u].mn = min(D[u].mn, D[v].mn);
            return true;
        }
        return false;
    }
};
namespace subtask1{
    bool check(){
        return n <= 100 and q <= 100;
    }


    DSU timelineDSU[103];
    void solve(){
        FOR(i, 1, q){
            timelineDSU[i] = DSU(n + 1);
            FOR(j, 1, n){
                if (lamp[j] == '1') {
                    timelineDSU[i].unite(j, j + 1);
                }
            }

            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                lamp[u] = ((lamp[u] == '0') ? '1' : '0');
            }
            else{
                int ans = 0;
                FOR(j, 1, i){
                    if (timelineDSU[j].root(Query[i].l) == timelineDSU[j].root(Query[i].r)) {
                        ans++;
                    }
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask2{
    bool check(){
        FOR(i, 1, q){
            if (Query[i].type == "query" and Query[i].l != Query[i].r - 1) return false;
        }
        return true;
    }

    int pre[300003], lastTime[MAXN];
    void solve(){
        FOR(i, 1, n){
            pre[i] = 0;
            if (lamp[i] == '1') lastTime[i] = 1;
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                if (lamp[u] == '1') {
                    pre[u] += i - lastTime[u] + 1;
                    lastTime[u] = 0;
                    lamp[u] = '0';
                }
                else{
                    lastTime[u] = i + 1;
                    lamp[u] = '1';
                }
            }
            if (Query[i].type == "query"){
                int ans = pre[Query[i].l];
                if (lamp[Query[i].l] == '1'){
                    ans += i - lastTime[Query[i].l] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}

namespace subtask3{
    char tmp[300005];
    bool check(){
        FOR(i, 1, n){
            tmp[i] = lamp[i];
        }
        FOR(i, 1, q){
            if (Query[i].type == "toggle" and tmp[Query[i].u] == '1') return false;
            if (Query[i].type == "toggle") tmp[Query[i].u] = '1';
        }
        return true;
    }

    /**
    Voi 2 dinh a va b, ta can tim thoi gian dau tien ma hai thang do ket hop lam 1. Cái này có thể giải bằng
    chặt nhị phân song song.

    Dùng reachability Tree.
    **/

    vector<int> reachability[MAXN * 2];
    int edgeTime[MAXN * 2];

    int P[22][MAXN * 2], depth[MAXN * 2];

    void dfs(int u, int p){
        P[0][u] = p;
        for(auto v: reachability[u]){
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    int lca(int u, int v){
        if (depth[u] < depth[v]) swap(u, v);
        FORD(i, 20, 0){
            if (P[i][u] != -1 and depth[P[i][u]] >= depth[v]) u = P[i][u];
        }

        if (u == v) return u;

        FORD(i, 20, 0){
            if (P[i][u] != -1 and P[i][v] != -1 and P[i][u] != P[i][v]) {
                u = P[i][u];
                v = P[i][v];
            }
        }

        return P[0][u];
    }

    void solve(){
        int small_to_large = 0;
        int path_compression = 1;
        int roll_back = 0;
        DSU D(2 * n + 9, small_to_large, path_compression, roll_back);
        int cntEdge = n + 1;
        FOR(i, 1, n){
            if (lamp[i] == '1') {
                ++cntEdge;
                edgeTime[cntEdge] = 1;

                int r1 = D.root(i);
                int r2 = D.root(i + 1);

                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;
                    reachability[cntEdge].pb(r2);
                }

            }

        }


        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                ++cntEdge;
                edgeTime[cntEdge] = i + 1;
                int r1 = D.root(u);
                int r2 = D.root(u + 1);
                if (D.unite(cntEdge, r1)){
//                    cerr << cntEdge << ' ' << r1 << endl;
                    reachability[cntEdge].pb(r1);
                }

                if (D.unite(cntEdge, r2)){
//                    cerr << cntEdge << ' ' << r2 << endl;

                    reachability[cntEdge].pb(r2);
                }
            }
        }

        FORD(i, 2 * n + 3, 1){
            if (P[0][i] == 0) dfs(i, -1);
        }

        FOR(i, 1, 20){
            FOR(j, 1, 2 * n + 3){
                if (P[i - 1][j] == -1) P[i][j] = -1;
                P[i][j] = P[i - 1][P[i - 1][j]];
            }
        }

        FOR(i, 1, q){
            int ans = 0;
            if (Query[i].type == "query"){
                int l = Query[i].l;
                int r = Query[i].r;
                if (D.root(l) == D.root(r)){
                    int acs = lca(l, r);
                    if (i >= edgeTime[acs]) ans += i - edgeTime[acs] + 1;
                }
                cout << ans << endl;
            }
        }
    }
}

struct BinaryIndexedTree{
    vector<int> BIT;
    BinaryIndexedTree(int sz = 0){
        BIT.resize(sz + 9);
    }

    void update(int id, int val){
        for(int i = id; i < BIT.size(); i += i & (-i)){
            BIT[i] += val;
        }
    }

    int get(int id){
        int res = 0;
        for(int i = id; i > 0; i -= i & (-i)){
            res += BIT[i];
        }
        return res;
    }

    void updateRange(int l, int r, int val){
        update(l, val);
        update(r + 1, -val);
    }
};
namespace subtask4{
    bool check(){
        bool alreadyQuery = 0;
        FOR(i, 1, q){
            if (Query[i].type == "toggle" and alreadyQuery) return false;
            if (Query[i].type == "query") alreadyQuery = true;
        }
        return true;
    }

    struct rectangle{
        int L, R, B, T, val;
        rectangle(int _L = 0, int _R = 0, int _B = 0, int _T = 0, int _v = 0){
            L = _L;
            R = _R;
            B = _B;
            T = _T;
            val = _v;
        }

    };

    vector<rectangle> rect;
    vector<iii> points;

    struct event{
        int x, type, l, r;
        event(int _x = 0, int _type = 0, int _l = 0, int _r = 0): x(_x), type(_type), l(_l), r(_r) {}
    };
    vector<int> valRectangleInclude(vector<rectangle> rect, vector<iii> points){
        vector<int> result(points.size());
        vector<event> events;
        BinaryIndexedTree BIT(300005);

        FOR(i, 0, (int) rect.size() - 1){
            events.pb(event(rect[i].L, rect[i].val, rect[i].B, rect[i].T));
            events.pb(event(rect[i].R + 1,-rect[i].val, rect[i].B, rect[i].T));
        }

        FOR(i, 0, (int) points.size() - 1){
            events.pb(event(points[i].se.fi, 0, points[i].fi, points[i].se.se));
        }

        sort(events.begin(), events.end(), [&](const event &a, const event &b){
             return a.x < b.x;
        });

        for(int i = 0, j = 0; i < events.size(); i = j){
            j = i;
            while(j < events.size() and events[j].x == events[i].x){
                if (events[j].type != 0) {
                    BIT.updateRange(events[j].l, events[j].r, events[j].type);
                }
                j++;
            }

            j = i;
            while(j < events.size() and events[j].x == events[i].x){
                 if (events[j].type == 0) {
                    result[events[j].l] = BIT.get(events[j].r);
                 }
                 j++;
            }
        }
        return result;
    }


    /**
    Moi lan ta them canh vao, ta chac no se tao 1 thanh phan lien thong moi, ta chi quan tam rang la
    2 doan ma no dang o thoi.
    Khi ta add 2 thang vao thi chac chan no se la hai thang tien de tao thanh 2 thang lon hon.
    **/

    vector<int> dsuRollback[MAXN << 2];
    DSU D;

    void addEvent(int nn, int l, int r, int u, int v, int e){
        if (l >= u and r <= v){
            dsuRollback[nn].pb(e);
            return;
        }
        if (l > v or r < u) return;
        int mid = (l + r) >> 1;
        addEvent(nn << 1, l, mid, u, v, e);
        addEvent(nn << 1 | 1, mid + 1, r, u, v, e);
    }

    void go(int nn, int l, int r){
        int sz = D.changes.size();
        for(auto p: dsuRollback[nn]){
            D.unite(p, p + 1);
            int rt = D.root(p);
            rect.pb(rectangle(D.D[rt].mn, p, p + 1, D.D[rt].mx, r - l + 1));
        }

        if (l != r){
            int mid = (l + r) >> 1;
            go(nn << 1, l, mid);
            go(nn << 1 | 1, mid + 1, r);
        }

        while(D.changes.size() > sz) D.rollback();


    }

    int lastTime[MAXN];
    void solve(){
        int startAsking = q + 1;
        FOR(i, 1, q){
            if (Query[i].type == "query") {
                startAsking = i;
                break;
            }
        }

        D = DSU(n + 1, 1, 0, 1);
        DSU current = DSU(n + 1, 1, 1, 0);

        FOR(i, 1, n){
            if (lamp[i] == '1') lastTime[i] = 1;
        }

        FOR(i, 1, startAsking - 1){
            int u = Query[i].u;
            if (lamp[u] == '1'){
                addEvent(1, 1, startAsking, lastTime[u], i, u);
                lastTime[u] = 0;
                lamp[u] = '0';
            }
            else{
                lamp[u] = '1';
                lastTime[u] = i + 1;
            }
        }

        FOR(i, 1, n){
            if (lastTime[i] > 0) addEvent(1, 1, startAsking, lastTime[i], startAsking, i);
        }

        go(1, 1, startAsking);

        FOR(i, 1, n){
            if (lamp[i] == '1') current.unite(i, i + 1);
        }


        FOR(i, startAsking, q){
            points.pb({i - startAsking, ii(Query[i].l, Query[i].r)});
        }

//        for(int i = 0; i < rect.size(); i++){
//            cerr << rect[i].val << endl;
//        }

        vector<int> result = valRectangleInclude(rect, points);

        FOR(i, startAsking, q){
            int l = Query[i].l;
            int r = Query[i].r;
            if (current.root(l) == current.root(r)){
                result[i - startAsking] += i - startAsking;
            }
            cout << result[i - startAsking] << endl;
        }


    }
}

namespace subtask5{
    int RAND(int l, int r){
        return rand() % (r - l + 1) + l;
    }
    struct TreapNode{
        int key = 0, val = 0, pr = 0, sz = 0, sum = 0;
        TreapNode *leftChild, *rightChild;

        TreapNode(int _key = 0, int _val = 0){
            key = _key;
            val = _val;
            sum = _val;
            pr = RAND(1, 3e5);
            sz = 1;
            leftChild = rightChild = NULL;
        }


    };

    typedef TreapNode* Treap;

    int getSize(Treap root){
        if (root == NULL) return 0;
        return root->sz;
    }

    int getSum(Treap root){
        if (root == NULL) return 0;
        return root->sum;

    }
    void calc(Treap root){
        if (root == NULL) return;
        root->sz = getSize(root->leftChild) + getSize(root->rightChild) + 1;
        root->sum = getSum(root->leftChild) + getSum(root->rightChild) + root->val;
    }

    void Split(Treap root, Treap &l, Treap &r, int key){
        if (root == NULL){
            l = r = NULL;
            return;
        }


        if (root->key <= key){
            l = root;
            Split(root->rightChild, l->rightChild, r, key);
        }
        else{
            r = root;
            Split(root->leftChild, l, r->leftChild, key);
        }

        calc(root);
    }

    void Merge(Treap &root, Treap l, Treap r){
        if (!l or !r) {
            root = (!l) ? r : l;
            return;
        }

        if (l->pr < r->pr) {
            Merge(l->rightChild, l->rightChild, r);
            root = l;
        }
        else {
            Merge(r->leftChild, l, r->leftChild);
            root = r;
        }

        calc(root);
    }
    bool findKey(Treap root, int key){
        if (root == NULL) return false;

        if (root->key == key) return true;
        if (root->key > key) return findKey(root->leftChild, key);
        if (root->key < key) return findKey(root->rightChild, key);
    }
    void insertKey(Treap &root, int key, int val){
        Treap res, l, r;
        Split(root, l, r, key - 1);
        Merge(l, l, new TreapNode(key, val));
        Merge(l, l, r);
        root = l;
    }

    void updateKey(Treap &root, int key, int value){
        if (root->key == key) root->val += value;

        if (root->key < key) updateKey(root->rightChild, key, value);
        if (root->key > key) updateKey(root->leftChild, key, value);

        calc(root);
    }

    void goUpdateKey(Treap &root, int key, int value){
        if (!findKey(root, key)){
            insertKey(root, key, value);
            return;
        }
        updateKey(root, key, value);
    }



    int get(Treap &root, int key){
        Treap l, r;
        Split(root, l, r, key);
        int res = getSum(l);
        Merge(l, l, r);
        root = l;
        return res;

    }

    void go(Treap root){
        if (root == NULL) return;
        go(root->leftChild);
        cerr << root->val << ' ' ;
        go(root->rightChild);
    }

    Treap segtree[MAXN << 2];

    void update(int nn, int l, int r, int L, int R, int B, int T, int val){
        if (l >= L and r <= R){
            goUpdateKey(segtree[nn], B, val);
            goUpdateKey(segtree[nn], T + 1, -val);
            return;
        }

        if (l > R or r < L) return;
        int mid = (l + r) >> 1;
        update(nn << 1, l, mid, L, R, B, T, val);
        update(nn << 1 | 1, mid + 1, r, L, R, B, T, val);
    }

    void getPoint(int nn, int l, int r, int x1, int y1, int &res){
        res +=get(segtree[nn], y1);
        if (l == r) return;

        int mid = (l + r) >> 1;

        if (x1 <= mid) getPoint(nn << 1, l, mid, x1, y1, res);
        else getPoint(nn << 1 | 1, mid + 1, r, x1, y1, res);

    }

    Treap root;
    char lamp[MAXN];

    struct Query{
        string type;
        int u, l, r;
    } Query[MAXN];

    struct BinaryIndexedTree{
        vector<int> BIT;
        BinaryIndexedTree(int sz = 0){
            BIT.resize(sz + 9, 0);
        }

        int get(int id){
            int res = 0;
            for(int i = id; i > 0; i -= i & (-i)){
                res += BIT[i];
            }
            return res;
        }

        void update(int id, int val){
            for(int i = id; i < BIT.size(); i += i & (-i)){
                BIT[i] += val;
            }
        }

        int getRange(int l, int r){
            return get(r) - get(l - 1);
        }

        int furthestLeft(int x){
            int l = 1, r = x, res = -1;
            while(l <= r){
                int mid = (l + r) >> 1;
                if (getRange(mid, x) == x - mid + 1){
                    res = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            return res;
        }

        int furthestRight(int x){
            int l = x, r = BIT.size() - 1, res = -1;
            while(l <= r){
                int mid = (l + r) >> 1;
                if (getRange(x, mid) == mid - x + 1){
                    res = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            return res;
        }
        //get(l - 1) + l + 1 == get(r) - r. Tìm vị trí 1 đầu tiên thỏa.
    };

    void solve(){

        BinaryIndexedTree BIT(n);
        FOR(i, 1, n){
            if (lamp[i] == '1') {
                BIT.update(i, 1);
                int l = BIT.furthestLeft(i);
    //            cout << l << ' ' << i << endl;
                update(1, 1, n, l, i, i, i, -1);
            }
        }



        FOR(i, 1, q){
            if (Query[i].type == "toggle"){
                int u = Query[i].u;
                if (lamp[u] == '0'){
                    lamp[u] = '1';
                    BIT.update(u, 1);
                    int L = BIT.furthestLeft(u);
                    int R = BIT.furthestRight(u);
    //                cout<< L << ' ' << u << ' ' << u << ' '<< R << ' ' << -(i + 1) << endl;
                    update(1, 1, n, L, u, u, R, -(i + 1));
                    int res = 0;
                    getPoint(1, 1, n, 1, 5, res);
    //                cout << res << endl;
                }
                else{
                    lamp[u] = '0';
                    int L = BIT.furthestLeft(u);
                    int R = BIT.furthestRight(u);
                    update(1, 1, n, L, u, u, R, +i + 1);
                    BIT.update(u, -1);
                }
            }
            else{
                int l = Query[i].l;
                int r = Query[i].r - 1;
                int res = 0;
                getPoint(1, 1, n, l, r, res);
                if (lamp[l] == '1' and lamp[r] == '1' and BIT.furthestRight(l) >= r){
                    res += i + 1;
                }
                cout << res << endl;
            }
        }

    }

}
main()
{
    fast;
    srand(time(NULL));
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".trau.out","w",stdout);
    }
    cin >> n >> q;
    FOR(i, 1, n){
        cin >> lamp[i];
    }
    FOR(i, 1, q){
        cin >> Query[i].type;
        if (Query[i].type == "toggle"){
            cin >> Query[i].u;

        }
        else if (Query[i].type == "query"){
            cin >> Query[i].l >> Query[i].r;
        }
    }

    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;
    if (subtask4::check()) return subtask4::solve(), 0;
    if (subtask5::check()) return subtask5::solve(), 0;
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message (stderr)

street_lamps.cpp: In constructor 'DSU::DSU(int, int, int, int)':
street_lamps.cpp:9:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DSU::DSUnode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
   83 |         FOR(i, 0, D.size() - 1){
      |             ~~~~~~~~~~~~~~~~~~   
street_lamps.cpp:83:9: note: in expansion of macro 'FOR'
   83 |         FOR(i, 0, D.size() - 1){
      |         ^~~
street_lamps.cpp: In member function 'void BinaryIndexedTree::update(int, int)':
street_lamps.cpp:330:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  330 |         for(int i = id; i < BIT.size(); i += i & (-i)){
      |                         ~~^~~~~~~~~~~~
street_lamps.cpp: In function 'std::vector<int> subtask4::valRectangleInclude(std::vector<subtask4::rectangle>, std::vector<std::pair<int, std::pair<int, int> > >)':
street_lamps.cpp:395:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  395 |         for(int i = 0, j = 0; i < events.size(); i = j){
      |                               ~~^~~~~~~~~~~~~~~
street_lamps.cpp:397:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  397 |             while(j < events.size() and events[j].x == events[i].x){
      |                   ~~^~~~~~~~~~~~~~~
street_lamps.cpp:405:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<subtask4::event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  405 |             while(j < events.size() and events[j].x == events[i].x){
      |                   ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void subtask4::go(int, int, int)':
street_lamps.cpp:450:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 6> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  450 |         while(D.changes.size() > sz) D.rollback();
      |               ~~~~~~~~~~~~~~~~~^~~~
street_lamps.cpp: In function 'void subtask5::insertKey(subtask5::TreapNode*&, int, int)':
street_lamps.cpp:601:15: warning: unused variable 'res' [-Wunused-variable]
  601 |         Treap res, l, r;
      |               ^~~
street_lamps.cpp: In member function 'void subtask5::BinaryIndexedTree::update(int, int)':
street_lamps.cpp:693:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  693 |             for(int i = id; i < BIT.size(); i += i & (-i)){
      |                             ~~^~~~~~~~~~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:781:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  781 | main()
      | ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:808:19: error: 'check' is not a member of 'subtask5'
  808 |     if (subtask5::check()) return subtask5::solve(), 0;
      |                   ^~~~~
street_lamps.cpp:808:19: note: suggested alternatives:
street_lamps.cpp:127:10: note:   'subtask1::check'
  127 |     bool check(){
      |          ^~~~~
street_lamps.cpp:160:10: note:   'subtask2::check'
  160 |     bool check(){
      |          ^~~~~
street_lamps.cpp:199:10: note:   'subtask3::check'
  199 |     bool check(){
      |          ^~~~~
street_lamps.cpp:349:10: note:   'subtask4::check'
  349 |     bool check(){
      |          ^~~~~
street_lamps.cpp: In function 'bool subtask5::findKey(subtask5::Treap, int)':
street_lamps.cpp:599:5: warning: control reaches end of non-void function [-Wreturn-type]
  599 |     }
      |     ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:786:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  786 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:787:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  787 |         freopen(TASKNAME".trau.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~