#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
const ll inf = 3e18;
int buben = 1000;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> void vout(T s){cout << s << endl;exit(0);}
vector <int> V[4 * N + 3], V1[4 * N + 3];
pii a[N + 3];
int stn;
pii b[N + 3];
int Stn;
bool f_deleted[N + 3], will_deleted[N + 3];
void clr(int v, int tl, int tr){
V[v].clear();
V1[v].clear();
if(tl != tr){
int tm = (tl + tr) >> 1;
clr(v << 1, tl, tm);
clr((v << 1) + 1, tm + 1, tr);
}
}
int luk, ruk;
void build(int v, int tl, int tr){
if(tl == tr){
V[v].p_b(a[tl - 1].se);
V1[v].p_b(a[tl - 1].se - a[tl - 1].fi + 1);
}else{
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm);
build((v << 1) + 1, tm + 1, tr);
luk = 0;
ruk = 0;
while(luk < V[v << 1].size() && ruk < V[(v << 1) + 1].size()){
if(V[v << 1][luk] < V[(v << 1) + 1][ruk]){
V[v].p_b(V[v << 1][luk]);
luk++;
}else{
V[v].p_b(V[(v << 1) + 1][ruk]);
ruk++;
}
}
while(luk < V[v << 1].size()){
V[v].p_b(V[v << 1][luk]);
}
while(ruk < V[(v << 1) + 1].size()){
V[v].p_b(V[(v << 1) + 1][ruk]);
}
luk = 0;
ruk = 0;
while(luk < V1[v << 1].size() && ruk < V1[(v << 1) + 1].size()){
if(V1[v << 1][luk] < V1[(v << 1) + 1][ruk]){
V1[v].p_b(V1[v << 1][luk]);
luk++;
}else{
V1[v].p_b(V1[(v << 1) + 1][ruk]);
ruk++;
}
}
while(luk < V1[v << 1].size()){
V1[v].p_b(V1[v << 1][luk]);
}
while(ruk < V1[(v << 1) + 1].size()){
V1[v].p_b(V1[(v << 1) + 1][ruk]);
}
}
}
struct qry{
int t, a, b, c, Id;
};
int val;
int V_more(int v, int tl, int tr, int l, int r){
if(l > r)return 0;
if(tl == l && tr == r){
return (int)V[v].size() - (lower_bound(all(V[v]), val) - V[v].begin());
}
int tm = (tl + tr) >> 1;
return V_more(v << 1, tl, tm, l, min(r, tm)) + V_more((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r);
}
int V1_more(int v, int tl, int tr, int l, int r){
if(l > r)return 0;
if(tl == l && tr == r){
return (int)V1[v].size() - (lower_bound(all(V1[v]), val) - V1[v].begin());
}
int tm = (tl + tr) >> 1;
return V1_more(v << 1, tl, tm, l, min(r, tm)) + V1_more((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r);
}
int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
int n, t;
cin >> n >> t;
//while(sqr(buben) < n)buben++;
vector <qry> c(n + 1);
for(int i = 1; i <= n; i++){
cin >> c[i].t;
if(c[i].t == 1){
cin >> c[i].a >> c[i].b;
}else if(c[i].t == 2){
cin >> c[i].a;
}else{
cin >> c[i].a >> c[i].b >> c[i].c;
}
}
int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k;
for(int i = 1; i <= n; i++){
if(i % buben == 0){
for(int j = i; j <= min(n, i + buben - 1); j++){
if(c[j].t == 2){
will_deleted[c[j].a] = 1;
}
}
if(stn){
clr(1, 1, stn);
}
stn = 0;
for(int j = 1; j <= Stn; j++)if(!will_deleted[j]){
stn++;
a[stn] = b[j];
}
if(stn){
sort(a + 1, a + stn + 1);
build(1, 1, stn);
}
l = i;
}
if(c[i].t == 1){
c[i].a ^= t * last_ans;
c[i].b ^= t * last_ans;
if(c[i].a > c[i].b)swap(c[i].a, c[i].b);
Stn++;
c[i].Id = Stn;
b[Stn] = {c[i].a, c[i].b};
}else if(c[i].t == 2){
f_deleted[c[i].a] = 1;
}else if(c[i].t == 3){
c[i].a ^= t * last_ans;
c[i].b ^= t * last_ans;
if(c[i].a > c[i].b)swap(c[i].a, c[i].b);
if(c[i].b - c[i].a + 1 < c[i].c){
cout << "0\n";
last_ans = 0;
continue;
}
ans = 0;
k = c[i].c;
for(int j = l; j < i; j++)if(c[j].t == 1 && !f_deleted[c[j].Id]){
if(min(c[i].b, c[j].b) - max(c[i].a, c[j].a) + 1 >= c[i].c)ans++;
}
if(!k)ans += stn;
else{
if(stn){
L = 1, R = stn;
while(L < R){
mid = (L + R) >> 1;
if(a[mid].fi < c[i].a)L = mid + 1; else mid = R;
}
if(a[L].fi < c[i].a)L++;
if(L != 1){
val = k + c[i].a - 1;
ans += V_more(1, 1, stn, 1, L - 1);
}
Le = L;
L = 1, R = stn;
while(L < R){
mid = (L + R) >> 1;
if(a[mid].fi < c[i].b - k + 1)L = mid + 1; else mid = R;
}
if(a[L].fi < c[i].b - k + 1)L++;
if(Le < L){
val = k;
ans += V1_more(1, 1, stn, Le, L - 1);
}
}
}
cout << ans << "\n";
last_ans = ans;
}
}
return 0;
}
Compilation message
segments.cpp: In function 'void build(int, int, int)':
segments.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V[v << 1].size() && ruk < V[(v << 1) + 1].size()){
~~~~^~~~~~~~~~~~~~~~~~
segments.cpp:68:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V[v << 1].size() && ruk < V[(v << 1) + 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V[v << 1].size()){
~~~~^~~~~~~~~~~~~~~~~~
segments.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ruk < V[(v << 1) + 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V1[v << 1].size() && ruk < V1[(v << 1) + 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~
segments.cpp:88:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V1[v << 1].size() && ruk < V1[(v << 1) + 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V1[v << 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~
segments.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ruk < V1[(v << 1) + 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:154:43: warning: unused variable 'Ri' [-Wunused-variable]
int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k;
^~
segments.cpp:154:47: warning: unused variable 'L1' [-Wunused-variable]
int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k;
^~
segments.cpp:154:51: warning: unused variable 'R1' [-Wunused-variable]
int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 2 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 3 |
Runtime error |
91 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 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 |
120 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 |
123 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 |
38 ms |
37880 KB |
Output is correct |
| 2 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 3 |
Runtime error |
91 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 2 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 3 |
Runtime error |
91 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
