Stone Games

主席樹

Code1

#include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=1000010; using ll=long long; const ll MAX=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=++cnt;tree[u]=tree[pre];tree[u].v+=pos;if(l==r) return;int mid=l+r>>1;if(pos<=mid) insert(tree[u].l,tree[pre].l,l,mid,pos);elseinsert(tree[u].r,tree[pre].r,mid+1,r,pos); } ll query(int u,int l,int r,int L,int R) {if(!u) return 0ll;if(L<=l&&r<=R) return tree[u].v;int mid=l+r>>1;ll v=0;if(L<=mid) v+=query(tree[u].l,l,mid,L,R);if(R>mid)v+=query(tree[u].r,mid+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=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) insert(root[i],root[i-1],1,MAX,a[i]);ll ans=0;while(m--){int l,r;cin>>l>>r;l=(l+ans)%n+1;r=(r+ans)%n+1;if(r<l) swap(l,r);ll pre=0;while(true){ll now=query(root[r],1,MAX,1,min(MAX,pre+1))-query(root[l-1],1,MAX,1,min(MAX,pre+1));if(now==pre) break;pre=now;}ans=pre+1;cout<<ans<<'\n';} }

Code2

賽時寫的樹套樹分塊MLE

#include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<bitset> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> 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=1e9+7; const int N=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=++cnt;tree[u].s+=pos;if(l==r) return;int mid=l+r>>1;if(pos<=mid)insert(tree[u].l,l,mid,pos);elseinsert(tree[u].r,mid+1,r,pos); } ll qsum(int u,int l,int r,ll L,ll R) {if(!u) return 0ll;if(L<=l&&r<=R) return tree[u].s;int mid=l+r>>1;ll v=0;if(L<=mid)v+=qsum(tree[u].l,l,mid,L,R);if(R>mid)v+=qsum(tree[u].r,mid+1,r,L,R);return v; } void update(int k,int x) {for(;k<=n;k+=lowbit(k)) insert(root[k],1,1000000000,x); } ll query(int l,int r,ll L,ll R) {ll v=0;for(;r;r-=lowbit(r)) v+=qsum(root[r],1,1000000000,L,R);for(;l;l-=lowbit(l)) v-=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=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) update(i,a[i]);ll ans=0;while(m--){ll l,r;cin>>l>>r;l=(l+ans)%n+1;r=(r+ans)%n+1;if(l>r) swap(l,r);ll pre=0;while(1){ll s=query(l-1,r,1ll,min(pre+1ll,1000000000ll));if(s==pre) break;pre=s;}ans=pre+1ll;cout<<ans<<'\n';}return 0; }

總結

以上是生活随笔為你收集整理的第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） Stone Games的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。