题目链接: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; }