CF 813 E - Army Creation

問題

Problem - E - Codeforces

問題概要

長さの数列と整数が与えられる。次のようなクエリが個与えられるので、それに答えよ：

• クエリ : 区間 について、同じ値は個までしか選べない時に、最大で何個まで選べるか

(問題を読んでもらうと分かるが、オンラインクエリになっている)

• 
• 
• 
• 

アイデア

オフラインクエリだったら、クエリを先読みしてMoを使ってmapで頻度数えて終わりだったのに...と思った。

クエリごとに、各値について先頭から個を選ぶということを考えよう。番目の要素が選ばれるには、そもそもでないといけないし、からスタートしてそれまでの間にと同じ値が個現れていてはいけないということになる。

ここで、新たな数列を作る。の番目の要素の値は、a[i]と同じ値で、k個前にあるindex(ｂ＝なければ-1)というものである。すると、番目の要素が選ばれるということはであることと、と言える。

あとは、区間 について、である要素がいくつあるかを数えれば良い。これは、mergesortの過程を保存したようなSegmentTreeなどで各ノードで二分探索をすればできたりする。

今回は(SegmentTreeの実装をサボりたかったので)平方分割した。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int N = 100000;
vector<int> idx[N];

const int B = 400;
const int INF = 19191919;

int b[N];
vector<int> sb[N/B];

int query(int l, int r){
    int ret = 0;

    int lid = l/B, rid = r/B;
    if(lid == rid){
        for(int i=l; i<=r; ++i) ret += (b[i]<l);
    }
    else{
        for(int i=l; i<B*(lid+1); ++i) ret += (b[i]<l);
        for(int bid=lid+1; bid<rid; ++bid){
            int add = lower_bound(all(sb[bid]), l) - sb[bid].begin();
            ret += add;
        }
        for(int i=B*rid; i<=r; ++i) ret += (b[i]<l);
    }

    return ret;
}

int main(){
    int n,k;
    scanf(" %d %d", &n, &k);
    vector<int> a(n);
    rep(i,n){
        scanf(" %d", &a[i]);
        --a[i];
        idx[a[i]].pb(i);
    }

    fill(b,b+N,INF);
    rep(i,N){
        int SZ = idx[i].size();

        rep(j,min(k,SZ)) b[idx[i][j]] = -1;
        for(int j=k; j<SZ; ++j) b[idx[i][j]] = idx[i][j-k];
    }
    rep(i,N) sb[i/B].pb(b[i]);
    rep(i,N/B) sort(all(sb[i]));

    int q;
    scanf(" %d", &q);

    int ans = 0;
    while(q--){
        int x,y;
        scanf(" %d %d", &x, &y);
        int l = (x+ans)%n, r = (y+ans)%n;
        if(l>r) swap(l,r);

        ans = query(l,r);
        printf("%d\n", ans);
    }
    return 0;
}