luogu P1533 可怜的狗狗 |莫队+二分

题目背景

小卡由于公务需要出差，将新家中的狗狗们托付给朋友嘉嘉，但是嘉嘉是一个很懒的人，他才没那么多时间帮小卡喂狗狗。

题目描述

小卡家有N只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。

可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间（i,j）不互相包含。

输入格式

第一行输入两个数n，m，你可以假设n<300001 并且 m<50001；m表示他喂了m次。

第二行n个整数，表示第i只狗的漂亮值为ai。

接下来m行，每行3个整数i,j,k表示这次喂食喂第i到第j只狗中第k漂亮的狗的漂亮值。

输出格式

M行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。

---

因为区间不会互相包含，所以复杂度O(nlognlogn)

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=3e5+10;

int a[N],b[N];

struct node{

    int l,r,k,id;

}e[N];

inline bool cmp(node t1,node t2){

    return t1.l<t2.l;

}

int ans[N];

int c[N],n,m,k;

inline void Add(int x,int y){

    for(;x<=n;x+=x&(-x))c[x]+=y;

}

inline int sum(int x){

    int ans=0;

    for(;x;x-=x&(-x))ans+=c[x];

    return ans;

}

inline bool check(int mid){

    if(sum(mid)<k)return 1;

    else return 0;

}

inline int erfen(){

    int l=0,r=n+1,ans=0;

    while(l<=r){

        int mid=(l+r)>>1;

        if(check(mid)){

            l=mid+1;

            ans=mid;

        }else r=mid-1;

    }

    return ans;

}

signed main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].k),e[i].id=i;

    sort(e+1,e+1+m,cmp); sort(b+1,b+1+n);

    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+n,a[i])-b;

    int l=e[1].l,r=e[1].r;

    for(int i=l;i<=r;i++)Add(a[i],1);

    for(int i=1;i<=m;i++){

        while(l<e[i].l)Add(a[l++],-1);

        while(l>e[i].l)Add(a[--l],1);

        while(r>e[i].r)Add(a[r--],-1);

        while(r<e[i].r)Add(a[++r],1);

        k=e[i].k;

        ans[e[i].id]=b[erfen()+1];

    }

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

}