Codeforces 813E - Army Creation

813E - Army Creation

思路：

线段树+二分

先预处理每个点往后走k步的下标

线段树二叉树的每个节点用vector维护这些下标，给这些下标排个序

询问区间L,R,那么把下标小于等于R的位置都减掉，因为只要后面连续k个就够了

代码：

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define pb push_back

#define ls rt<<1,l,m

#define rs rt<<1|1,m+1,r

#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e5+;

int a[N],now[N],nxt[N],pre[N],nxtk[N],ans=;

vector<int>vc[N<<];

void build(int rt,int l,int r){

    if(l==r){

        vc[rt].pb(nxtk[l]);

        return ;

    }

    for(int i=l;i<=r;i++)vc[rt].pb(nxtk[i]);

    sort(vc[rt].begin(),vc[rt].end());

    int m=(l+r)>>;

    build(ls);

    build(rs);

}

void query(int L,int R,int rt,int l,int r){

    if(L<=l&&r<=R){

        int T=upper_bound(vc[rt].begin(),vc[rt].end(),R)-vc[rt].begin();

        ans-=T;

        return ;

    }

    int m=(l+r)>>;

    if(L<=m)query(L,R,ls);

    if(R>m)query(L,R,rs);

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie();

    cout.tie();

    int n,k,q,l,r;

    cin>>n>>k;

    for(int i=;i<=n;i++)cin>>a[i];

    for(int i=;i<N;i++)now[i]=n+;

    nxt[n+]=n+;

    for(int i=n;i>=;i--){

        nxt[i]=now[a[i]];

        pre[now[a[i]]]=i;

        now[a[i]]=i;

    }

    for(int i=;i<=n;i++){

        if(i==now[a[i]]){

            int t=i,cnt=;

            while(t!=n+&&cnt<k){

                t=nxt[t];

                cnt++;

            }

            nxtk[i]=t;

        }

        else{

            nxtk[i]=nxt[nxtk[pre[i]]];

        }

    }

    cout<<endl;

    build(,,n);

    cin>>q;

    while(q--){

        cin>>l>>r;

        l+=ans;

        r+=ans;

        l=l%n+;

        r=r%n+;

        if(l>r)swap(l,r);

        ans=r-l+;

        query(l,r,,,n);

        cout<<ans<<endl;

    }

    return ;

}