[作业题] #6 CF571D

我这进度也太慢了吧，果然我整个人就是一个水。

Campus

题目描述

点此看题

解法

我自己想到正解的题都是水题，这题也不例外。

考虑在并查集上修改的主要方法就是在根上打标记，那么本题我们就打标记，并且为了复杂度我们不下放，而是在询问的时候暴力跳父亲来计算标记的影响，前提是启发式合并保证深度是 \(O(\log n)\) 级别。

考虑清除操作（就是整个并查集赋 \(0\)）的影响可以通过计算每个点最后一次被清除的时间得到，那么我们在每个节点上维护一个清除标记，在清楚时间 \(\geq\) 合并时间的条件下父亲的清除就可以作用于儿子，那么我们可以在线算出清除时间。

对于加法操作我们维护一个以时间为顺序的 \(\tt vector\)，那么知道了清除时间之后就可以在上面二分，有贡献的加法标记一定是一段后缀（注意还要把合并时间也考虑进去），时间复杂度 \(O(n\log^2n)\)

总结

数据结构题，不一定要把东西全部维护出来询问直接去拿，询问操作可以承担起在线计算的作用。

观察操作的特性，比如本题清除操作的特性就是爹，清除之后什么都没有了，所以我们只需要知道最后一次清除的时间。

#include 
#include 
#include 
using namespace std;
const int M = 500005;
#define pii pair
#define x first
#define y second
#define ll long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
void write(ll x)
{
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int n,m,k,fa[2][M],t[2][M],sz[2][M],z[M];
vector d[M];vector s[M];
int find(int x,int o)
{
	return (x!=fa[o][x])?find(fa[o][x],o):x;
}
void merge(int u,int v,int o)
{
	u=find(u,o);v=find(v,o);
	if(u==v) return ;
	if(sz[o][u]