// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>
#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif
using namespace std ;
using ll = long long ;
using ld = long double ;
/**
* Description: Does not allocate storage for nodes with no data
* Source: USACO Mowing the Field
* Verification: ~
*/
#define int ll
const int SZ = 4e9 + 5;
template<class T> struct node {
T val = 0; node<T>* c[2];
node() { c[0] = c[1] = NULL; }
void upd(int ind, T v, int L = 0, int R = SZ-1) { // add v
if (L == ind && R == ind) { val += v; return; }
int M = (L+R)/2;
if (ind <= M) {
if (!c[0]) c[0] = new node();
c[0]->upd(ind,v,L,M);
} else {
if (!c[1]) c[1] = new node();
c[1]->upd(ind,v,M+1,R);
}
val = 0; for (int i = 0 ; i < 2 ; i++) if (c[i]) val += c[i]->val;
}
T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
if (hi < L || R < lo) return 0;
if (lo <= L && R <= hi) return val;
int M = (L+R)/2; T res = 0;
if (c[0]) res += c[0]->query(lo,hi,L,M);
if (c[1]) res += c[1]->query(lo,hi,M+1,R);
return res;
}
void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
if (L != R) {
int M = (L+R)/2;
if (ind <= M) {
if (!c[0]) c[0] = new node();
c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M);
} else {
if (!c[1]) c[1] = new node();
c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R);
}
}
val = (c0?c0->val:0)+(c1?c1->val:0);
}
};
node<int> _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.upd(l, 1) ;
_r.upd(r, 1) ;
// cout << "add = " << l << ' ' << r << '\n' ;
}
void remove(int i) {
sz-- ;
auto [l, r] = p[i] ;
_l.upd(l, -1) ;
_r.upd(r, -1) ;
// cout << "del = " << l << ' ' << r << '\n' ;
}
int query(int lo, int hi, int k) {
if (!sz || hi - lo + 1 < k) {
last = 0 ;
return 0 ;
}
int mn = lo + k - 2 ;
int mx = hi - k + 2 ;
int ret = sz ;
// dbg(mn, mx, _l.get(mx, 20000000002), _r.get(0, mn + 2)) ;
mx = max(mx, 0ll) ;
ret -= _l.query(mx , 3e9) ;
ret -= _r.query(1, mn) ;
last = ret ;
return ret ;
}
int32_t main() {
ios::sync_with_stdio(false) ;
cin.tie(nullptr) ;
cin >> n >> t ;
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 ;
}
// 希望白银
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2908 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
147 ms |
55708 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
120 ms |
41048 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
41296 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2908 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2908 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
