Educational Codeforces Round 22 E. Army Creation

#include <iostream> 
#include <stdio.h> 
#include <string.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <vector> 
#include <math.h> 
#include <bitset> 
#include <algorithm> 

using namespace std;

#define X first
#define Y second
#define eps 1e-2
#define gcd __gcd
#define pb push_back
#define PI acos(-1.0)
#define lowbit(x) (x)&(-x)
#define bug printf("!!!!!\n");
#define mem(x,y) memset(x,y,sizeof(x))

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef unsigned long long uLL;

const int N = 1e5+2;
const int INF  = 1<<30;
const int mod  = 1e9+7;

std::vector<int> v[N];
struct node{
    
    int l,r,sum;
}t[N<<5];
int tot=0;
int build(int p,int l,int r){
    
    p=++tot;
    if(l==r) return p;
    int mid=(l+r)>>1;
    t[p].l=build(p,l,mid);
    t[p].r=build(p,mid+1,r);
    return p;
}
int update(int p,int l,int r,int x){
    
    t[++tot]=t[p];p=tot;t[p].sum++;
    if(l==r) return p;
    int mid=(l+r)>>1;
    if(x<=mid) t[p].l=update(t[p].l,l,mid,x);
    else t[p].r=update(t[p].r,mid+1,r,x);
    return p;
}
int query(int p1,int p2,int l,int r,int from,int to){
    
    if(from<=l&&to>=r) return t[p2].sum-t[p1].sum;
    int mid=(l+r)>>1,ans=0;
    if(from<=mid) ans+=query(t[p1].l,t[p2].l,l,mid,from,to);
    if(to>=mid+1) ans+=query(t[p1].r,t[p2].r,mid+1,r,from,to);

    return ans;
}
int n,k,a[N],q,rt[N];
void solve(){
    
    scanf("%d%d",&n,&k);rt[0]=build(1,0,n);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&a[i]),v[a[i]].push_back(i);
        int sz=v[a[i]].size();
        int pos=(sz>k?v[a[i]][sz-1-k]:0);
        rt[i]=update(rt[i-1],0,n,pos);
    }
    // cout<<tot<<endl;
    scanf("%d",&q);
    int last=0;
    // cout<<t[18].sum<<endl;
    // cout<<rt[1]<<" "<<rt[2]<<endl;
    while(q--){
    
        int l,r;scanf("%d%d",&l,&r);
        l=((l+last)%n)+1;
        r=((r+last)%n)+1;
        if(l>r) swap(l,r);
        // cout<<l<<" "<<r<<endl;
        last=query(rt[l-1],rt[r],0,n,0,l-1);
        cout<<last<<endl;
    }
    return;
}

int main()
{
    
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
    int t = 1;
    //scanf("%d",&t);
    while(t--){
    
    // printf("Case %d: ",cas++);
        solve();
    }
    return 0;
}