题意分析

1. 核心问题：
   • 给定一个静态数组（狗的漂亮值），处理多个区间查询，每次查询区间$[i,j]$中第$k$小的值（第$k$漂亮的狗）。
2. 限制条件：
   • 所有查询区间互不包含，但可以交叉。
   • 漂亮值较低的狗更漂亮（即求区间第$k$小值）。

解题思路

1. 数据结构选择：
   • 使用主席树维护区间$[1,i]$的权值线段树，支持高效查询区间第$k$小值。
   • 由于区间互不包含，无需处理动态修改，适合离线构建。
2. 查询处理：
   • 对每个查询$[i,j]$，利用主席树的差分性质（$T_j - T_{i-1}$）在$O(\log n)$时间内得到第$k$小值。

实现步骤

1. 离散化处理：
   • 将狗的漂亮值离散化为排名，减少权值线段树的空间开销。
2. 构建主席树：
   • 从左到右依次插入每个元素，构建可持久化版本。
3. 处理查询：
   • 对每个查询$[i,j,k]$，在主席树上二分查找第$k$小的离散化值，再映射回原始漂亮值。
4. 输出结果：
   • 对每个查询直接返回计算得到的漂亮值。

代码实现

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define lim 1000000000
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
 
const int maxn=100010;
int n,m,sz,rt[maxn];
struct node {
    int son[2],s;
    int& operator [] (int x) {return son[x];}
}tr[maxn*40];
 
void build(int &u,int v,int l,int r,int val) {
    u=++sz;
    if (l==r) {tr[u].s=tr[v].s+1;return;}
    int mid=(l+r)>>1;
    if (val<=mid) build(tr[u][0],tr[v][0],l,mid,val),tr[u][1]=tr[v][1];
    else build(tr[u][1],tr[v][1],mid+1,r,val),tr[u][0]=tr[v][0];
    tr[u].s=tr[tr[u][0]].s+tr[tr[u][1]].s;
}
int query(int u,int v,int l,int r,int k) {
    if (l==r) return l;
    int mid=(l+r)>>1,c=tr[tr[v][0]].s-tr[tr[u][0]].s;
    if (c>=k) return query(tr[u][0],tr[v][0],l,mid,k);
    else return query(tr[u][1],tr[v][1],mid+1,r,k-c);
}
int main() {
    scanf("%d%d",&n,&m);
    for (int x,i=1;i<=n;i++) {
        scanf("%d",&x);
        build(rt[i],rt[i-1],-lim,lim,x);
    }
    for (int x,y,k,i=1;i<=m;i++) {
        scanf("%d%d%d",&x,&y,&k);
        printf("%d\n",query(rt[x-1],rt[y],-lim,lim,k));
    }
    return 0;
}