Submission #893773

#	Time	Username	Problem	Language	Result	Execution time	Memory
893773		vjudge1	Segments (IZhO18_segments)	C++17	0 / 100	180 ms	65536 KiB

segments

// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std ;
using ll = long long ;
using ld = long double ;


struct Node {
    Node *l = nullptr;
    Node *r = nullptr;
    int left;
    int right;
    int nsum;
    Node(){}
    Node(int lo, int hi, int val) : left(lo), right(hi), nsum(val) {}

    void add(int pos, int val) {
        if (pos < left || pos > right) {
            return;
        }
        nsum += val;
        if (right - left == 1) {
            return;
        }
        int mid = (left + right) / 2;
        if (pos < mid) {
            if (l == nullptr) {
                l = new Node(left, mid, 0);
            }
            l->add(pos, val);
        } else {
            if (r == nullptr) {
                r = new Node(mid + 1, right, 0);
            }
            r->add(pos, val);
        }
    }

    int get(int from, int to) {
        if (to < left || right < from) {
            return 0;
        }
        if (from <= left && right <= to) {
            return nsum;
        }
        return (l ? l->get(from, to) : 0) + (r ? r->get(from, to) : 0);
    }
};

Node _l, _r ;

int n , t, idx = 0, last = 0, sz = 0 ;
vector<pair<int,int>> p ;

void insert(int l ,int r) {
    sz++ ;
    p[++idx] = {l, r} ;
    _l.add(l, 1) ;
    _r.add(r, 1) ;
}

void remove(int i) {
    sz-- ;
    auto [l, r] = p[i] ;
    _l.add(l, -1) ;
    _r.add(r, -1) ;
}

int query(int lo, int hi, int k) {
    int mn = lo + k - 1 ;
    int mx = hi - k + 1 ;
    int ret = sz ;
    ret -= _l.get(mx- 2 , 2000000000) ;
    ret -= _r.get(0, mn) ;
    last = ret ;
//    dbg(lo, hi, k, ret) ;
    return ret ;
}

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cin >> n >> t ;
    _l = Node(0, 2000000001, 0) ;
    _r = Node(0, 2000000001, 0) ;
    p.resize(n + 5) ;
    for (int i = 0 ; i < n ; i++) {
        int cmd ; cin >> cmd ;
        if (cmd == 1) {
            int a , b; cin >> a >> b ;
            int l = (a ^ (t * last)) ;
            int r = (b ^ (t * last)) ;
            if (l > r) swap(l, r) ;
            insert(l, r) ;
        } else if (cmd == 2) {
            int ind ; cin >> ind ;
            remove(ind) ;
        } else {
            int a , b, k ; cin >> a >> b >> k ;
            int l = (a ^ (t * last)) ;
            int r = (b ^ (t * last)) ;
            if (l > r) swap(l, r) ;
            cout << query(l, r, k) << "\n" ;
        }
    }
    return 0 ;
}

// 希望白银

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25