思路

裸的主席树。查询的时候，通过相减求出区间内左子树中数的个数a。然后判断要查找的k是否比这个z要大。如果比这个值大，那么就去右子树中查找第k - z大，否则去左子树中查找第k大。

代码

/*

* @Author: wxyww

* @Date:   2018-12-11 16:27:19

* @Last Modified time: 2018-12-11 16:46:07

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<map>

#include<bitset>

using namespace std;

typedef long long ll;

const int N = 200000 + 100;

ll read() {

   ll x=0,f=1;char c=getchar();

   while(c<'0'||c>'9') {

      if(c=='-') f=-1;

      c=getchar();

   }

   while(c>='0'&&c<='9') {

      x=x*10+c-'0';

      c=getchar();

   }

   return x*f;

}

int a[N],root[N];

map<int,int>ma;

int tree[N * 30],ls[N * 30],rs[N * 30];

int tot,dy[N];

void update(int &rt,int lst,int l,int r,int pos) {

   rt = ++tot;

   ls[rt] = ls[lst];rs[rt] = rs[lst];

   tree[rt] = tree[lst] + 1;

   if(l == r) return;

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

   if(pos <= mid) update(ls[rt],ls[lst],l,mid,pos);

   else update(rs[rt],rs[lst],mid + 1,r,pos);

}

int query(int L,int R,int l,int r,int k) {

   int z = tree[ls[R]] - tree[ls[L]];

   if(l == r) return l;

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

   if(k <= z) return query(ls[L],ls[R],l,mid,k);

   else return query(rs[L],rs[R],mid + 1,r,k - z);

}

int main() {

   int n = read(),m = read();

   for(int i = 1;i <= n;++i) ls[i] = a[i] = read();

   sort(ls + 1,ls + n + 1);

   int js = 0;

   ma[ls[1]] = ++js;

   dy[js] = ls[1];

   for(int i = 2;i <= n;++i) if(ls[i] != ls[i - 1]) ma[ls[i]] = ++js,dy[js] = ls[i];

   for(int i = 1;i <= n;++i) a[i] = ma[a[i]];

   for(int i = 1;i <= n;++i) update(root[i],root[i - 1],1,js,a[i]);

   while(m--) {

      int l = read(),r = read(),k = read();

      printf("%d\n",dy[query(root[l - 1],root[r],1,js,k)]);

   }

   return 0;

}

巴特西

[luogu3834][可持久化线段树 1(主席树)]

思路

代码

最新文章

热门文章