[SPOJ] DQUERY - D-query (持久化)

題目連結:http://www.spoj.com/problems/DQUERY/

---

被雷了才會做QQ，本題有兩種做法，一種是持久化線段樹，作法滿特別的(?，序列要將在每個時間點最遠的各個數字改成一，其他改成零(如圖)
那詢問一個$[l, r]$時，就只要對第$r$時間點的線段樹詢問$[l, r]$即可。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ALL(x) (x).begin(), (x).end()

const int N = 30000 + 5;
const int MEM = 900000;

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));
		}
} lisan;

class SegTree{
	private:
		struct Node{
			int val, lc, rc;
			Node(){val=0;lc=-1;rc=-1;}
		};
		static Node nodes[MEM];
		static int _mem;
		inline int _new(){
			assert(_mem < MEM);
			nodes[_mem]=Node();
			return _mem++;
		}
		int size;
		int build(int l, int r, int id){
			if(id==-1) id = _new();
			if(r-l>1){
				int mid=(l+r)>>1;
				nodes[id].lc = build(l, mid, nodes[id].lc);
				nodes[id].rc = build(mid, r, nodes[id].rc);
			}
			return id;
		}
		int query(int ql, int qr, int l, int r, int id){
			if(qr <= l or r <= ql) return 0;
			if(ql <= l and r <= qr) return nodes[id].val;
			int mid=(l+r)>>1;
			int ll = query(ql, qr, l, mid, nodes[id].lc);
			int rr = query(ql, qr, mid, r, nodes[id].rc);
			return ll+rr;
		}
		int modify(int ql, int qr, int v, int l, int r, int id){
			if(qr <= l or r <= ql) return id;
			int nid = _new();
			nodes[nid] = nodes[id];
			if(ql <= l and r <= qr){
				nodes[nid].val = v;
				return nid;
			}
			int mid = (l+r)>>1;
			int ll = modify(ql, qr, v, l, mid, nodes[id].lc);
			int rr = modify(ql, qr, v, mid, r, nodes[id].rc);
			nodes[nid].val = nodes[ll].val + nodes[rr].val;
			nodes[nid].lc = ll;
			nodes[nid].rc = rr;
			return nid;
		}
	public:
		int build(int n){
			size=n;
			return build(0, n, -1);
		}
		int query(int l, int r, int id){
			return query(l, r, 0, size, id);
		}
		int modify(int p, int v, int id){
			return modify(p, p+1, v, 0, size, id);
		}
};
int SegTree::_mem=0;
SegTree::Node SegTree::nodes[MEM];
SegTree seg;

int arr[N], pos[N], roots[N];

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