HDU 3333 Turing Tree 莫队算法

题意：

给出一个序列和若干次询问，每次询问一个子序列去重后的所有元素之和。

分析：

先将序列离散化，然后离线处理所有询问。

用莫队算法维护每个数出现的次数，就可以一边移动区间一边维护不同元素之和。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long LL;

const int maxn = 30000 + 10;

const int maxq = 100000 + 10;

int n, m, a[maxn], b[maxn];

int cnt[maxn];

LL ans[maxq];

struct Query

{

    int l, r, id;

    bool operator < (const Query& t) const {

        return ((l / m) < (t.l / m)) || ((l / m) == (t.l / m) && r < t.r);

    }

};

Query q[maxq];

int main()

{

    int T; scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        for(int i = 1; i <= n; i++) { scanf("%d", a + i); b[i] = a[i]; }

        sort(b + 1, b + 1 + n);

        int tot = unique(b + 1, b + 1 + n) - b - 1;

        for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;

        m = sqrt(n);

        int Q; scanf("%d", &Q);

        for(int i = 1; i <= Q; i++) {

            scanf("%d%d", &q[i].l, &q[i].r);

            q[i].id = i;

        }

        sort(q + 1, q + 1 + Q);

        LL sum = 0;

        int L = 1, R = 0;

        memset(cnt, 0, sizeof(cnt));

        for(int i = 1; i <= Q; i++) {

            while(L < q[i].l) {

                cnt[a[L]]--;

                if(!cnt[a[L]]) sum -= b[a[L]];

                L++;

            }

            while(L > q[i].l) {

                L--;

                if(!cnt[a[L]]) sum += b[a[L]];

                cnt[a[L]]++;

            }

            while(R < q[i].r) {

                R++;

                if(!cnt[a[R]]) sum += b[a[R]];

                cnt[a[R]]++;

            }

            while(R > q[i].r) {

                cnt[a[R]]--;

                if(!cnt[a[R]]) sum -= b[a[R]];

                R--;

            }

            ans[q[i].id] = sum;

        }

        for(int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);

    }

    return 0;

}