[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{
	private:
		vector<int> nodes[4*N];
		int size;
		inline int lc(int x){return (x<<1)+1;}
		inline int rc(int x){return (x<<1)+2;}
		void build(int l, int r, int id, int arr[]){
			if(r-l==1){
				nodes[id].PB(arr[l]);
				return;
			}
			int mid = (l+r)>>1;
			build(l, mid, lc(id), arr);
			build(mid, r, rc(id), arr);
			int _=0;
			for(int i=0;i<(int)nodes[lc(id)].size();++i){
				while(_ < (int)nodes[rc(id)].size() and \
					nodes[rc(id)][_] < nodes[lc(id)][i]){
					nodes[id].PB(nodes[rc(id)][_++]);
				}
				nodes[id].PB(nodes[lc(id)][i]);
			}
			while(_ < (int)nodes[rc(id)].size()) nodes[id].PB(nodes[rc(id)][_++]);
		}
		int query(int ql, int qr, int l, int r, int id, int x){
			if(qr <= l or r <= ql) return 0;
			if(ql <= l and r <= qr)
				return distance(lower_bound(ALL(nodes[id]), x), nodes[id].end());
			int mid=(l+r)>>1;
			int ll = query(ql, qr, l, mid, lc(id), x);
			int rr = query(ql, qr, mid, r, rc(id), x);
			return ll+rr;
		}
	public:
		void build(int n, int arr[]){
			size=n;
			build(0, n, 0, arr);
		}
		int query(int l, int r, int x){
			return query(l, r, 0, size, 0, x);
		}
} seg;

int arr[N], pos[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	fill(pos, pos+n, INF);
	for(int i=0;i<n;i++){
		cin>>arr[i];
		lisan.insert(arr[i]);
	}
	lisan.done();
	for(int i=n-1;i>=0;--i){
		int x = lisan.get(arr[i]);
		arr[i] = pos[x];
		pos[x]=i;
	}
	seg.build(n, arr);
	int q; cin>>q;
	while(q--){
		int l, r; cin>>l>>r;
		cout<<seg.query(l-1, r, r)<<'\n';
	}
	return 0;
}