AC日记——曼哈顿交易 洛谷 P3730

曼哈顿交易

思路：

　　都是套路；

代码：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 100005

int n,m,bel[maxn],num[maxn],ai[maxn],size,block;

int ans[maxn],num_[maxn],num__[maxn],cnt,bi[maxn];

struct QueryType {

    int l,r,k,id;

    bool operator<(const QueryType &o)const{

        if(bel[l]==bel[o.l]) return (bel[l]&)?r>o.r:r<o.r;

        return l<o.l;

    }

};

struct QueryType qu[maxn];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void updata(int x)

{

    if(num[x]) num_[num[x]]--,num__[bel[num[x]]]--;

    else cnt++;

    num_[++num[x]]++,num__[bel[num[x]]]++;

}

inline void updata_(int x)

{

    num_[num[x]]--,num__[bel[num[x]--]]--;;

    if(num[x]) num_[num[x]]++,num__[bel[num[x]]]++;

    else cnt--;

}

inline int query(int k)

{

    if(k>cnt) return -;

    int i=;for(;k>num__[i];k-=num__[i++]);

    int j=i*block;for(;k>num_[j];k-=num_[j++]);

    return j;

}

int main()

{

    freopen("trade.in","r",stdin);

    freopen("trade.out","w",stdout);

    in(n),in(m),block=sqrt(n);

    for(int i=;i<=n;i++) in(ai[i]),bi[i]=ai[i],bel[i]=i/block;

    sort(bi+,bi+n+),size=unique(bi+,bi+n+)-bi-;

    for(int i=;i<=n;i++) ai[i]=lower_bound(bi+,bi+size+,ai[i])-bi;

    for(int i=;i<=m;i++) in(qu[i].l),in(qu[i].r),in(qu[i].k),qu[i].id=i;

    int l=,r=;sort(qu+,qu+m+);

    for(int no=;no<=m;no++)

    {

        while(r<qu[no].r) updata(ai[++r]);

        while(r>qu[no].r) updata_(ai[r--]);

        while(l<qu[no].l) updata_(ai[l++]);

        while(l>qu[no].l) updata(ai[--l]);

        ans[qu[no].id]=query(qu[no].k);

    }

    for(int i=;i<=m;i++) printf("%d\n",ans[i]);

    return ;

}