- 1
- #include
- 2
- #include
- 3
- #include
- 4
- #include<
- string
- >
- 5
- #include
- 6
- #include
- 7
- #include
- 8
- #include
- 9
- #include
- 10 using namespace std;
- 11 const int
- maxn=1e5+
- 3;
- 12
- typedef
- long long ll;
- 13 int n,m;
- 14
- vector
- int
- ,
- int
- > >
- p[maxn];
- 15
- map
- int
- >
- pre;
- 16
- 17 ll tree[maxn];
- 18 ll a[maxn];
- 19 ll ans[maxn];
- 20 void init()
- 21 {
- 22
- memset(ans,
- 0
- ,
- sizeof(ans));
- 23 for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- 24 {
- 25
- tree[i]=
- 0LL;
- 26 }
- 27 pre.clear();
- 28 }
- 29 int
- lowbit(
- int x)
- 30 {
- 31 return
- x&(-
- x);
- 32 }
- 33 void
- add(
- int k,ll x)
- 34 {
- 35 while
- (k<=
- n)
- 36 {
- 37
- tree[k]+=
- x;
- 38
- k+=
- lowbit(k);
- 39 }
- 40 }
- 41
- 42
- ll query(
- int k)
- 43 {
- 44
- ll res=
- 0LL;
- 45 while(k)
- 46 {
- 47
- res+=
- tree[k];
- 48
- k-=
- lowbit(k);
- 49 }
- 50 return res;
- 51 }
- 52
- ll query(
- int
- l,
- int r)
- 53 {
- 54 return
- query(r)-query(l-
- 1);
- 55 }
- 56 int main()
- 57 {
- 58 int T;
- 59
- scanf(
- "%d"
- ,&
- T);
- 60 while
- (T--
- )
- 61 {
- 62
- scanf(
- "%d"
- ,&
- n);
- 63 init();
- 64 for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- 65 {
- 66
- cin>>
- a[i];
- 67 p[i].clear();
- 68 }
- 69
- scanf(
- "%d"
- ,&
- m);
- 70 int u,v;
- 71 for
- (
- int
- i=
- 1
- ;i<=m;i++
- )
- 72 {
- 73
- scanf(
- "%d%d"
- ,&u,&
- v);
- 74 p[v].push_back(make_pair(u,i));
- 75 }
- 76 for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- 77 {
- 78 if(pre.count(a[i]))
- 79 {
- 80
- add(pre[a[i]],-
- a[i]);
- 81 }
- 82
- pre[a[i]]=
- i;
- 83 add(i,a[i]);
- 84 int
- sz=
- p[i].size();
- 85 for
- (
- int
- k=
- 0
- ;k
- )
- 86 {
- 87
- ans[p[i][k].second]=
- query(p[i][k].first,i);
- 88 }
- 89 }
- 90 for
- (
- int
- i=
- 1
- ;i<=m;i++
- )
- 91 {
- 92
- cout<
- endl;
- 93 }
- 94 }
- 95 return 0;
- 96
- }
来源: http://www.bubuko.com/infodetail-2157580.html