[POJ] 2104. K-th Number
題目連結: http://poj.org/problem?id=2104 裸的區間第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;
...
