#include <bits/stdc++.h>
#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;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
const ll inf = 3e18;
int buben = 1;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
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;
int WD[N + 3];
int Wstn;
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){
clr(v << 1, tl, ((tl + tr) >> 1));
clr((v << 1) + 1, ((tl + tr) >> 1) + 1, tr);
}
}
int luk, ruk;
void build(int v, int tl, int tr){
if(tl == tr){
V[v].p_b(a[tl].se);
V1[v].p_b(a[tl].se - a[tl].fi + 1);
}else{
build(v << 1, tl, ((tl + tr) >> 1));
build((v << 1) + 1, ((tl + tr) >> 1) + 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]);
luk++;
}
while(ruk < V[(v << 1) + 1].size()){
V[v].p_b(V[(v << 1) + 1][ruk]);
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]);
luk++;
}
while(ruk < V1[(v << 1) + 1].size()){
V1[v].p_b(V1[(v << 1) + 1][ruk]);
ruk++;
}
}
}
struct qry{
short t;
int 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());
}
return V_more(v << 1, tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1))) + V_more((v << 1) + 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 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());
}
return V1_more(v << 1, tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1))) + V1_more((v << 1) + 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 1), r);
}
int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
int n, t;
cin >> n >> t;
//while(sqr(buben) < n)buben++;
buben = 2501;
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){
Wstn = 0;
for(int j = i; j <= min(n, i + buben - 1); j++){
if(c[j].t == 2){
will_deleted[c[j].a] = 1;
if(c[j].a <= Stn){
Wstn++;
WD[Wstn] = c[j].a;
}
}
}
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;
will_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 || c[i].c == 0)ans++;
}
for(int j = 1; j <= Wstn; j++)if(!f_deleted[WD[j]]){
if(min(c[i].b, c[WD[j]].b) - max(c[i].a, c[WD[j]].a) + 1 >= c[i].c || c[i].c == 0)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 R = mid;
}
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 R = mid;
}
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:63: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:63: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:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V[v << 1].size()){
~~~~^~~~~~~~~~~~~~~~~~
segments.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ruk < V[(v << 1) + 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:85: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:85: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:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(luk < V1[v << 1].size()){
~~~~^~~~~~~~~~~~~~~~~~~
segments.cpp:100: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:153: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:153: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:153: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 |
37980 KB |
Output is correct |
| 2 |
Correct |
38 ms |
38008 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
38136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1066 ms |
56536 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
243 ms |
42232 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
220 ms |
42360 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
37980 KB |
Output is correct |
| 2 |
Correct |
38 ms |
38008 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
38136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
37980 KB |
Output is correct |
| 2 |
Correct |
38 ms |
38008 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
38136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
