http://www.spoj.com/problems/DQUERY/

http://www.2333333.tk/277.html

做法一：

離線 + 樹狀數組：

//}/* .................................................................................................................................. */ const int N = int(3e4) + 9, QN = int(2e5) + 9; int A[N], pre[N]; vector<PII> qry[N]; int ans[QN], n, m; namespace BIT{ const int N = int(3e4) + 9, M = int(2e5) + 9; int C[N]; void Add(int x, int d){ for (;x<=n;x+=low_bit(x)) C[x] += d; } int Sum(int x){ int z = 0; for (;x;x^=low_bit(x)) z += C[x]; return z; } } using namespace BIT; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n); VI P; REP_1(i, n) P.PB(RD(A[i])); UNQ(P); REP_1(i, n) A[i] = LBD(P, A[i]); REP_C(i, RD(m)){ int l, r; RD(l, r); qry[l].PB(MP(r, i)); } #define ii pre[A[i]] DWN_1(i, n, 1){ if (ii) Add(ii, -1); Add(i, 1); ii = i; ECH(it, qry[i]) ans[it->se] = Sum(it->fi); } REP(i, m) OT(ans[i]); }

做法二：

主席樹。。。

這個題可以看做是主席樹的入門題。。。

//}/* .................................................................................................................................. */ const int N = int(3e4) + 9, QN = int(2e5) + 9; int T[N], A[N], pre[N], n, m; namespace ST{ #define lx l[x] #define rx r[x] #define ly l[y] #define ry r[y] #define ml (ll + rr >> 1) #define mr (ml + 1) const int NN = N*18 + 9; int l[NN], r[NN], c[NN], tot; int new_node(){ return ++tot; } int Add(int y, int p, int d){ int x = new_node(), root = x; int ll = 1, rr = n; c[x] = c[y] + d; while (ll < rr){ if (p < mr){ lx = new_node(), rx = ry; x = lx, y = ly, rr = ml; } else { lx = ly, rx = new_node(); x = rx, y = ry, ll = mr; } c[x] = c[y] + d; } return root; } int Sum(int x, int p){ int z = 0, ll = 1, rr = n; while (p != rr){ if (p < mr) x = lx, rr = ml; else z += c[lx], x = rx, ll = mr; } z += c[x]; return z; } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n); VI P; REP_1(i, n) P.PB(RD(A[i])); UNQ(P); REP_1(i, n) A[i] = LBD(P, A[i]); #define ii pre[A[i]] DWN_1(i, n, 1){ int x = T[i+1]; if (ii) x = ST::Add(x, ii, -1); x = ST::Add(x, i, 1); ii = i; T[i] = x; } REP_C(i, RD(m)){ int l, r; RD(l, r); OT(ST::Sum(T[l], r)); } }

SPOJ 3267. D-query

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1640753 ( Fotile 式。（不常用。。）

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1640759 ( Seter 式 。。（非遞歸。。）

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1640738（離線 + 樹狀數組 （1500ms