hdu 3333 Turing Tree (求区间中不相同数的和，离线+线段树/树状数组)
喵呜，离散树状数组。
这道题由于相同的值加和的时候只算一次，所以比较伤脑筋==
怎么办呢？
我们发现对于一个值，由于相同的只算一次，所以在任意时间内，这个值只需要出现一次。
如果我们从作往右将原数组更新到树状数组，如果某个值之前出现过，那么我在更新当前的时候，还需要删掉之前那个。
这样就可以保证当前的序列中一个值只出现了一次，而且位置更新成最后出现的位置。
如果只出现一次的话那就又是我们喜闻乐见的那个熟悉的树状数组了呢 喵呜！
但是这样删掉前面出现的元素真心大丈夫？ 万一之后又查询了之前你删掉的点岂不是整个人都萌萌哒了？
所以我们可以按照查询区间的又断点排序，保证前面删掉的点以后不会再被查询。
也就是按照顺序，从左往右，边查询，边更新原数组到树状数组。
由于查询区间是无序的，按照右端点排序之后打乱了原来的查询顺序，所以要离线操作。
由于查询区间是无序的，按照右端点排序之后打乱了原来的查询顺序，所以要离线操作。
由于查询区间是无序的，按照右端点排序之后打乱了原来的查询顺序，所以要离线操作。
** **重要的事情说三遍。
所谓离线操作，就是查询的时候不直接输出答案，而是将答案存起来，然后最后一起输出。
我们需要开一个数组pre [x] 记录x这个数的上一个位置，初始为-1
由 x的范围太大，数组存不下，所以要离散化。
离散化是为了记录一个数上次出现的位置！
注意要开LL 。
/*************************************************************************
> File Name: code/hdu/3333.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月07日 星期五 17时04分07秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=3E4+3;
25LL c[N];
26LL n,m,qur;
27LL ref[N];
28LL pre[N];
29LL ori[N];
30struct Q
31{
32 LL val,id;
33}q[N];
1struct S
2{
3 LL x,y;
4 LL id,ans;
5}s[100005];
1bool cmp( Q a,Q b)
2{
3 if (a.val<b.val) return true;
4 return false;
5}
6bool cmp2(S a,S b)
7{
8 if (a.y<b.y) return true;
9 return false;
10}
1LL lowbit ( int x)
2{
3 return x&(-x);
4}
1void update ( LL x,LL delta)
2{
3 for ( LL i = x ; i <= n ; i = i + lowbit(i))
4 {
5 c[i] = c[i] + delta;
6 }
7}
8LL sum( LL x)
9{
10 LL res = 0 ;
11 for ( LL i = x; i >= 1 ; i = i - lowbit(i))
12 {
13 res = res + c[i];
14 }
15 return res;
16}
17int main()
18{
19 int T;
20 cin>>T;
21 while (T--)
22 {
23 memset(ref,0,sizeof(ref));
24 memset(c,0,sizeof(c));
25 memset(pre,-1,sizeof(pre)); //标记上次出现位置的数组
26 scanf("%lld",&n);
27 for ( LL i = 1 ; i <= n ; i++)
28 {
29 scanf("%lld",&q[i].val);
30 q[i].id = i;
31 }
32 sort(q+1,q+n+1,cmp);
33 LL cnt = 0;
34 for ( LL i = 1 ; i <= n ; i++ )
35 {
36 if (q[i].val!=q[i-1].val)
37 {
38 cnt++;
39 }
40 ref[q[i].id] = cnt;
41 ori[q[i].id] = q[i].val;
42 }
1 scanf("%lld",&qur);
2 for ( LL i = 1 ;i <= qur; i++ )
3 {
4 scanf("%lld %lld",&s[i].x,&s[i].y);
5 s[i].id = i;
6 }
7 sort(s+1,s+1+qur,cmp2);
8 s[0].y = 0;
9 for ( LL i = 1 ; i <= qur ; i++)
10 {
11 for ( LL j = s[i-1].y+1 ; j <= s[i].y ; j++)
12 {
13 int tmp = ref[j];
14 if (pre[tmp]==-1)
15 {
16 update(j,ori[j]);
17 }
18 else
19 {
20 update (j,ori[j]);
21 update (pre[tmp],-ori[j]);
22 }
23 pre[tmp] = j;
24 }
25 s[s[i].id].ans = sum(s[i].y)-sum(s[i].x-1);
26 }
27 for ( int i = 1 ; i <= qur ; i++ )
28 {
29 cout<<s[i].ans<<endl;
30 }
}
return 0;
}
update:20160916,写了个线段树的版本。
1/* ***********************************************
2Author :111qqz
3Created Time :Fri 16 Sep 2016 08:26:34 PM CST
4File Name :code/hdu/r3333.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=3E4+7;
32const int M=1E5+7;
33LL tree[N<<2];
34LL a[N];
35int n,m;
36struct node
37{
38 int l,r;
39 int id;
40 bool operator < (node b)
41 {
42 if (r==b.r) return l<b.l;
43 return r<b.r;
44 }
45}q[M];//把M写成N
46void PushUp( int rt)
47{
48 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
49}
50void update( int p,LL sc,int l,int r,int rt)
51{
52 if (l==r)
53 {
54 tree[rt]+=sc;
55 return;
56 }
57 int m = (l+r)>>1;
58 if (p<=m)update(p,sc,lson);
59 else update(p,sc,rson);
60 PushUp(rt);
61}
62LL query(int L,int R,int l,int r,int rt)
63{
64 if (L<=l&&r<=R) return tree[rt];
65 int m = (l+r)>>1;
66 LL ret = 0 ;
67 if (L<=m) ret+= query(L,R,lson);
68 if (R>=m+1) ret+=query(L,R,rson);
69 return ret;
70}
71map<LL,int>mp;
72LL ans[M]; //把M写成N
73int main()
74{
75 #ifndef ONLINE_JUDGE
76 freopen("code/in.txt","r",stdin);
77 #endif
78 int T;
79 scanf("%d",&T);
80 while (T--)
81 {
82 ms(tree,0);
83 ms(ans,0);
84 mp.clear();
85 scanf("%d",&n);
86 for ( int i = 1; i <= n ; i++) scanf("%lld",a+i);
87 scanf("%d",&m);
88 for ( int i = 1 ; i <= m ; i++)
89 {
90 int a,b;
91 scanf("%d%d",&a,&b);
92 q[i].l = a;
93 q[i].r = b;
94 q[i].id = i ;
95 }
96 sort(q+1,q+m+1);
97 int l = 1;
98 for ( int i = 1 ; i <= m ; i++)
99 {
100 for ( ; l <= q[i].r ; l++)
101 {
102 if (mp[a[l]]) update(mp[a[l]],-a[l],1,n,1);
103 mp[a[l]] = l ;
104 update(mp[a[l]],a[l],1,n,1);
105 }
106 ans[q[i].id] = query(q[i].l,q[i].r,1,n,1);
107 }
108 for ( int i = 1 ; i <= m ; i++) printf("%lld\n",ans[i]);
109 }
110 #ifndef ONLINE_JUDGE
111 fclose(stdin);
112 #endif
113 return 0;
114}