StoneGames

The first line of input contains two integers $n$ and $Q$ , where $n(1\leq n\leq 10^6)$ is the number of tiles and $Q(1\leq Q\leq 10^5)$ is the number of the rounds of the games.

The second line contains $n$ integers $s_1,...,s_n$ , the $i$ -th of which, $s_i(1\leq s_i\leq 10^9)$ , indicates the number of stones in the tile with index $i$ .

Satoko wants you to compute the answers immediately after Rika chooses the interval, so she uses the following method to encrypt the input. The $i$ -th of the next $Q$ lines contains two integers $l_i',r_i'(1\leq l_i', r_i'\leq n)$ . The chosen index range for the $i$ -th round, $l_i,r_i$ , can be computed by the following formula:

$l_i = \min\{ (l_i'+ans_{i-1}) \bmod n+1, (r_i'+ans_{i-1}) \bmod n+1 \}$

$r_i = \max\{ (l_i'+ans_{i-1}) \bmod n+1, (r_i'+ans_{i-1}) \bmod n+1 \}$

where $ans_i$ denotes the answer for the $i$ -th round of the game (and thus $ans_{i-1}$ is the answer for the previous round). You can assume that $ans_0=0$ . It is clear that under the given constraints, $1\leq l_i\leq r_i\leq n$ holds.

C++(clang++11) 解法, 执行用时: 1576ms, 内存消耗: 492220K, 提交时间: 2021-04-07 09:17:33

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n,m,rt[N],cnt;ll p;
struct node{int lc,rc;ll sum;}t[32345678];
void modi(int &x,int l,int r,int v){
    x=++cnt;
    t[x]=t[v];t[x].sum+=p;
    int mid=l+r>>1;
    if(l==r)return;
    if(p<=mid)modi(t[x].lc,l,mid,t[v].lc);
    else modi(t[x].rc,mid+1,r,t[v].rc);
}
ll ask(int p,int l,int r,int u,int v){
    if(r<=p)return t[v].sum-t[u].sum;
    int mid=l+r>>1;
    return ask(p,l,mid,t[u].lc,t[v].lc)+(p>mid?ask(p,mid+1,r,t[u].rc,t[v].rc):0);
}
int main()
{
    int i;
    ll sum,las=0,l,r;
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>p,modi(rt[i],1,1e9,rt[i-1]);
    while(m--){
        cin>>l>>r;
        l=(l+las)%n+1,r=(r+las)%n+1;
        if(l>r)swap(l,r);
        las=sum=0;
        while(1){
            sum=ask(min(sum+1,(ll)1e9),1,1e9,rt[l-1],rt[r]);
            if(sum==las)break;
            las=sum;
        }
        las=sum+1;
        cout<<las<<'\n';
    }
}

C++(g++ 7.5.0) 解法, 执行用时: 1738ms, 内存消耗: 490904K, 提交时间: 2022-09-02 05:18:27

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int i,j,k,n,m,t,rt[1005000];
ll res,t1,l,r;

struct SB{
	#define md ((l+r)/2)
	int ls[32005000],rs[32005000],it;
	ll f[32005000];
	void add(int id0,int &id,int l,int r,int w){
		id=++it;f[id]=f[id0]+w;ls[id]=ls[id0];rs[id]=rs[id0];
		if(l==r)return;
		if(w<=md)add(ls[id0],ls[id],l,md,w);else add(rs[id0],rs[id],md+1,r,w);
	}
	ll get(int id,int l,int r,int w){
		if(!id||r<=w)return f[id];
		if(md<w)return f[ls[id]]+get(rs[id],md+1,r,w);
		return get(ls[id],l,md,w);
	}
}sb;

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>t;
	for(i=1;i<=n;i++){cin>>k;sb.add(rt[i-1],rt[i],1,1e9,k);}
	while(t--){
		cin>>l>>r;
		l=(res+l)%n+1;r=(res+r)%n+1;if(l>r)swap(l,r);
		res=0;
		while(1){
			t1=sb.get(rt[r],1,1e9,res+1)-sb.get(rt[l-1],1,1e9,res+1);
			if(t1<=res)break;
			res=t1;if(res+1>=1000000000){res=sb.f[rt[r]]-sb.f[rt[l-1]];break;}
		}
		cout<<++res<<'\n';
	}
}

详情