第45届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明）StoneGames

#include
#include
#include
using namespace std;
const int N&＃61;1000010;
using ll&＃61;long long;
const ll MAX&＃61;1000000000ll;
int n,a[N],m;
struct node
{int l,r;ll v;
}tree[N*40];
int root[N],cnt;
void insert(int &u,int pre,int l,int r,int pos)
{u&＃61;&＃43;&＃43;cnt;tree[u]&＃61;tree[pre];tree[u].v&＃43;&＃61;pos;if(l&＃61;&＃61;r) return;int mid&＃61;l&＃43;r>>1;if(pos<&＃61;mid) insert(tree[u].l,tree[pre].l,l,mid,pos);elseinsert(tree[u].r,tree[pre].r,mid&＃43;1,r,pos);
}
ll query(int u,int l,int r,int L,int R)
{if(!u) return 0ll;if(L<&＃61;l&&r<&＃61;R) return tree[u].v;int mid&＃61;l&＃43;r>>1;ll v&＃61;0;if(L<&＃61;mid) v&＃43;&＃61;query(tree[u].l,l,mid,L,R);if(R>mid)v&＃43;&＃61;query(tree[u].r,mid&＃43;1,r,L,R);return v;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) cin>>a[i];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) insert(root[i],root[i-1],1,MAX,a[i]);ll ans&＃61;0;while(m--){int l,r;cin>>l>>r;l&＃61;(l&＃43;ans)%n&＃43;1;r&＃61;(r&＃43;ans)%n&＃43;1;if(r<l) swap(l,r);ll pre&＃61;0;while(true){ll now&＃61;query(root[r],1,MAX,1,min(MAX,pre&＃43;1))-query(root[l-1],1,MAX,1,min(MAX,pre&＃43;1));if(now&＃61;&＃61;pre) break;pre&＃61;now;}ans&＃61;pre&＃43;1;cout<<ans<<&＃39;\n&＃39;;}
}


Code2

赛时写的树套树分块MLE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
const ll mod&＃61;1e9&＃43;7;
const int N&＃61;1000010;
int a[N],n,m;
struct node
{int l,r;ll s;
}tree[N*67];int cnt;
int root[N];
int lowbit(int x){return x&-x;}void insert(int &u,int l,int r,int pos)
{if(!u) u&＃61;&＃43;&＃43;cnt;tree[u].s&＃43;&＃61;pos;if(l&＃61;&＃61;r) return;int mid&＃61;l&＃43;r>>1;if(pos<&＃61;mid)insert(tree[u].l,l,mid,pos);elseinsert(tree[u].r,mid&＃43;1,r,pos);
}
ll qsum(int u,int l,int r,ll L,ll R)
{if(!u) return 0ll;if(L<&＃61;l&&r<&＃61;R) return tree[u].s;int mid&＃61;l&＃43;r>>1;ll v&＃61;0;if(L<&＃61;mid)v&＃43;&＃61;qsum(tree[u].l,l,mid,L,R);if(R>mid)v&＃43;&＃61;qsum(tree[u].r,mid&＃43;1,r,L,R);return v;
}
void update(int k,int x)
{for(;k<&＃61;n;k&＃43;&＃61;lowbit(k)) insert(root[k],1,1000000000,x);
}
ll query(int l,int r,ll L,ll R)
{ll v&＃61;0;for(;r;r-&＃61;lowbit(r)) v&＃43;&＃61;qsum(root[r],1,1000000000,L,R);for(;l;l-&＃61;lowbit(l)) v-&＃61;qsum(root[l],1,1000000000,L,R);return v;
}
int main()
{ios::sync_with_stdio(false);cin.tie();cout.tie(0);cin>>n>>m;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) cin>>a[i];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) update(i,a[i]);ll ans&＃61;0;while(m--){ll l,r;cin>>l>>r;l&＃61;(l&＃43;ans)%n&＃43;1;r&＃61;(r&＃43;ans)%n&＃43;1;if(l>r) swap(l,r);ll pre&＃61;0;while(1){ll s&＃61;query(l-1,r,1ll,min(pre&＃43;1ll,1000000000ll));if(s&＃61;&＃61;pre) break;pre&＃61;s;}ans&＃61;pre&＃43;1ll;cout<<ans<<&＃39;\n&＃39;;}return 0;
}