P1533 可怜的狗狗

http://www.luogu.org/problem/show?pid=1533

题目背景

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

题目描述

小卡家有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行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。

输入输出样例

输入样例#1：

7 2

1 5 2 6 3 7 4

1 5 3

2 7 1

输出样例#1：

3

2

以前写的暴力60

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 1000000

using namespace std;

int n,m;

char a2[];

int a[],a1[];

int x,y,k;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        cin>>a1[i];

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

    {

        scanf("%d%d%d",&x,&y,&k);

        memset(a,maxn,sizeof(a));

        for(int i=;i<=n;i++)

            a[i]=a1[i];

        sort(a+x,a+y+);

        printf("%d\n",a[k+x-]);

    }

    return ;

}

正解是什么，南城说是主席树

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

using namespace std;

const int M=3e5+;

const int N=M*;

int tot,sum[N],ls[N],rs[N],T[M],san[M],num[M];

int n,m;

void build(int &rt,int l,int r){

    rt=++tot;

    if(l==r) return ;

    int mid=l+r>>;

    build(ls[rt],l,mid);

    build(rs[rt],mid+,r);

}

void updata(int &rt,int last,int l,int r,int p){

    rt=++tot;

    ls[rt]=ls[last];

    rs[rt]=rs[last];

    sum[rt]=sum[last]+;

    if(l==r) return ;

    int mid=l+r>>;

    p<=mid?updata(ls[rt],ls[last],l,mid,p):updata(rs[rt],rs[last],mid+,r,p);

}

int query(int l,int r,int x,int y,int k){

    if(l==r) return l;

    int mid=l+r>>;

    int cnt=sum[ls[y]]-sum[ls[x]];

    k<=cnt?query(l,mid,ls[x],ls[y],k):query(mid+,r,rs[x],rs[y],k-cnt);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        int a;

        scanf("%d",&a);

        san[i]=num[i]=a;

    }

    stable_sort(san+,san+n+);

    int cnt=unique(san+,san+n+)-(san+);

    for(int i=;i<=n;i++) num[i]=lower_bound(san+,san+cnt+,num[i])-san;

    build(T[],,cnt);

    for(int i=;i<=n;i++) updata(T[i],T[i-],,cnt,num[i]);

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

        int x,y,k;

        scanf("%d%d%d",&x,&y,&k);

        int id=query(,cnt,T[x-],T[y],k);

        printf("%d\n",san[id]);

    }

    return ;

}