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]);
	}
}