http://www.spoj.com/problems/DQUERY/
https://www.shuizilong.com/house/archives/uva-12345-dynamic-lensetalr/
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

Posted by xiaodao
Category: SPOJ