[SPOJ] DQUERY - D-query (歸併樹)
題目連結: http://www.spoj.com/problems/DQUERY/ 本題的另外一種解法，構造方式與 上一種 不同，這裡的構造方式是將每個相同的數字由左至右連邊(如圖) 那這樣對於一個詢問$[L, R]$，就變成詢問$[L,R]$中大於$R$的數有多少個，因為每個數字最終必須往外伸出去。 而詢問$[L,R]$中大於$R$的數有多少個，其實可以用一種跟線段樹很像的做法做，節點存的是排序好的$[L,R]$，那詢問就直接二分搜就好，不過建立的過程退化成$O(n log n)$查詢則變成$O( n log^2 n)$ #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
const int N = 30000 + 5;
const int INF = 1<<30;
class LiSan{
private:
vector<int> v;
public:
void init(){v.clear();}
void insert(int x){v.PB(x);}
int size(){return v.size();}
void done(){
sort(ALL(v));
v.resize(distance(v.begin(), unique(ALL(v))));
}
int get(int x){
return distance(v.begin(), lower_bound(ALL(v), x));
}
} lisan;
class SegTree{...
