M.StoneGames（ICPC2020昆明题解）xiaodangao

题目链接：M.Stone Games
思路：
先上图：

所以假设当前满足$[1,x]$全覆盖，且$[1,x]$中所有元素都已经选完，那么我们发现，我们判断$x+2$是否存在没有什么意义，只有判断$[1,x+1]$中元素存在才有意义，选择$x+1$就是为了能构成上述图中情况1。因为有一个$x+1$，那么整体集合就可以$+(x+1)$，所以有几个x+1，整体集合就会增加几个x+1，最终能够停在的地方就是对于值域在$[1,x+1]$的所有数的$sum$，就是根据上图中的条件进行递推，每一次递推能够增加到$\sum_1^{x+1}{\sum{i}}$。最后判断一下是否需要继续递推就可以。方法是利用可持久化权值线段树，记录区间sum值。复杂度$\Theta (nlogn^2)$(咱也不知道为什么，离散化会MLE
$Code:$

/* -*- encoding: utf-8 -*-
'''
@File    :   255.cpp
@Time    :   2021/05/31 21:05:02
@Author  :   puddle_jumper
@Version :   1.0
@Contact :   1194446133@qq.com
'''

# here put the import lib*/
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#define ch() getchar()
#define pc(x) putchar(x)
#include<stack>
#include<unordered_map>
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define ll long long
#define ull unsigned long long
#define pb emplace_back
#define mp make_pair
#define PI acos(-1)
using namespace std;
template<typename T>void read(T&x){
    static char c;
    static int f;
    for(c=ch(),f=1; c<'0'||c>'9'; c=ch())if(c=='-')f=-f;
    for(x=0; c>='0'&&c<='9'; c=ch())x=x*10+(c&15);
    x*=f;
}
template<typename T>void write(T x){
    static char q[65];
    int cnt=0;
    if(x<0)pc('-'),x=-x;
    q[++cnt]=x%10,x/=10;
    while(x)
        q[++cnt]=x%10,x/=10;
    while(cnt)pc(q[cnt--]+'0');
}

const int N = 1e6+10;
const int inf = 1e9+10;
int n,q;
int root[N];
struct node{
    int l,r;
    ll sum;
}tr[N*50];
int a[N];
int idx;
int add(int l,int r,int p,int k){
    int q = ++idx;
    tr[q] = tr[p];
    if(l == r){tr[q].sum += k;return q; }
    int mid = l + r >> 1;
    if(k <= mid){tr[q].l = add(l,mid,tr[p].l,k); }
    else tr[q].r = add(mid+1,r,tr[p].r,k);
    tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum;
    return q;
}

ll query(int l,int r,int s,int t,int p,int q){
    if(s<=l and r<=t)return tr[q].sum - tr[p].sum;
    int mid = l + r >> 1;
    ll ans = 0;
    if(s<=mid)ans += query(l,mid,s,t,tr[p].l,tr[q].l);
    if(t>mid)ans += query(mid+1,r,s,t,tr[p].r,tr[q].r);
    return ans;
}


void solve(){
    read(n);read(q);
    rep(i,1,n)read(a[i]);//nums.pb(a[i]); }
    //sort(nums.begin(),nums.end());
    //nums.erase(unique(nums.begin(),nums.end()),nums.end());
    //int mx = *max_element(nums.begin(),nums.end());
    rep(i,1,n){ root[i] = add(1,inf,root[i-1],a[i]); }
    ll ans = 0;
    //printf("%lld\n",query(0,(int)nums.size()-1,0,found(4),root[1],root[4]));
    while(q--){
        int u,v;
        read(u);read(v);
        u = (ans + u) % n+1;
        v = (ans + v) % n+1;
        if(u>v)swap(u,v);
       // printf("%d %d\n",u,v);
        ll sum = 0;
        while(true){
            ll now = query(1,inf,1,min((ll)inf,sum+1),root[u-1],root[v]);
            //printf("%lld %lld\n",now,sum);
            if(now == sum)break;
            sum = now;
        }
        ans = sum + 1;
        write(ans);pc('\n');
    }
}


signed main(){solve();return 0; }

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章