codeforces 1181D

奇怪。这种题为什么我三个月之前没补。。。
线段树都被队友写完了啊
https://blog.csdn.net/hzk_cpp/article/details/92797305
康的这个

首先我们对a[i]排序，
然后其实就是不停的在推平一段区间，
也就是 将前i个数全部变成与i+1一样大的过程。
我们可以随便判断一下推平到哪个数对应的应该是哪些询问。
全推平以后就不用再推了。

现在需要找第k小。也就是答案。
显然我们可以二分一个下标然后不停的query前缀和。
这东西用线段树单log很好施展。
然后我们用同样的思想在树状数组上倍增即可。

不对啊？？？这种题为什么我三个月之前没过啊？？？？这种傻逼线段树二分不是前几天(周)cf刚出了一个吗？？？

学到了奇淫技巧
具体表现为

#define 你老婆的名字 inline

然后就可以在每个函数前面都加上你老婆的名字了。
死宅真恶心

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define pii pair<ll,int>
#define sakuratxdy inline
using namespace std;
typedef long long ll;
const int N = 1e6+5;
ll bit[N];
int n,m,t;int a[N];
sakuratxdy int lowbit(int x){return x & -x;}
sakuratxdy void upd(int pos, int x){
    while (pos<N)bit[pos]+=x,pos+=lowbit(pos);
}
sakuratxdy int que(int pos){
    int res = 0;
    for(int i=19;i>=0;i--){
        if(res+(1<<i)<=m&&pos>bit[res+(1<<i)])
            pos-=bit[res+(1<<i)],res+=1<<i;
    }
    return res+1;
}
struct Node{
    ll val,id;
}node[N];
pii q[N];int ans[N];
bool cmp(Node a,Node b){
    return a.val<b.val||(a.val==b.val&&a.id<b.id);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)cin>>a[i],node[a[i]].val++;
    for(int i=1;i<=m;i++)node[i].id=i;
    sort(node+1,node+1+m,cmp);
    for(int i=1;i<=t;i++){
        cin>>q[i].first,q[i].second=i,q[i].first-=n;
    }
    sort(q+1,q+1+t);
    ll now = 0;int j=1;
    for(int i=1;i<m;i++){
        upd(node[i].id,1);
        while (j<=t&&q[j].first<=now+(node[i+1].val-node[i].val)*i){
            int t=(q[j].first-now)%i;
            ans[q[j++].second]=que(t==0?i:t);
        }
        now+=(node[i+1].val-node[i].val)*i;
    }
    upd(node[m].id,1);
    while (j<=t){//
        int t = (q[j].first-now)%m;
        ans[q[j++].second]=que(t==0?m:t);
    }
    for(int i=1;i<=t;i++){
        cout<<ans[i]<<'\n';
    }
}

codeforces 1181D

原文：https://www.cnblogs.com/MXang/p/11514344.html