Submission #893754

#	Time	Username	Problem	Language	Result	Execution time	Memory
893754		vjudge1	Segments (IZhO18_segments)	C++17	0 / 100	67 ms	27200 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;

#define Node int
#define at(i) find_by_order(i)
#define which(x) order_of_key(x)
#define SET tree<Node, null_type,less<Node>, rb_tree_tag,tree_order_statistics_node_update>

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

const int N = 4e5 + 5 ;

struct Fenwick {
   vector<int> t ;
   int n;
   Fenwick(int len) {
      n = len ;
      t.assign(n + 1, 0) ;
   }
   void upd(int i, ll x) {
      while (i <= n) {
         t[i] += x;
         i += (i & (-i)) ;
      }
   }
   ll get(int i) {
      ll sum = 0 ;
      while (i) {
         sum += t[i] ;
         i -= (i & (-i)) ;
      }
      return sum ;
   }
   ll get(int l, int r) {
      return get(r) - get(l - 1) ;
   }
};

Fenwick _l(N), _r(N) ;
int n , t, idx = 0, last = 0, sz = 0 ;
pair<int,int> p[N] ;
SET L, R ;
map<pair<int,int>,int> cnt ;

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

void remove(int i) {
    sz-- ;
    auto [l, r] = p[i] ;
    cnt[{l, r}]-- ;
    _l.upd(l, -1) ;
    _r.upd(r, -1) ;
    if (cnt[{l, r}] == 0) {
        L.erase(l) ;
        R.erase(r) ;
        cnt.erase({l, r}) ;
    }
}

int query(int lo, int hi, int k) {
    int mn = lo + k - 2 ;
    int l = 0 , r = R.size() - 1 ;
    while (l < r) {
        int m = (l + r + 1) / 2;
        int cur = *R.at(m) ;
        if (cur > mn) r = m - 1 ;
        else l = m ;
    }
    int x = *R.at(l) ;
    int mx = hi - k + 2 ;
    l = 0 , r = L.size() - 1 ;
    while (l < r) {
        int m = (l + r) / 2;
        int cur = *L.at(m) ;
        if (cur < mx) l = m + 1 ;
        else r = m ;
    }
    int y = *L.at(r) ;
    int ret = sz ;
    if (x <= mn) ret -= _r.get(mn) ;
    if (y >= mx) ret -= _l.get(mx, 400000) ;
    last = ret ;
    return ret ;
}

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cin >> n >> t ;
    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