数据结构做题笔记

牛客NOIP模拟第一场T3

Description

给一棵树,给定m条树上的路径.
每次询问x,k.
表示从x到根节点的路径上的某个点y,x到y的路径必须被至少k条路径完全覆盖.
求深度最浅的y.

\(n,m,q\leq 200000\)

Solution

主席树

可以发现对于y有一种单调性,每次二分一个深度,然后就化成了一个判定性问题.
已知一条关于(x,y)的路径,求给定的路径有几条包含它.
设x属于以s为根的y的子树中.
那么就要数一端落在(Lt[x],Rt[x]),一端落在(1,Lt[s]-1)U(Rt[s]+1,n)的路径有几条.
这是一个经典的二维数点问题.
用主席树差分一下,复杂度logn.
加上外面的二分,复杂度\(O(nlog^2{n})\).

线段树合并

树上路径还有很多性质,比如可拆分性,就是说把一条路径根据LCA剖成两半.
发现一条不弯折路径要包含一个点(x),一端要在x的子树内,一端要在x到根节点的路径上.
那么对于询问,只用查询子树上所有点,连到自己上方点的路径情况,做一个类似于区间第K值的线段树内二分即可.
子树信息可以用线段树合并完成.
复杂度\(O(nlogn)\)

YCJS 3916 三角形

Desciption

给定一个序列,有两种操作.
op1:改变某个点的权值
op2:询问[l,r]的点集中选取三个点,要求它们的大小关系满足三角形三边关系,同时要求总长尽量大.
\(Ai\leq 1e9,n\leq 1e5\)

Solution

有限关系+归并树

首先,如果序列有序,那么就只用把点排序,然后扫描一遍相邻三个是否合法即可.
使每一层序列有序,可以利用归并树解决
但是每一层归并树的节点数量太多了,需要进行优化.
考虑记录最大的几个点.
如果\(a_i>=a_{i-1}+a_{i-2}\),那么\(a_i\)不会有效.
但发现这样的不等式满足斐波那契数列,所以最多连续出现\(logV\)次,那么只用记录\(logV+2\)的最大的点就一定存在答案.
所以总复杂度\(O(nlogn*45)\)

hihoCoder 1046 K个串

Description

给一个序列,求连续子串和第K大的值(重复出现的数字只被统计一次)。

\(1 \le n \le 100000, 1 \le k \le 200000, 0 \le |a_i| \leq 10^9\)

Solution

可持久化线段树+堆

这道题的突破口是K的取值范围,K小时暴力的枚举最大值是可行的。
做这道题是应有如下结论：
- 线段树可以查询除最大外的第二大值(把最大值删除,然后up)。
- 线段树的区间修改的复杂度是\(logn\),所以如果动态开点也只会添\(logn\)个。
很容易想到，要枚举左端点，然后可以知道左端点为i和i-1对应序列的对应关系，那么可以在前一棵线段树的基础上建树。
把每棵树的最大值丢进优先队列中，每弹出一个值，删掉对应树中的最大值，丢进次大值，一直到第k个值。

YCJS 3925 瘟疫

Description

MUPA生活的国家拥有N个城市,每两座城市之间有且仅有一条路径可以到达,并且1城市是这个国家的首都,可以认为是根节点为1的有根树.原本这个国家的人都安安稳稳的生活.

但是有一天,有一位阴谋者ihcamoK在这个国家散布fAKo瘟疫,想让这个国家全部陷入AKo之中.

每一次,ihcamoK会选择一个城市,在该城市散布病毒,但是如果该城市已经被感染了瘟疫,那么这个瘟疫会往下传播,直到找到没有被感染的为止.当然,如果该城市没有被感染病毒,那么这一次散播病毒只会感染该城市

\(n,q\leq 10^5\)

当a=1时,ihcamoK对于b城市散播了病毒

当a=2时,20XZH02对于b城市和以他为根的子树城市施展了净化术

当a=3时,MUPA询问b城市是否在感染之中

Solution

树剖线段树维护最大前缀和

首先如果没有清空操作，考虑如何判断某个点是否被感染。
首先只有自己的祖先对自己会造成影响。
然后看从自己到某个祖先的整个路径上有几个点被更新过，如果更新次数c>=dis(自己到该祖先的路径)，那么该点已被感染。
那么一种比较简便的方法是把每个点的初始值赋为-1，然后对于一次更新操作就把该点的权值+1。
查询只用看从自己到根的路径的最大前缀和是否\(\ge 0\) 。
然后有清空操作后，就要把整个子树自己的标记给去掉。这个只用区间更新即可。
但有要去除到根路径标记对自己的影响，所以求一遍最大前缀和然后更新子树树根的权值就可以消除影响。

POI2014 Solar lamps (三维偏序)

Description

有n个四元组(\(x,y,t,k\))，一个四元组开始有效当且仅当时间到达\(t\)或者超过k个四元组满足\(x_1\le x,y_1\le y\)

问所有的四元组何时有效。 \(n\leq 2*10^5\)

Solution

整体二分+BIT

利用整体二分维护时间，排序x，BIT维护y。
整体二分当前时间为mid，那么一个四元组有效只有两种情况：1.\(t\le mid\) 2.超过k个四元组有效.
由于x已经有序，所以后面的一定不会影响前面的，即如果判定当前四元组无效，就不会在后面的更新中在考虑该四元组。
每次只用在BIT中查找\(y_1\le y\)的四元组个数即可。
剩下的是整体二分的常规套路。

void Solve(int l,int r,int L,int R){
	if(L==R){FOR(i,l,r)Ans[Q[i].id]=L;return;}
	int mid=(L+R)>>1;	
	
	int c1=l-1,c2=r;
	FOR(i,l,r){
		if(query(Q[i].y)>=Q[i].k||Q[i].id<=mid){
			Q1[++c1]=Q[i];
			add(Q[i].y,1);
		}else {
			Q[i].k-=query(Q[i].y);
			Q2[c2--]=Q[i];
		}
	}
	
	FOR(i,l,c1)Q[i]=Q1[i];
	FOR(i,c2+1,r)Q[i]=Q2[c2+1+(r-i)];
	
	FOR(i,l,c1)add(Q[i].y,-1);
	Solve(l,c1,L,mid);
	Solve(c2+1,r,mid+1,R);
}

YCJS3927 相同的题目

Description

一个长度为n的序列，有m中不同的权值，有q个询问，每次询问\([l,r]\)，要求求出相同权值元素位置差的绝对值最大是多少？

\(n,m,q\le 2*10^5\)

Solution

分块

设每个块的大小为\(S\)
利用分块预处理出块与块之间的答案，复杂度为\(O(\frac {n^2}{S})\)
然后对于每个询问，剩下的点暴力二分查找距离自己的最远的和自己颜色相同的点，复杂度为\(O(qSlogn)\)
所以总复杂度为\(O(\frac {n^2}{S}+qSlogn)\)
然后当\(S=\sqrt{nlogn}\) 时，复杂度最小，为\(O(n\sqrt{nlogn})\)