[POJ] 2104. K-th Number
題目連結:http://poj.org/problem?id=2104
裸的區間第K大值,曾經會過可是又忘記了,只記得關鍵字持久化,被雷了才知道。原來就是原本的序列第K大是直接用樹上的節點作二分搜,但是區間的話就變成要用$[L,R]$的和做節點二分搜,而要算$[L,R]$的和,其實就用持久化線段樹把$roots[R]-roots[L]$即可。
裸的區間第K大值,曾經會過可是又忘記了,只記得關鍵字持久化,被雷了才知道。原來就是原本的序列第K大是直接用樹上的節點作二分搜,但是區間的話就變成要用$[L,R]$的和做節點二分搜,而要算$[L,R]$的和,其實就用持久化線段樹把$roots[R]-roots[L]$即可。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
const int N = 100000 + 5;
const int MEM = 2000000;
class LiSan{
private:
vector<int> v;
public:
inline void init(){v.clear();}
inline void insert(int x){v.PB(x);}
inline int size(){return v.size();}
inline void done(){
sort(ALL(v));
v.resize(distance(v.begin(), unique(ALL(v))));
}
inline int get(int x){
return distance(v.begin(), lower_bound(ALL(v), x));
}
inline int inv_get(int x){return v[x];}
} lisan;
class PSegTree{
private:
struct Node{
int val, lc, rc;
Node(){val=0;lc=-1;rc=-1;}
} nodes[MEM];
int _mem, size;
int _new(){
assert(_mem < MEM);
nodes[_mem]=Node();
return _mem++;
}
inline int lc(int x){return nodes[x].lc;}
inline int rc(int x){return nodes[x].rc;}
int build(int l, int r, int id){
id = _new();
if(r-l>1){
int mid=(l+r)>>1;
nodes[id].lc = build(l, mid, -1);
nodes[id].rc = build(mid, r, -1);
}
return id;
}
int modify(int ql, int qr, int l, int r, int v, int id){
if(qr <= l or r <= ql) return id;
int nid = _new();
if(ql <= l and r <= qr){
nodes[nid] = nodes[id];
nodes[nid].val += v;
return nid;
}
int mid = (l+r)>>1;
nodes[nid].lc = modify(ql, qr, l, mid, v, nodes[id].lc);
nodes[nid].rc = modify(ql, qr, mid, r, v, nodes[id].rc);
nodes[nid].val = nodes[nodes[nid].lc].val + nodes[nodes[nid].rc].val;
return nid;
}
int query(int k, int l, int r, int idL, int idR){
if(r-l==1) return l;
int lV = nodes[lc(idR)].val - nodes[lc(idL)].val;
int mid=(l+r)>>1;
if(lV >= k)
return query(k, l, mid, lc(idL), lc(idR));
else
return query(k-lV, mid, r, rc(idL), rc(idR));
}
public:
int build(int n){
_mem=0;
size=n;
return build(0, n, -1);
}
int modify(int p, int v, int id){
return modify(p, p+1, 0, size, v, id);
}
int query(int k, int idL, int idR){
return query(k, 0, size, idL, idR);
}
};
PSegTree seg;
int arr[N], roots[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, q; cin>>n>>q;
lisan.init();
for(int i=0;i<n;i++){
cin>>arr[i];
lisan.insert(arr[i]);
}
lisan.done();
roots[0]=seg.build(lisan.size());
for(int i=0;i<n;i++)
roots[i+1] = seg.modify(lisan.get(arr[i]),1,roots[i]);
for(int i=0;i<q;i++){
int l, r, k; cin>>l>>r>>k;
int res = seg.query(k, roots[l-1], roots[r]);
cout<<lisan.inv_get(res)<<'\n';
}
return 0;
}
留言
張貼留言