Codeforces Round #567 (Div. 2) D. Irrigation(思维+主席树)

题目链接
大意：m个城市，给你前n年的举办城市，之后的每一年都会让举办次数最少且标号最小的城市举办一次，给你q组询问让你求出第k年的举办城市。
思路：首先，对m个城市按举办次数从小到达排序，建一颗主席树，然后每次举办的城市显然是在一些举办次数相同且最小的城市中轮换，那我们就预处理出每种等级的城市升级到下一个等级一共需要多少次（按举办次数分等级），然后每次询问就二分一下是从哪个等级升过来的，然后在主席树上查一下区间第x小就行了。
细节有一些需要注意：

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 5e5 + 3;
const LL mod = 1e9 + 7;
int n,m,q;
int a[N],b[N],cnt;
LL sum[N];
vector<int>v[N];
int T[N];
struct faker{int sum,l,r;}t[N*40];
struct uzi{int a,i;bool operator <(const uzi &t)const{return a<t.a;}}p[N];
int NOW;
void up(int &x,int y,int l,int r,int pos){
    t[++NOW]=t[y];t[NOW].sum++;x=NOW;
    if(l==r)return ;
    int mid=l+r>>1;
    if(pos<=mid)up(t[x].l,t[y].l,l,mid,pos);
    else up(t[x].r,t[y].r,mid+1,r,pos);
}
int get(int x,int y,int l,int r,int k){
    if(l==r)return l;
    int res=t[t[y].l].sum-t[t[x].l].sum;
    int mid=l+r>>1;
    if(res>=k)return get(t[x].l,t[y].l,l,mid,k);
    else return get(t[x].r,t[y].r,mid+1,r,k-res);
}
int tot[N];
int main() {
	ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)p[i].i=i;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i],p[a[i]].a++,p[a[i]].i=a[i];
    sort(b+1,b+1+n);
    sort(p+1,p+1+m);
    int level=0;p[0].a=-1;
    for(int i=1;i<=m;i++){
        if(p[i].a!=p[i-1].a)level++;
        v[level].pb(p[i].i);
        up(T[i],T[i-1],1,m,p[i].i);
    }
    for(int i=1;i<=level;i++)tot[i]=tot[i-1]+SZ(v[i]);
    int l=1;
    while(l<=m){
        LL res=b[l];int pre=l;
        while(l+1<=m&&p[l+1].a==p[l].a)++l;
        if(l!=m){
            sum[++cnt]=1ll*l*p[l+1].a-1ll*l*p[l].a+sum[cnt-1];//升级到下一个需要的
        }else break;
        l++;
    }
    for(int i=1;i<=q;i++){
        LL x;cin>>x;x-=n;
        if(!cnt){
            x%=m;if(!x)x=m;
            cout<<get(T[0],T[m],1,m,x)<<endl;
        }else{
            int pos=lower_bound(sum+1,sum+1+cnt,x)-sum;
            if(pos>cnt){
                x-=sum[cnt];x%=m;if(!x)x=m;
                cout<<get(T[0],T[m],1,m,x)<<endl;
            }else{
                x-=sum[pos-1];x%=tot[pos];if(!x)x=tot[pos];
                cout<<get(T[0],T[tot[pos]],1,m,x)<<endl;
            }
        }
    }
	return 0;
}