spoj DQUERY(树状数组+离线/主席树)

发表于 | 分类于 | | + s

spoj DQUERY
caioj 1445
题意：给出一个$n$个数的序列，求区间$[l,r]$里有多少种不同数字。

树状数组离线作法：
我们将所有询问离线，按$r$排序。树状数组维护区间。然后不断根据询问向右加点加到$r$(排序避免删点)，如果当前数之前没有出现过，直接在树状数组该位置加$1$。否则就把之前出现这个值的位置减$1$，为的是把数尽可能放到右边，因为记录值中位置不影响答案。这样就方便求解$[l,r]$的信息，直接减即可，正确性显然，因为数都尽可能在右边。

主席树做法：
与树状数组类似，主席树维护区间，相当于可持久化维护每次加点后的情况。每个点按顺序建树，如果这个点的数之前没有出现过，直接在本棵主席树该位置加$1$。否则就把之前出现这个值的位置减$1$，再重复做没有出现的情况。为的是把数尽可能放到右边，因为记录值中位置不影响答案。这样就方便求解$[l,r]$的信息。
询问直接用右端点的主席树，由于上述操作后答案可减，所以直接把右端点的主席树左端点以右的值求和即可

树状数组离线做法：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 50000 + 5;
struct data {
    int l, r, id;
    bool operator < (const data &b) const {
        return r < b.r;
    }
}qj[200000 + 5];
int n, q, ai[MAXN], c[MAXN], lst[1000000 + 5], ans[200000 + 5];
int lowbit(int x) {return x & (-x);}
void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) c[i] += v;
}
int query(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= lowbit(i)) ret += c[i];
    return ret;
}
void clean() {
    ms(lst, -1);
}
int solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]); scanf("%d", &q);
    for (int i = 1; i <= q; i++) scanf("%d%d", &qj[i].l, &qj[i].r), qj[i].id = i;
    sort(qj + 1, qj + 1 + q);
    int now = 1;
    for (int i = 1; i <= q; i++) {
        while (now <= qj[i].r) {
            if (lst[ai[now]] < 0) add(now, 1); else add(lst[ai[now]], -1), add(now, 1);
            lst[ai[now]] = now, now++;
        }
        ans[qj[i].id] = query(qj[i].r) - query(qj[i].l - 1);
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0; 
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}

主席树做法：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 30000 + 5;
int n, q, sz, ai[MAXN], rt[MAXN], lst[1000000 + 5];
#define M ((l + r) >> 1)
int sumv[MAXN * 20], lc[MAXN * 20], rc[MAXN * 20];
int mge(int &x, int y) {//主席树x合并主席树y 
    if (y == 0) return 0;
    if (x == 0) return x = y, 0;
    sumv[x] += sumv[y];
    mge(lc[x], lc[y]), mge(rc[x], rc[y]);
    return 0;
}
void build(int l, int r, int &x, int pos, int v) {//建链维护[l,r], 主席树上x点，修改位置和值 
    if (x == 0) x = ++sz, lc[x] = rc[x] = sumv[x] = 0;
    sumv[x] += v;
    if (l == r) return ;
    if (pos <= M) build(l, M, lc[x], pos, v); else build(M + 1, r, rc[x], pos, v);
}
int query(int l, int r, int x, int u) {//查询[l,r]答案，主席树上x点，左边临界点u 
    if (l == r) return 0;
    if (u <= M) return sumv[rc[x]] + query(l, M, lc[x], u); //加上右边，查询左边
    else return query(M + 1, r, rc[x], u); //不要加左，左边有临界点
}
void clean() {
    sz = 0, ms(lst, -1);
}
int solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]);
    for (int i = 1; i <= n; i++) {//维护 [0, n] 区间，因为l - 1可能为 0
        if (lst[ai[i]] < 0) build(0, n, rt[i], i, 1), mge(rt[i], rt[i - 1]);//之前没有
        else {
            build(0, n, rt[i], lst[ai[i]], -1), build(0, n, rt[i], i, 1);
            mge(rt[i], rt[i - 1]);
        }//之前有
        lst[ai[i]] = i;
    }
    scanf("%d", &q);
    while (q--) {
        int l, r; scanf("%d%d",&l, &r);
        printf("%d\n", query(0, n, rt[r], l - 1));
    }
    return 0; 
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}
------ 本文结束 ------