【树状数组】洛谷 P4113 采花
2021-06-02 17:13:00 # ACM

—–

题链

可将询问按$L$从小到大排序，每次将序列中花朵第二次出现的位置置为$1$，用树状数组维护；

–树状数组

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
92
93
94
95
96
97
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm> 
#include <ctime>
#include <cmath>
#include <stdio.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 2e6
#define MS 2000009

LL n,m,k;
LL a[MS];
LL fr[MS]; // 记录第一次出现的位置 
LL aft[MS]; // 记录后一个相同值出现的位置 
LL v[MS];
LL p[MS];
struct node{
	int l,r;
	int id;
}ask[MS];
LL ac[MS];

bool cmp(node t1,node t2){
	return t1.l < t2.l;
}

LL lowbit(LL x){
	return x&(-x);
}

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

LL query(int pos){
	LL ans = 0;
	for(;pos;pos-=lowbit(pos)) ans += p[pos];
	return ans; 
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		if(!fr[a[i]]) fr[a[i]] = i;
	}
	
	for(int i=1;i<=m;i++){
		v[i] = n+1;
	}
	for(int i=n;i>=1;i--){
		aft[i] = v[a[i]];
		v[a[i]] = i;
	}
	aft[n+1] = n+1;
	
	for(int i=1;i<=m;i++){
		if(fr[i]){
			add(aft[fr[i]],1);
		}
	}
	
	for(int i=1;i<=k;i++){
		int l,r;
		cin >> l >> r;
		ask[i] = {l,r,i};
	}
	sort(ask+1,ask+k+1,cmp);
	
	for(int i=1,L=1;i<=k;i++){
		while(L < ask[i].l){
			add(aft[L],-1);
			add(aft[aft[L]],1);
			L++;
		}
		LL ans = query(ask[i].r);
		ac[ask[i].id] = ans;
	}
	
	for(int i=1;i<=k;i++){
		cout << ac[i] << "\n";
	}
	cout << "\n";
	

	return 0;
}

动态开点线段树

额…复习一下；吸氧过

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm> 
#include <ctime>
#include <cmath>
#include <stdio.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL int
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 2e6
#define MS 2000009

LL n,m,k;
LL a[MS];
LL fr[MS];
LL aft[MS];
LL v[MS];
struct node{
	int l,r;
	int id;
}ask[MS];
struct nod{
	int l,r;
	LL val;
}p[MS<<5];
int tot;
int root;
LL ac[MS];

bool cmp(node t1,node t2){
	return t1.l < t2.l;
}

void push_up(int &rt){
	if(!p[rt].l && !p[rt].r){
		rt = 0;
	}
	else if(!p[rt].l){
		p[rt].val = p[p[rt].r].val;
	}
	else if(!p[rt].r){
		p[rt].val = p[p[rt].l].val;
	}
	else{
		p[rt].val = p[p[rt].l].val + p[p[rt].r].val;
	}
}

void update(int &rt,int pos,int l,int r,LL val){
	if(!rt) rt = ++tot;
	if(l == r){
		p[rt].val = val;
		if(!p[rt].val) rt = 0;
		return;
	}
	int m = l+r>>1;
	if(m >= pos) update(p[rt].l,pos,l,m,val);
	else update(p[rt].r,pos,m+1,r,val);
	push_up(rt);
}

LL query(int rt,int L,int R,int l,int r){
	if(!rt) return 0;
	if(L <= l && r <= R){
		return p[rt].val;
	}
	int m = l+r>>1;
	LL ans = 0;
	if(m >= L) ans += query(p[rt].l,L,R,l,m);
	if(m <  R) ans += query(p[rt].r,L,R,m+1,r);
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		v[i] = n+1;
		if(!fr[a[i]]) fr[a[i]] = i;
	}
	
	for(int i=n;i>=1;i--){
		aft[i] = v[a[i]];
		v[a[i]] = i;
	}
	aft[n+1] = n+1;
	
	for(int i=1;i<=m;i++){
		if(fr[i] && aft[fr[i]] != n+1){
			update(root,aft[fr[i]],1,MAXN,1);
		}
	}
	for(int i=1;i<=k;i++){
		int l,r;
		cin >> l >> r;
		ask[i] = {l,r,i};
	}
	sort(ask+1,ask+k+1,cmp);
	for(int i=1,L=1;i<=k;i++){
		while(L < ask[i].l){
			if(aft[L] != n+1){
				update(root,aft[L],1,MAXN,0);
				if(aft[aft[L]] != n+1){
					update(root,aft[aft[L]],1,MAXN,1);
				}
			}
			L++;
		}
		LL ans = query(root,ask[i].l,ask[i].r,1,MAXN);
		ac[ask[i].id] = ans;
	}
	for(int i=1;i<=k;i++){
		cout << ac[i] << "\n";
	}
	cout << "\n";
	

	return 0;
}

Prev
2021-06-02 17:13:00 # ACM
Next