【线段树】2021牛客寒假算法基础集训营3 E-买礼物
2021-03-03 17:03:00 # ACM

题链

线段树记录第i个礼物与之相同的后一个礼物的位置；
LL $p[MS]$; // 记录第$i$个礼物 后一个礼物位置
LL $q[MS];$ // 记录第$i$个礼物 前一个礼物位置
关于修改：
$1.$删除第$pos$个礼物：在线段树中将其置为$INF$(表示该礼物不存在)，删除后该礼物左右所指向的礼物位置则需要更改;
$2.$第$pos$个礼物与之相同的前一个礼物，该礼物所指向的后一个礼物位置需要更新，即在线段树上修改$p[q[pos]]$的值为$p[pos]$;
$3.$第$pos$个礼物与之相同的后一个礼物，该礼物所指向的前一个礼物位置需要更新，更新$q[p[pos]]$为$q[pos]$; 

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
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define MS 500009
#define INF 1e18
#define mod 998244353
#define Pi acos(-1.0)
#define Pair pair<LL,LL>

LL n,m,k;
LL p[MS]; // 记录第i个礼物 后一个礼物位置 
LL q[MS]; // 记录第i个礼物 前一个礼物位置 
LL a[MS]; // 原数组 
LL ne[1000009];
LL fr[1000009];
LL tr[MS<<2];

void push_up(int rt){
	tr[rt] = min(tr[ls],tr[rs]);
}

void build(int l,int r,int rt){
	if(l == r){
		tr[rt] = p[l];
		return;
	}
	int m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
	push_up(rt);
}

void update_change(int L,int R,int l,int r,int rt,LL val){
	if(L <= l && r <= R){
		tr[rt] = val;
		return;
	}
	int m = l+r>>1;
	if(m >= L) update_change(L,R,l,m,ls,val);
	if(m <  R) update_change(L,R,m+1,r,rs,val);
	push_up(rt);
}

LL get_min(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R) return tr[rt];
	int m = l+r>>1;
	LL ans = INF;
	if(m >= L) ans = min(ans,get_min(L,R,l,m,ls));
	if(m <  R) ans = min(ans,get_min(L,R,m+1,r,rs));
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=0;i<=1000000;i++){
		fr[i] = 0;
		ne[i] = INF;
	} 
	for(int i=n;i>=1;i--){
		p[i] = ne[a[i]];
		ne[a[i]] = i;
	}
	for(int i=1;i<=n;i++){
		q[i] = fr[a[i]];
		fr[a[i]] = i;
	}
	
	build(1,n,1);
	while(m--){
		LL op,l,r,pos;
		cin >> op;
		if(op == 1){
			cin >> pos;
			update_change(pos,pos,1,n,1,INF);
			if(q[pos] != 0){
				p[q[pos]] = p[pos];
				update_change(q[pos],q[pos],1,n,1,p[pos]);
			} 
			if(p[pos] != INF){
				q[p[pos]] = q[pos];
			}
		}
		else{
			cin >> l >> r;
			if(get_min(l,r,1,n,1) <= r) cout << 1 << endl;
			else cout << 0 << endl;
		}
	}
	
	
	return 0;
}
Prev
2021-03-03 17:03:00 # ACM
Next