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;
}