Hdu-3333 Turning Tree （离线树状数组/线段树）

题目大意：先给出n个数字。面对q个询问区间，输出这个区间不同数的和。

题解：这道题有多重解法。我另一篇博客写了分块的解法 HDU-3333 Turing Tree 分块求区间不同数和。

这里讲一下离线树状数组或者线段树的解法。

先讲一下我们在线（按询问顺序）做这道题会有什么麻烦。因为一个区间重复的数我们只算一个，那么我们认为对于一个区间，重复的数我们只算最接近区间右段点的哪一个。但是因为按询问顺序，它的右端点是会起伏的。所以我们不好统计到底对于每一个询问区间，哪一个才是该区间重复数中有效的哪一个。

那么我们转变一下思路。改成离线算法。先把询问区间按右端点排序。那么因为区间右段点的单调性，按照这个顺序我们可以只算重复数的最右边的那个。

具体做法是排序询问右端点r，把1-r的数都加入到树状数组。如果该数在前面有重复数last[i]。那么就把last[i]的值在树状数组去掉，把r点的值在树状数组上加上。那么保证在1-r内每个数只会出现一次。

AC代码如下：

#include<iostream>

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

const int N=+;

const int M=+;

struct node{

    int x,y,num;

    bool operator < (const node& t) {

        return y<t.y;

    }

}q[M];

int n,m,a[N];

long long sum[*N],ans[M],last[N];

map<int,int> lst;

int lowbit(int x) { return x&(-x); }

void update(int x,int v) {

    while (x<=n) {

        sum[x]+=v;

        x+=lowbit(x);

    }

}

long long query(int x) {

    long long ans=;

    while (x) {

        ans+=sum[x];

        x-=lowbit(x);

    }

    return ans;

}

int main()

{

    int T;

    scanf("%d",&T);

    while (T--) {

        scanf("%d",&n);

        for (int i=;i<=n;i++) scanf("%d",&a[i]);

        lst.clear();

        for (int i=;i<=n;i++) last[i]=;

        for (int i=;i<=n;i++) {

            last[i]=lst[a[i]];

            lst[a[i]]=i;

        }

        scanf("%d",&m);

        for (int i=;i<=m;i++) {

            scanf("%d%d",&q[i].x,&q[i].y);

            q[i].num=i;

        }

        sort(q+,q+m+);

        int now=;

        for (int i=;i<=n;i++) sum[i]=;

        for (int i=;i<=m;i++) {

            while (now<q[i].y) {

                now++;

                update(now,a[now]);

                if (last[now]) update(last[now],-a[now]);

            }

            ans[q[i].num]=query(q[i].y)-query(q[i].x-);

        }

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

    }

    return ;

}

巴特西

Hdu-3333 Turning Tree （离线树状数组/线段树）

最新文章

热门文章