2021牛客暑期多校训练营7 B xay loves monotonicity

2021牛客暑期多校训练营7 B xay loves monotonicity

八月 08, 2021

题目概述

给定一个序列$a$,和一个布尔序列$b$.现在有若干修改和询问。

其中修改分成两种，一种是将$a_i$修改为某个值，另一种是修改$b$的一个区间$[L,R]$​，使区间内所有量01反转。

询问。对于$[L,R]$，找出以$a_L$开头的最长非降子序列，记为$a_{p_1},a_{p_2},…a_{p_k}$，回答$b_{p_1},b_{p_2},…b_{p_k}$序列相邻元素不相等的位置数目。

分析与解

这道题给我们最大的启示，就是将线段树看做一个合适的二分递归的结构，从左到右动态地，而不是传统从上到下地访问线段树，并求得一个构造答案。

题目的核心在于快速求一个区间的LIS（非严格）。我们考虑每个线段树节点维护两个量，一个mmax，表示当前处理进程中，从该节点的左端点起的LIS的末端最大值，一个flag表示当前处理进程中，从该节点左端点起的LIS的末端布尔量（对应$b$序列）。

对于单点修改mmax和区间取反flag,都可以用传统线段树的方法做，push_down和push_up。关键看询问。说到底，询问其实是在一个一个拼凑出当前最长的LIS。快速其实就是可以用$logn$来代替线性实现枚举下一个可行的位置。具体而言，我们记状态$(id,nowmax,flag)$表示遍历到当前$id$节点时，左端过往遍历过的LIS的末端最大值为$nowmax$,对应布尔量为$flag$.首先我们要考虑当前节点的左右儿子是否可能接上，就是比较$id.lson.mmax$和$nowmax$，如果比这个$nowmax$​小，那左儿子肯定没戏，直接看右儿子，否则先递归左儿子，导致$nowmax$和$flag$​​​的变更，再拿变更后的两个量去考察右儿子。（如下示意图）

事实上，出于数据定义一致性的考量，我们其实在每个节点push_up的过程中，就顺势计算当前节点左二子的情形导致的新$nowmax$和$flag$​对右儿子的影响，在push_up中query右儿子，这样以来，如先遍历左儿子，再遍历右儿子时，就不用真的遍历右儿子，而是在左儿子pushup过程中解决了右儿子的问题，对答案贡献时直接$id.len -id.lson.len$​即可解决。

这道题的思路似乎有个名字叫线段树区间合并。类似的还有清华集训-楼房重建。

具体细节见代码。

复杂度$O(qlog^2n)$

代码

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
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) (a)<(b) ? (a) : (b)
#define max(a,b) (a)>(b) ? (a) : (b)
typedef long long LL;
int mread() {
	int ret=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9') {
		if(c=='-')f=-1;
		c=getchar();
	}
	do {
		ret=ret*10+c-'0';
		c=getchar();
	} while('0'<=c && c<='9');
	return ret*f;
}
#define MAXN 200100
struct node {
	int mmax,len,l,r;
	int flag,lazy;
} seg[MAXN<<3];
int n,q;
int a[MAXN],b[MAXN];
int ql,qr,qval;
void push_down(int id) {
	if(seg[id].lazy) {
		seg[id<<1].flag^=1,seg[id<<1].lazy^=1;
		seg[id<<1|1].flag^=1,seg[id<<1|1].lazy^=1;
		seg[id].lazy=0;
	}
}
int query(int id,int &now_max,int &flag) { //引用以备后面的查询
//	printf("query:l=%d r=%d now=%d flag=%d\n",seg[id].l,seg[id].r,now_max,flag);
	if(seg[id].l==seg[id].r) { //直到找到合适的单点
		if(seg[id].mmax >= now_max) {
			int ret=(flag!=seg[id].flag);
			if(now_max==-1)ret=0;
			now_max=seg[id].mmax;
			flag=seg[id].flag;
			return ret;
		}
		return 0;
	}
	push_down(id); //!
	if(seg[id<<1].mmax >= now_max) {
		int ret = query(id<<1,now_max,flag) + seg[id].len - seg[id<<1].len; //右半在push_up中计算得到
		now_max=seg[id].mmax;
		flag=seg[id].flag; //同理，已经更新过了
//		printf("for call:%d %d\n",now_max,flag);
		return ret;
	} else return query(id<<1|1,now_max,flag);
}
void push_up(int id) {
	seg[id].mmax=seg[id<<1].mmax;
	seg[id].flag=seg[id<<1].flag;
	seg[id].len=seg[id<<1].len + query(id<<1|1,seg[id].mmax,seg[id].flag);//顺势更新 
}
void change(int id) {
	if(seg[id].l==seg[id].r) {
		seg[id].mmax=qval;
		return ;
	}
	push_down(id);
	if(ql <= seg[id<<1].r)change(id<<1);
	else change(id<<1|1);
	push_up(id);
}
void rev(int id) {
	if(ql<=seg[id].l &&seg[id].r <=qr) {  //!
		seg[id].flag^=1;
		seg[id].lazy^=1;
		return ;
	}
	push_down(id);
	if(ql <= seg[id<<1].r)rev(id<<1);
	if(seg[id<<1|1].l <= qr)rev(id<<1|1);
	push_up(id);
}
void build(int id,int l,int r) {
	seg[id].l=l,seg[id].r=r;
	if(l==r) {
		seg[id].mmax=a[l];
		seg[id].flag=b[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	push_up(id);
}
int get_ans(int id,int& now_max,int& flag) {
	if(ql<=seg[id].l && seg[id].r<=qr) return query(id,now_max,flag);
	push_down(id);  //!
	int ret=0;
	if(ql <= seg[id<<1].r)ret+=get_ans(id<<1,now_max,flag);
	if(seg[id<<1|1].l <= qr)ret+=get_ans(id<<1|1,now_max,flag);
	return ret;
}
int main() {
	int mx,fl;
	int op,t1,t2;
	n=mread();
	for(int i=1; i<=n; i++)a[i]=mread();
	for(int	i=1; i<=n; i++)b[i]=mread();
	build(1,1,n);
	q=mread();
	while(q--) {
		op=mread(),t1=mread(),t2=mread();
		if(op==1) {
			ql=t1;
			qval=t2;
			change(1);
		} else if(op==2) {
			ql=t1,qr=t2;
			rev(1);
		} else if(op==3) {
			ql=t1,qr=t2;
			mx=-1,fl=0;//!
			printf("%d\n",get_ans(1,mx,fl));
		}
	}
	return 0;
}