本文共 1795 字，大约阅读时间需要 5 分钟。
题目链接：
题目大意：长为 n 的数组，m 次询问，每次问区间 [l,r] 内第 k 小的数。
题目思路：主席树
应该是按权值建立线段树，先将权值离散化，然后利用前缀和的思想来解决。
主席树还是有点难理解，，，
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define fi first#define se second#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))using namespace std;#define gamma 0.5772156649015328606065120#define MOD 1000000007#define inf 0x3f3f3f3f#define N 100005#define maxn 30010typedef pair PII;typedef long long LL;LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}int n,m,k,sz,L,R;int a[N],b[N],c[N];int root[N];struct Seg{ int l,r,v;}seg[N*30];void update(int &rot,int rt,int l,int r){ seg[++sz]=seg[rot],rot=sz; ++seg[rot].v; if(l==r)return; int mid=l+r>>1; if(L<=mid)update(seg[rot].l,lson); else update(seg[rot].r,rson);}int query(int rt,int l,int r,int k){ if(l==r)return a[l]; int num=seg[seg[R].l].v-seg[seg[L].l].v; int mid=l+r>>1; if(num>=k){ L=seg[L].l;R=seg[R].l; return query(lson,k); } else{ L=seg[L].r;R=seg[R].r; return query(rson,k-num); }}int main(){ int i,j,group,x,y; n=read();m=read(); for(i=1;i<=n;++i)a[i]=read(),c[i]=b[i]=a[i]; sort(a+1,a+n+1); int _n=unique(a+1,a+n+1)-a; for(i=1;i<=n;++i)b[i]=lower_bound(a+1,a+_n+1,b[i])-a; for(i=1;i<=n;++i)L=b[i],update(root[i]=root[i-1],1,1,n); while(m--){ x=read(),y=read(),k=read(); L=root[x-1];R=root[y]; printf("%d\n",query(1,1,n,k)); } return 0;}
转载于:https://www.cnblogs.com/Kurokey/p/5918580.html