#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int N=1e5, INF=1e9;
int cur=2;
vector<int> ki(2), ka(2);
vector<bool> st(2);
void upd(int ql, int qr, int l, int r, int idx){
if(l>qr || r<ql) return;
if(l>=ql && r<=qr){
st[idx]=true;
return;
}
int mid=(l+r)/2;
if(ki[idx]==0){
ki[idx]=cur++;
ki.push_back(0);
ka.push_back(0);
st.push_back(0);
}
if(ka[idx]==0){
ka[idx]=cur++;
ki.push_back(0);
ka.push_back(0);
st.push_back(0);
}
upd(ql, qr, l, mid, ki[idx]);
upd(ql, qr, mid+1, r, ka[idx]);
}
int query(int ql, int qr, int l, int r, int idx){
if(l>qr || r<ql) return 0;
if(st[idx]) return min(qr, r)-max(ql, l)+1;
int mid=(l+r)/2, ret=0;
if(ki[idx]!=0) ret+=query(ql, qr, l, mid, ki[idx]);
if(ka[idx]!=0) ret+=query(ql, qr, mid+1, r, ka[idx]);
return ret;
}
int main(){
fast();
int m, type, l, r, c=0; cin>>m;
while(m--){
cin>>type>>l>>r;
if(type==1){
c=query(l+c, r+c, 1, INF, 1);
cout<<c<<'\n';
}
else upd(l+c, r+c, 1, INF, 1);
}
}
/*
#define int long
const int N=1e6;
int a[N+1], st[4*N+1];
void build(int l, int r, int idx){
if(l==r){
st[idx]=a[l];
return;
}
int mid=(l+r)/2;
build(l, mid, 2*idx);
build(mid+1, r, 2*idx+1);
st[idx]=st[2*idx]+st[2*idx+1];
}
void upd(int l, int r, int idx, int k, int v){
if(l==r){
st[idx]+=v;
return;
}
int mid=(l+r)/2;
if(k<=mid) upd(l, mid, 2*idx, k, v);
else upd(mid+1, r, 2*idx+1, k, v);
st[idx]=st[2*idx]+st[2*idx+1];
}
int query(int ql, int qr, int l, int r, int idx){
if(l>=ql && r<=qr) return st[idx];
if(l>qr || r<ql) return 0ll;
int mid=(l+r)/2;
return query(ql, qr, l, mid, 2*idx)+query(ql, qr, mid+1, r, 2*idx+1);
}
signed main(){
fast();
int n; cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
build(1, n, 1);
char type;
int q, l, r; cin>>q;
while(q--){
cin>>type>>l>>r;
if(type=='q') cout<<query(l, r, 1, n, 1)<<'\n';
else upd(1, n, 1, l, r);
}
}
*/
/*
const int N=5e4+5;
int a[N];
struct Node{
int pref, suff, sum, ans;
Node(){}
Node(int val){
pref=val, suff=val, sum=val, ans=val;
}
bool operator==(Node other) const {
return pref==other.pref && suff==other.suff && sum==other.sum && ans==other.ans;
}
};
Node tree[4*N];
const Node invaldi=Node(-1e9);
Node merge(Node ki, Node ka){
if(ki==invaldi) return ka;
if(ka==invaldi) return ki;
Node ret=Node(0);
ret.pref=max(ki.pref, ki.sum+ka.pref);
ret.suff=max(ka.suff, ki.suff+ka.sum);
ret.sum=ki.sum+ka.sum;
ret.ans=max({ki.suff+ka.pref, ki.ans, ka.ans});
return ret;
}
void build(int l, int r, int idx){
if(l==r){
tree[idx]=Node(a[l]);
return;
}
int mid=(l+r)/2;
build(l, mid, 2*idx);
build(mid+1, r, 2*idx+1);
tree[idx]=merge(tree[2*idx], tree[2*idx+1]);
}
void upd(int l, int r, int idx, int k, int v){
if(l==r){
tree[idx]=Node(v);
return;
}
int mid=(l+r)/2;
if(k<=mid) upd(l, mid, 2*idx, k, v);
else upd(mid+1, r, 2*idx+1, k, v);
tree[idx]=merge(tree[2*idx], tree[2*idx+1]);
}
Node query(int ql, int qr, int l, int r, int idx){
if(l>qr || r<ql) return invaldi;
if(l>=ql && r<=qr) return tree[idx];
int mid=(l+r)/2;
return merge(query(ql, qr, l, mid, 2*idx), query(ql, qr, mid+1, r, 2*idx+1));
}
int main(){
fast();
int n; cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
build(1, n, 1);
int q, type, l, r, v; cin>>q;
while(q--){
cin>>l>>r;
cout<<query(l, r, 1, n, 1).ans<<'\n';
}
}
*/
/*
const int N=2e5, INF=2e9;
int timer=1, a[N+1], in[N+1], out[N+1], lev[N+1];
vector<vector<int>> v(N+1);
vector<pair<int,int>> val(N+1), st[4*N+1];
void dfs(int node, int p){
in[node]=timer;
val[timer++]={lev[node], a[node]};
for(auto i:v[node]){
if(i==p) continue;
lev[i]=lev[node]+1;
dfs(i, node);
}
out[node]=timer-1;
}
void build(int l, int r, int idx){
if(l==r){
st[idx].push_back(val[l]);
return;
}
int mid=(l+r)/2;
build(l, mid, 2*idx);
build(mid+1, r, 2*idx+1);
int i=0, j=0, sz1=st[2*idx].size(), sz2=st[2*idx+1].size();
while(i<sz1 && j<sz2){
if(st[2*idx][i]<st[2*idx+1][j]) st[idx].push_back(st[2*idx][i++]);
else st[idx].push_back(st[2*idx+1][j++]);
}
while(i<sz1) st[idx].push_back(st[2*idx][i++]);
while(j<sz2) st[idx].push_back(st[2*idx+1][j++]);
}
void build_pref(int l, int r, int idx){
if(l==r){
return;
}
int mid=(l+r)/2;
build_pref(l, mid, 2*idx);
build_pref(mid+1, r, 2*idx+1);
int sz=st[idx].size();
for(int i=1; i<sz; i++){
st[idx][i].second=min(st[idx][i-1].second, st[idx][i].second);
}
}
int getMin(int idx, int k){
pair<int,int> temp={k, INF};
int id=upper_bound(st[idx].begin(), st[idx].end(), temp)-st[idx].begin();
id--;
if(id==-1) return INF;
return st[idx][id].second;
}
int query(int ql, int qr, int l, int r, int idx, int k){
if(l>qr || r<ql) return INF;
if(l>=ql && r<=qr){
return getMin(idx, k);
}
int mid=(l+r)/2;
return min(query(ql, qr, l, mid, 2*idx, k), query(ql, qr, mid+1, r, 2*idx+1, k));
}
int main(){
fast();
int n, r; cin>>n>>r;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<n; i++){
int x, y; cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(r, 0);
build(1, n, 1);
build_pref(1, n, 1);
int ans=0, x, k, q;
cin>>q;
while(q--){
cin>>x>>k;
x=(ans+x)%n+1;
k=(ans+k)%n;
ans=query(in[x], out[x], 1, n, 1, lev[x]+k);
cout<<ans<<'\n';
}
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
5 ms |
976 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1308 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1360 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1360 KB |
Output is correct |
| 8 |
Correct |
33 ms |
6872 KB |
Output is correct |
| 9 |
Correct |
61 ms |
8568 KB |
Output is correct |
| 10 |
Correct |
73 ms |
13280 KB |
Output is correct |
| 11 |
Correct |
66 ms |
13252 KB |
Output is correct |
| 12 |
Correct |
69 ms |
13160 KB |
Output is correct |
| 13 |
Correct |
68 ms |
13220 KB |
Output is correct |
| 14 |
Correct |
68 ms |
13292 KB |
Output is correct |
| 15 |
Correct |
88 ms |
25916 KB |
Output is correct |
| 16 |
Correct |
88 ms |
25860 KB |
Output is correct |
| 17 |
Correct |
67 ms |
13212 KB |
Output is correct |
| 18 |
Correct |
65 ms |
13252 KB |
Output is correct |
| 19 |
Correct |
88 ms |
25860 KB |
Output is correct |
| 20 |
Correct |
88 ms |
25844 KB |
Output is correct |
