#include<bits/stdc++.h>
using namespace std;
#define int long long
int N = 1<<30;
int M = 1<<24;
vector<array<int, 2>> down(M, {-1, -1});
int c = 1;
vector<int> bit(M, 0);
void update(int curr, int l, int r, int cl, int cr)
{
if (cr < l || cl > r) return;
if (l <= cl && cr <= r)
{
bit[curr] = cr-cl+1;
return;
}
if (down[curr][1]==-1)
{
down[curr][0] = ++c;
down[curr][1] = ++c;
}
int subl = down[curr][0];
int subr = down[curr][1];
if(bit[curr] == cr-cl+1)
{
bit[subl] = (cr-cl+1)/2;
bit[subr]=(cr-cl+1)/2;
}
int m = (cl+cr)/2;
update(subl, l, r, cl, m);
update(subr, l, r, m+1, cr);
bit[curr] = bit[subl]+bit[subr];
return;
}
int query(int curr, int l, int r, int cl, int cr)
{
if (cr < l || cl > r) return 0;
if (l <= cl && cr <= r) return bit[curr];
if (down[curr][1]==-1)
{
down[curr][0] = ++c;
down[curr][1] = ++c;
}
int subl = down[curr][0];
int subr = down[curr][1];
if(bit[curr] == cr-cl+1)
{
bit[subl] = (cr-cl+1)/2;
bit[subr]=(cr-cl+1)/2;
}
int m = (cl+cr)/2;
int sol = 0;
sol += query(subl, l, r, cl, m);
sol += query(subr, l, r, m+1, cr);
return sol;
}
int32_t main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int q;
cin >> q;
int last = 0;
for (int i = 0; i < q; i++)
{
int a, b, c;
cin >> a >> b >> c;
b--; c--;
b+=last;
c+=last;
if (a==2)
{
update(1, b, c, 0, N-1);
}
else
{
last = query(1, b, c, 0, N-1);
cout << last << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
83 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
