hdu 3333 Turing Tree

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

三鲜图灵树

主要是离线处理。另外要记录每个数字上一次出现的位置，但是数字太大，达到1000000000，所以没办法直接开一个pre[m]数组去记录，所以映射一下（离散化）, 因为最多只有30000个数字

把所有询问读入，按右端点升序排序，然后只需要扫一遍原序列

每扫到一个数字，看看它之前是否出现过，在它上一次出现的位置删除它，然后在当前位置插入它。然后看看这个位置是否是某些询问的右端点，是的话把右端点为该点的询问全部回答。

离散化的这题没怎么应用，就是在判断一个数字是否出现时用了一下

所以说白了就是单点更新（插入，删除），区间求和

这个东西，树状数组做起来容易很多，所以就用树状数组写了，虽然是线段树的题，但线段树应该是比树状数组慢一点的，另外编程复杂度肯定高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
#define N 30010
#define NQ 100010
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int num[N],Hash[N],n,tot,pre[N];
map<int,int>M;
struct ASK{
    int l,r;
    LL res;
}ask[NQ];
vector<int>List[N];
LL c[N];

inline int lowbit(int x){
	return x & (-x);
}

void add(int pos,LL val){
	while(pos <= n){
		c[pos] += val;
		pos += lowbit(pos);
	}
}

LL sum(int pos){
	LL res = 0;
	while(pos){
		res += c[pos];
		pos -= lowbit(pos);
	}
	return res;
}

void solve(){
    cl(c,0); cl(pre,-1);
	for(int i = 1; i <= n; i++){
		int m = M[num[i]];
		if(pre[m] != -1){
			add(pre[m],-num[i]);
		}
		add(i,num[i]);
		pre[m] = i;
		if(!List[i].empty()){
			for(int k = 0; k < List[i].size(); k++){
				int id = List[i][k];
				int l = ask[id].l , r = ask[id].r;
				ask[id].res = sum(r)-sum(l-1);
			}		
		}
	}
}

int main(){
    int T,q;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        M.clear();
        for(int i = 1; i <= n; i++){
            scanf("%d",&num[i]);
            Hash[i] = num[i];
        }
        sort(Hash+1,Hash+n+1);
        tot = 0;
        for(int i = 1; i <= n; i++)
            if(i == 1 || Hash[i] != Hash[i-1]){
                M[Hash[i]] = ++tot;
            }

        for(int i = 1; i <= n; i++) 
			List[i].clear();
        scanf("%d",&q);
		for(int i = 0; i < q; i++){
            scanf("%d%d",&ask[i].l,&ask[i].r);
            List[ask[i].r].pb(i);
        }    
        solve();
        for(int i = 0; i < q; i++)
			printf("%I64d\n",ask[i].res);      
    }
    return 0;
}