#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define lft(x) x * 2
#define rgt(x) x * 2 + 1
#define tm hui_pizda
#define ft first
#define sd second
#define pb push_back
#define pf push_front
#define sz size()
#define cnt continue
#define m_p make_pair
#define fr(i, l, r) for(int i = l; i <= r; ++ i)
#define rf(i, r, l) for(int i = r; i >= l; -- i)
#pragma GCC optimize(-O3)
#pragma GCC optimize(Ofast)
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef vector <ll> vl;
typedef vector <pll> vpl;
mt19937_64 rnd(time(NULL));
const ll N = 10;
const ll mtrxN = 10;
const ll oo = 2000000000;
//const ll oo = 228;
const ll B = 500;
const ll mod = 1e9 + 7;
struct mtrx{
ll m[mtrxN][mtrxN] = {};
};
mtrx mtrx_mult(mtrx a, mtrx b){
mtrx c;
fr(i, 0, mtrxN - 1){
fr(j, 0, mtrxN - 1){
ll sum = 0;
fr(x, 0, mtrxN - 1){
sum += a.m[i][x] * b.m[x][j];
sum %= mod;
}
c.m[i][j] = sum;
}
}
return c;
}
mtrx mtrx_pow(mtrx a, ll n){
mtrx res;
fr(i, 0, mtrxN - 1)fr(j, 0, mtrxN - 1)res.m[i][j] = a.m[i][j];
n --;
while(n){
if(n&1)res = mtrx_mult(res, a);
a = mtrx_mult(a, a);
n >>= 1;
}
return res;
}
ll _pow(ll a, ll n){
ll r = 1;
while(n){
if(n&1)r = r * a % mod;
a = a * a % mod;
n >>= 1;
}
return r;
}
ll div(ll x, ll y, ll md){
return x * _pow(y, md - 2) % md;
}
ll _gcd(ll x, ll y){
if(x == 0)return y;
if(y == 0)return x;
return __gcd(x, y);
}
struct SegmentTreeSet{
struct node{
_set <pll> s;
_set <pll> d;
ll l = -1;
ll r = -1;
} emp;
vector <node> t;
void add_root(){
t.pb(emp);
}
void ins(ll p, ll v, ll id, ll nw = 0, ll l = 0, ll r = oo){
//cout << "p = " << p << " v = " << v << " id = " << id << " nw = " << nw << " l = " << l << " r = " << r << " t.sz = " << t.sz<< endl;
t[nw].s.insert({v, id});
t[nw].d.insert({v - p + 1, id});
if(l != r){
ll c = (l + r) / 2;
if(p <= c){
if(t[nw].l == -1){
t[nw].l = t.sz;
t.pb(emp);
}
ins(p, v, id, t[nw].l, l, c);
} else {
if(t[nw].r == -1){
t[nw].r = t.sz;
t.pb(emp);
}
ins(p, v, id, t[nw].r, c + 1, r);
}
}
}
void ers(ll p, ll v, ll id, ll nw = 0, ll l = 0, ll r = oo){
//cout << "p = " << p << " v = " << v << " id = " << id << " nw = " << nw << " l = " << l << " r = " << r << " t.sz = " << t.sz<< endl;
t[nw].s.erase({v, id});
t[nw].d.erase({v - p + 1, id});
if(l != r){
ll c = (l + r) / 2;
if(p <= c){
if(t[nw].l == -1){
t[nw].l = t.sz;
t.pb(emp);
}
ers(p, v, id, t[nw].l, l, c);
} else {
if(t[nw].r == -1){
t[nw].r = t.sz;
t.pb(emp);
}
ers(p, v, id, t[nw].r, c + 1, r);
}
}
}
ll get1(ll l, ll r, ll k, ll nw = 0, ll tl = 0, ll tr = oo){
if(l > r)return 0;
if(tl == l && tr == r){
pll p = {k, 0};
return t[nw].s.sz - t[nw].s.order_of_key(p);
}
ll c = (tl + tr) / 2;
if(t[nw].l == -1){
t[nw].l = t.sz;
t.pb(emp);
}
if(t[nw].r == -1){
t[nw].r = t.sz;
t.pb(emp);
}
return get1(l, min(r, c), k, t[nw].l, tl, c) + get1(max(l, c + 1), r, k, t[nw].r, c + 1, tr);
}
ll get2(ll l, ll r, ll k, ll nw = 0, ll tl = 0, ll tr = oo){
if(l > r)return 0;
if(tl == l && tr == r){
pll p = {k, 0};
return t[nw].d.sz - t[nw].d.order_of_key(p);
}
ll c = (tl + tr) / 2;
if(t[nw].l == -1){
t[nw].l = t.sz;
t.pb(emp);
}
if(t[nw].r == -1){
t[nw].r = t.sz;
t.pb(emp);
}
return get2(l, min(r, c), k, t[nw].l, tl, c) + get2(max(l, c + 1), r, k, t[nw].r, c + 1, tr);
}
};
pll ls[2000001];
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
ll T, t, lastans = 0, now = 1, wn = 0;
cin >> T >> t;
SegmentTreeSet tree;
tree.add_root();
while(T --){
ll tp, a, b, l, r, id, k;
cin >> tp;
if(tp == 1){
wn ++;
cin >> a >> b;
l = a ^ (lastans * t);
r = b ^ (lastans * t);
//???
if(l > r)swap(l, r);
//cout << "ins l..r " << l << ' ' << r << endl;
ls[now] = {l, r};
tree.ins(l, r, now);
now ++;
}
if(tp == 2){
wn --;
cin >> id;
//cout << "del l..r" << ls[id].ft << ' ' << ls[id].sd << endl;
tree.ers(ls[id].ft, ls[id].sd, id);
}
if(tp == 3){
cin >> a >> b >> k;
if(k == 0){
cout << wn << "\n";
cnt;
}
l = a ^ (lastans * t);
r = b ^ (lastans * t);
//???
if(l > r)swap(l, r);
//cout << "ask: "<< l << ' ' << r << ' ' << k << endl;
//cout << "get1 = " << tree.get1(1, l, l + k) << " get2 = " << tree.get2(l + 1, r, k) << endl;
lastans = tree.get1(1, l, l + k - 1) + tree.get2(l + 1, r, k);
//cout << " ";
cout << lastans << "\n";
}
}
return 0;
}
/*
5 0
1 1 1
1 1 1
1 3 3
1 3 3
3 2 2 0
*/
Compilation message
segments.cpp:17:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
#pragma GCC optimize(-O3)
^
segments.cpp:18:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
#pragma GCC optimize(Ofast)
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Runtime error |
126 ms |
51808 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
267 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
181 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
183 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Runtime error |
126 ms |
51808 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Runtime error |
126 ms |
51808 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 4 |
Halted |
0 ms |
0 KB |
- |
