HDU3333 – Turing Tree(离线树状数组||在线主席树)

题目链接：HDU3333

【题意】给出N长的序列，Q个询问(x,y)，输出[x,y]所有不同的数之和。

【分析】和spoj dquery基本一样，只是这里是求和的，首先可以用离线做法，给每个查询按右值从小到大排序，然后用树状数组维护当前序列不同数前缀和，按照排序好后的询问计算，同时根据右值把a一个一个加入，当前a[i]如果在[1~i-1]出现过则需要把树状数组前面那一个位置的a[i]删除，在i位置插入a[i]，这样不会错？因为我们对右值排序后，需要把每个值出现的位置尽量往右边移，如果a[i]在i-3出现过而不把i-3删除放到i的话查询区间为[i-2,i]时会把这个a[i]漏掉，而如果查询区间为[1,i]的话也不会影响答案，因为只算一次嘛。这样复杂度为n*logn+q*logn

【AC CODE】530ms

#include <cstdio>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MAXN 30010
struct QUERY{
	int x,y, num;
	bool operator<(const QUERY& t)const{return y < t.y;}
}query[100010];
LL cnt[MAXN], a[MAXN], n, ans[100010];
unordered_map<LL,int> vis;

inline int lowbit(int x){return x&-x;}
void update(int x, LL d)
{
	while(x <= n)
	{
		cnt[x] += d;
		x += lowbit(x);
	}
}
LL sum(int x)
{
	LL ans = 0;
	while(x > 0)
	{
		ans += cnt[x];
		x -= lowbit(x);
	}
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d%*c", &t);
	while(t--)
	{
		scanf("%d%*c", &n);
		repe(i,1,n) scanf("%I64d%*c", &a[i]);
		int q;
		scanf("%d%*c", &q);
		rep(i,0,q)
		{
			scanf("%d %d%*c", &query[i].x, &query[i].y);
			query[i].num = i;
		}
		sort(query,query+q);
		vis.clear();
		clc(cnt,0);
		int p = 1;
		rep(i,0,q)
		{
			int st = query[i].x, ed = query[i].y;
			for(;p <= ed; p++)
			{
				if(!vis.count(a[p])) update(p,a[p]);
				else
				{
					update(vis[a[p]],-a[p]);
					update(p,a[p]);
				}
				vis[a[p]] = p;
			}
			ans[query[i].num] = sum(ed)-sum(st-1);
		}
		rep(i,0,q) printf("%I64d\n", ans[i]);
	}
	return 0;
}

第二种可以用主席树实现在线查询，对每个位置建一棵主席树，每颗树记录的区间信息为[1~n]位置上的不重复权值和(第k大主席树记录的是值域，和这里不同)。从左往右建树，这样rt[i]树表示[1~i]所有不同值之和，然后和上面一样把重复出现的值的位置劲量往右移，当出现过a[i]时先删除rt[i-1]中对应位置的a[i]再把它加入到当前树中的i位置，查询的时候只要查询rt[y]树中[x,y]区间之和即可。

【AC CODE】951ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 30000+10, MAXM = MAXN*50;
int lc[MAXM],rc[MAXM],tol;
LL sum[MAXM];
int a[MAXN], rt[MAXN];
unordered_map<int,int> vis;

void update(int &u, int x, int y, int p, LL v)
{
    sum[tol] = sum[u]+v,lc[tol] = lc[u],rc[tol] = rc[u];
    u = tol++;
    if(x == y) return;
    int m = (x+y)>>1;
    if(p <= m) update(lc[u],x,m,p,v);
    else update(rc[u],m+1,y,p,v);
}
LL query(int u, int x, int y, int ql, int qr)
{
    if(ql <= x && y <= qr) return sum[u];
    int m = (x+y)>>1;
    LL ans = 0;
    if(ql <= m) ans += query(lc[u],x,m,ql,qr);
    if(qr > m) ans += query(rc[u],m+1,y,ql,qr);
    return ans;
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d%*c", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        repe(i,1,n) scanf("%d", &a[i]);
        tol = 1;
        vis.clear();
        repe(i,1,n)
        {
            rt[i] = rt[i-1];
            if(vis.find(a[i]) != vis.end())
            {
                int tmp = rt[i-1];
                update(tmp,1,n,vis[a[i]],-a[i]);
                rt[i] = tmp;
                update(rt[i],1,n,i,a[i]);
            }
            else
            {
                rt[i] = rt[i-1];
                update(rt[i],1,n,i,a[i]);
            }
            vis[a[i]] = i;
        }
        int q;
        scanf("%d", &q);
        rep(i,0,q)
        {
            int x,y;
            scanf("%d %d", &x, &y);
            printf("%I64d\n", query(rt[y],1,n,x,y));
        }
    }
    return 0;
}