vijos1081 野生动物园[离线区间第K大 ZKW权值线段树]

又一道卡了半天的鬼题……
头图来自P站，pid48524695

题目

描述

cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内，这个区域从南到北被划分成N个区域，每个区域都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮子都有一个觅食能力值Ai，Ai越> 小觅食能力越强。饲养员cmdButtons决定对狮子进行M次投喂，每次投喂都选择一个区间[I,J]，从中选取觅食能力值第K强的狮子进行投喂。值得注意的是，cmdButtons不愿意对某些区域进行过多的投喂，他认为这样有悖公> 平。因此cmdButtons的投喂区间是互不包含的。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。

格式

输入格式

输入第一行有两个数N和M。此后一行有N个数，从南到北描述狮子的觅食能力值。此后M行，每行描述一次投喂。第t+2的三个数I,J,K表示在第t次投喂中，cmdButtons选择了区间[I,J]内觅食能力值第K强的狮子进行投喂。

输出格式

输出有M行，每行一个整数。第i行的整数表示在第i次投喂中吃到食物的狮子的觅食能力值。

样例1

样例输入1

7 2
1 5 2 6 3 7 4
1 5 3
2 7 1

样例输出1

3
2

限制

各个测试点2s

提示

对于100%的数据，有1<=N<=100000，1<=M<=50000。

分析

明摆着的离线区间第K大查询，由于是纯静态的，输入数据不变，一看就是什么平衡树的裸题（真可惜我不会2333)，不会归不会，题还是得A的，怎么办呢，网上题解一堆的主席树模板，可我只会写写线段树之类的，看这个数据量绝对会被卡……不怕，我们有ZKW神树啊，我们理想中的能满足我们要求的数据结构应该是这样的

• 单点插入

• 单点更新

• 求任意区间的第K大

• 允许元素重复

但实际上找不到这玩意……平衡树支持的如下

• 单点插入
• 单点更新
• 单点删除
• 求当前树的第K大
• 查询数的排名
• 查找某数是否存在
• 允许重复

乍一看很像有木有？唯一的区别是我们要查的是任意区间，而平衡树只能维护整棵树的Kth，这启发我们可以将所有查询区间读进来，按照左端点为第一关键字，右端点为第二关键字从小到大排序，然后分别处理完每个区间的答案，再统一输出，每次查询答案时都保证当前树上维护的区间是查询所对应的区间即可，由于区间没有包含，只有相交和不相交，直接暴力for循环维护区间值即可，如下：

• 当我处理第i组询问的时候，通过for循环将不是该询问区间的元素从树上删掉，将该区间元素中还未加入树中的加入，由于我们已经对询问排序了，每个元素最多会被加入和删除一次，所以复杂度不是问题。

那么问题来了，不会平衡树怎么办……我们有线段树啊！在此介绍zkw权值线段树，常数极小，但处理方式得稍微不同。

由于线段树的处理区间是连续的，按照权值线段树下去建树，zkw线段树的最底下一层的元素个数将会是$\max\{a_1,a_2,...a_n\}$的(因为权值线段树代表处理的区间是$[1...MaxVal]$)，而且zkw线段树的数组空间得开到四倍大(还不了解的同学请先去研究zkw线段树)，空间上将会非常吃紧，所以我们得通过离散化，将数组离散掉，那么离散过后$\max\{a_1,a_2,...a_n\}$就会小于等于N，这样空间的问题就得到了解决，那么像普通平衡树一样，将询问区间排好序，依次处理每个区间，若$a_i$在当前询问区间，那么$c[a_i]+=1$,否则，$c[a_i]-=1$即可，保证每次处理询问的时候，树上只有这个区间内的所有元素，然后只要自顶向下实现find_by_order函数即可，具体实现见代码，很简单，从堆顶往下依次判断第K大的数在左子树还是右子树，一直递归到最底下一层即可。

• 最重要的一点，通过find_by_order返回的元素是原本的元素离散后的值，所以我们必须再建一个字典（数组，哈希表都可以），若$b[i]==x$,则代表离散化后值为i的元素的原来的值是x，那么找到后输出字典中对应的原始值即可。

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=100008;
int n,m,k,mm,h;
long long cnt;
int a[maxn],b[maxn],ans[maxn];
int c[maxn*4];
int alll,allr,curl,curr;
pair<int,int> g[maxn];
struct node
{
    int l,r,k,ind;
}t[maxn];
bool cmp(node aa,node bb){
    if(aa.l==bb.l)
        return aa.r<bb.r;
    return aa.l<bb.l;
}
inline void insert(int ind,int va){
    for(long long it=ind+mm;it>=1;it>>=1)
        c[it]+=va;
}
long long find_by_order(int kth,int cur,int dep){
    if (dep==h)
        return cur;
    long long tans = 0;
    if ((cnt+c[cur+cur])<kth){
        cnt+=c[cur+cur];
        tans = find_by_order(kth,cur+cur+1,dep+1);
    } else
        tans = find_by_order(kth,cur+cur,dep+1);
    return tans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("input.in","r",stdin);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> g[i].first;
        g[i].second=i;
    }
    sort(g+1,g+1+n);
    for(int i=1;i<=n;i++){
        a[g[i].second]=i;
        b[i]=g[i].first;
    }
    for(h=1,mm=1;mm<=n+1;mm<<=1,h++);
    for(int i=1;i<=m;i++){
        cin >> t[i].l >>t[i].r >> t[i].k;
        t[i].ind=i;
    }
    sort(t+1,t+1+m,cmp);
    alll=1;allr=1;
    bool NotFirst=false;
    for(int i=1;i<=m;i++){
        curl=t[i].l;
        curr=t[i].r;
        if (NotFirst==false){
            for(int j=curl;j<=curr;j++)
                insert(a[j],1);
            NotFirst=true; 
            alll=curl,allr=curr;
        }else{
            for(int j=alll;j<=curl-1;j++)
                insert(a[j],-1);
            alll=curl;
            for(int j=allr+1;j<=curr;j++)
                insert(a[j],1);
            allr = curr;
        }
        cnt=0;
        ans[t[i].ind]=b[find_by_order(t[i].k,1,1)-mm];
    }
    for(int i=1;i<=m;i++)
        cout << ans[i] << endl;
    return 0;
}

后话

其实如果实在做不过去的话……STL中的nth_element能水60分呢！血赚不亏啊……

版权声明：本文为原创文章，版权归星夜的蓝天所有。

本文链接：http://poi.ac/archives/39/

本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

转载时须注明出处及本声明