CF1764H 题解

发表于
比较复杂的数据结构题

题意

给定长为 $n$ 的序列，初始 $a_i=i$。有 $m$ 个操作，操作为给出 $l_i,r_i$ 并将 $[a_{l_i},a_{r_i}]$ 赋值为 $a_{l_i}$。要求对每个 $[i,i+k-1]$，回答保留该区间内的操作后序列中不同元素的数量。

初步分析

不难发现，对答案产生贡献的有两种情况：

  • 没有被执行操作的元素

  • 某次操作左端点的元素

我们尝试分别统计这两种情况。

只考虑维护序列，我们容易想到一种基于均摊的，用 set 暴力维护的做法：在 set 中存下每一个区间，遇到修改操作就找到左右端点所在的 set 区间并将其分裂，暴力删去左右端点之间的区间，插入新区间。

我们想在上述过程中同时预处理我们需要的东西。

进一步分析

对于第一种情况：我们对 set 中的每个区间同时记录下一个 $time$，表示这个区间最初是第 $time$ 次修改操作插入进去的。假设当前是第 $i$ 次修改操作，将从 set 中删去 $[l,r]$ 这个区间，那么我们可以知道在 $[time+1,i-1]$ 这个时间段以内 $[l,r]$ 是没有被修改过的，可以作为第一种贡献。贡献的范围是所有 $ql>time\and qr<i$ 的询问操作。这是一个经典的二维数点问题，可以用扫描线+树状数组解决。

对于第二种情况：我们需要对每个操作维护 $3$ 个信息，分别是：$pre_i$，该操作之前最后一个覆盖到 $l_i$ 的操作；$go_i$，该操作的原始区间 $[l_i,r_i]$ 被完全覆盖掉的时刻；$ed_i$，该操作彻底不能产生贡献的时刻。如果维护好了这些信息，我们知道这个操作能对 $pre_i<ql\and qr<ed_i\and ql\le i\le qr$ 的询问产生贡献，这同样是一个二维数点问题。

具体的，$pre_i$ 只需要在 set 中插入该操作之前查询即可；$go_i$ 为所有 $time=i$ 的区间中被删去时刻的最大值；$ed_i=\max (go_i,ed_j[pre_j==i])$。

这样这道题就完全解决了。

代码实现

感觉只有必要放一下预处理，都来做这题了不至于不会二维数点吧：

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
struct bignod{
	int l,r,tim;
	bool operator<(bignod b)const{
		return l<b.l;
	}
};
struct gonxian{
	int x,y,v;
}gx[2000015];
void init(){
	set<bignod> st;
	set<bignod> ::iterator it,ti,it2;
	st.insert(bignod{1,n,0});
	for(int i=1;i<=m;i++){
		int l=xg[i].l,r=xg[i].r;
		it=st.upper_bound(bignod{l,0,0}),ti=--st.upper_bound(bignod{r,0,0});
		it2=it,it2--;
		bignod u=*it2,v=u;
		pre[i]=u.tim;
		if(u.r>=xg[i].r){
			go[u.tim]=max(go[u.tim],i);
			st.erase(it2);
			if(u.l<l)st.insert(bignod{u.l,l-1,u.tim});
			if(u.r>r)st.insert(bignod{r+1,u.r,u.tim});
			st.insert(bignod{l,r,i});
			if(u.tim+1<=i-1)gx[++cqt]=gonxian{u.tim+1,i-1,r-l+1};
			continue;
		}
		st.erase(it2);
		for(;it!=ti;){
			go[(*it).tim]=max(go[(*it).tim],i);
			if((*it).tim+1<=i-1)gx[++cqt]=gonxian{(*it).tim+1,i-1,(*it).r-(*it).l+1};
			it2=it++;
			st.erase(it2);
		}
		u=*ti,st.erase(ti);
		go[v.tim]=max(go[v.tim],i),go[u.tim]=max(go[u.tim],i);
		if(v.tim+1<=i-1)gx[++cqt]=gonxian{v.tim+1,i-1,v.r-l+1};
		if(u.tim+1<=i-1)gx[++cqt]=gonxian{u.tim+1,i-1,r-u.l+1};
		if(v.l<l)st.insert(bignod{v.l,l-1,v.tim});
		if(u.r>r)st.insert(bignod{r+1,u.r,u.tim});
		st.insert(bignod{l,r,i});
	}
	for(it=st.begin();it!=st.end();it++){
		bignod u=*it;
		if(u.tim+1<=m)gx[++cqt]=gonxian{u.tim+1,m,u.r-u.l+1};
		go[u.tim]=max(go[u.tim],m+1);
	}
	for(int i=m;i;i--){
		die[i]=max(die[i],go[i]);
		if(pre[i])die[pre[i]]=max(die[pre[i]],die[i]);
	}
}