【线段树】2021牛客暑期多校训练营7 B xay loves monotonicity
2021-09-11 13:54:00 # ACM

题链

题目解析

题意包含三种操作：
  $1.$ 将 $a_{pos}$ 改为 $val$；
  $2.$ 将 $b_l$ 到 $b_r$ 都异或上 $1$；
  $3.$ 求 $f(l,r)$；
定义 $f(l,r)$ 为：
  $1.$ 将 $l$ 加入集合 $S$；
  $2.$ 设 $S$ 末尾值为 $t$，找到最小的 $i$，满足 $i>t$ 并且 $a_i \geq a_t$；
  $3.$ 如果找不到满足条件的 $i$ 则跳至第 $4$ 步，否则将 $i$ 加入到 $S$ 中，跳至第 $2$ 步；
  $4.$ 令 $p_1,p_2, \dots ,p_k$ 为 $S$ 经过排序后的递增序列，$f(l,r)$ 为有多少个 $i \in [l,r)$，满足 $b_{p_i} \neq b_{p_{i+1}}$；

线段树维护节点信息有:{
  $a$ 数组下的区间最大值 $mx$ ；
  最大值对应的 $b$ 数组下的值 $mb$，(如果多个最大值则取最右边的)；
  区间答案 $val$ (也就是 $f(l,r)$ )；
  懒惰标记 $la$ (因为涉及到 $b$ 数组的区间修改)；
}

前两种操作是基本修改操作；
线段树节点信息的 $mx,mb$ 很好维护，难的是如何维护区间答案 $val$ ：

假设维护好了 $ls,rs$ 的节点信息，考虑如何得到 $rt$ 的节点信息：
  $ls.val$ 一定是 $rt.val$ 的组成部分，现在手握着 $ls.mx,ls,mb$ 如何得到 $rs$ 部分的贡献呢？

定义一个函数 $cal(rt,l,r,mx,mb)$ 表示通过现在手握着的 $mx,mb$ 得到在 $[l,r]$ 这个区间内的贡献：
  如果 $ls.mx < mx$，那么 $ls$ 就没有贡献，只需要计算 $cal(rs,m+1,r,mx,mb)$；
  否则可以快速计算出 $rs$ 的贡献 $=rt.val-ls.val$，再加上 $cal(ls,l,m,mx,mb)$；

于是 $rt.val = ls.val + cal(rs,m+1,r,ls.mx,ls.mb)$ 就合并好了两个节点信息；

既然能合并两个节点信息了，就能维护好线段树了，那么对于询问相当于就合并多个节点信息；
至此第 $3$ 中操作也完成了；

复杂度 $O(nlognlogn)$；

代码实现

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ULL unsigned long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define B1 131
	#define B2 13331
	#define M1 1000000007
	#define M2 122777
	#define eps 1e-9
	#define mod 998244353
	#define MAXN 9e18
	#define MS 2000005

int n,m,k;
int a[MS], b[MS];
struct node{
	int mx;
	int mb;
	int val;
	int la;
}p[MS<<2];
node ans;

void push_down(int rt){
	if(p[rt].la){
		p[ls].mb ^= 1; 
		p[rs].mb ^= 1;
		p[ls].la ^= 1;
		p[rs].la ^= 1;
		p[rt].la = 0;
	}
}

int cal(int rt,int l,int r,int mx,int mb){
	if(l == r) return p[rt].mx >= mx? (mb^p[rt].mb):0;
	int m = l+r>>1;
	push_down(rt);
	if(p[ls].mx < mx) return cal(rs,m+1,r,mx,mb);
	else return p[rt].val - p[ls].val + cal(ls,l,m,mx,mb);
}

void push_up(int rt,int l,int r){
	int m = l+r>>1;
	p[rt].val = p[ls].val + cal(rs,m+1,r,p[ls].mx,p[ls].mb);
	if(p[ls].mx <= p[rs].mx) p[rt].mx = p[rs].mx, p[rt].mb = p[rs].mb;
	else p[rt].mx = p[ls].mx, p[rt].mb = p[ls].mb;
}

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

void modify_a(int pos,int l,int r,int rt,int val){
	if(l == r){
		p[rt].mx = val;
		return;
	}
	int m = l+r>>1;
	push_down(rt);
	if(m >= pos) modify_a(pos,l,m,ls,val);
	else modify_a(pos,m+1,r,rs,val);
	push_up(rt,l,r);
}

void modify_b(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		p[rt].mb ^= 1;
		p[rt].la ^= 1;
		return;
	}
	int m = l+r>>1;
	push_down(rt);
	if(m >= L) modify_b(L,R,l,m,ls);
	if(m <  R) modify_b(L,R,m+1,r,rs);
	push_up(rt,l,r);
}

node get_fst(int pos,int l,int r,int rt){
	if(l == r) return p[rt];
	int m = l+r>>1;
	push_down(rt);
	if(m >= pos) return get_fst(pos,l,m,ls);
	else return get_fst(pos,m+1,r,rs);
}

void merge(node &t, int rt,int l,int r){
	t.val += cal(rt,l,r,t.mx,t.mb);
	if(t.mx <= p[rt].mx) t.mx = p[rt].mx, t.mb = p[rt].mb;
}

void query(node &ans,int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		merge(ans,rt,l,r);
		return;
	}
	int m = l+r>>1;
	push_down(rt);
	if(m >= L) query(ans,L,R,l,m,ls);
	if(m <  R) query(ans,L,R,m+1,r,rs);
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) cin >> b[i];
	build(1,n,1);
	cin >> m; 
	while(m--){
		int op; cin >> op;
		if(op == 1){
			int pos,val; cin >> pos >> val;
			modify_a(pos,1,n,1,val);
		}
		else if(op == 2){
			int l,r; cin >> l >> r;
			modify_b(l,r,1,n,1);
		}
		else{
			int l,r; cin >> l >> r;
			ans = get_fst(l,1,n,1);
			query(ans,l,r,1,n,1);
			cout << ans.val << "\n";
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	int ce = 1;
//	cin >> ce;
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/

Prev
2021-09-11 13:54:00 # ACM
Next