# 某岛

… : "…アッカリ～ン . .. . " .. .
August 8, 2014

# SPOJ 3267. D-query

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

UVa 12345. Dynamic len(set(a[L:R]))

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];
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){
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