题意:给出N个数字,Q个询问。
每次询问输出区间【L,R】范围内不重复的数的和。
思路:离线操作,先将区间都存起来,然后根据R来从小到大排序。
每次更新值,当值已经存在,则在前一位置减去该值。这样可以保证询问区间内的数是唯一的。
具体见代码。
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 2005 #define inf 2000000000 #define LL(x) (x<<1) #define RR(x) (x<<1|1) #define REP(i,s,t) for(int i=(s);i<=(t);++i) #define ll __int64//这题用long long交会WA 。不解 #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) using namespace std; inline void RD(int &ret) { char c; do { c = getchar(); } while(c < '0' || c > '9'); ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); } struct kdq { int l ,r ,id ; } qe[200005] ; int a[50005] ; int n ; ll c[50005] ; int vis[1000005] ; ll ans[200005] ; int lowbit(int x ) { return x & (-x) ; } bool cmp(kdq a ,kdq b) { if(a.r == b.r)return a.l < b.l ; return a.r < b.r ; } void add(int x ,int num) { for (int i = x ; i <= n ; i += lowbit(i))c[i] += num ; } ll sum(int x ) { ll ans = 0ll ; for (int i = x ; i > 0 ; i -= lowbit(i))ans += c[i] ; return ans ; } ll sum(int x ,int y) { return (ll)(sum(x) - sum(y - 1)) ; } int main() { #ifndef ONLINE_JUDGE freopen("acm.txt", "r", stdin); #endif int T ; RD(T) ; while( T -- ) { RD(n) ; mem(c,0) ; mem(vis,0) ; REP(i,1,n)RD(a[i]) ; int Q ; RD(Q) ; REP(i,0,Q - 1) { RD(qe[i].l) ; RD(qe[i].r) ; qe[i].id = i ; } sort(qe , qe + Q , cmp) ; int e = 1 ; REP(i,0,Q - 1) { while(e <= qe[i].r) { if(vis[a[e]] != 0) add(vis[a[e]],-a[e]) ; vis[a[e]] = e ; add(e,a[e]) ; e ++ ; } ans[qe[i].id] = sum(qe[i].r,qe[i].l ) ; } REP(i,0,Q - 1)printf("%I64d\n",ans[i]) ; } return 0; }