# [题解] ICPC2023 HongKong Sum of Numbers [线段树][扫描线]

也是好久没写博客了。最近学校各种事情太多了,基本每周都有事。
下周更是:CCSP 要来了,在此之前还有网综实验考试。。
好在网综实验貌似并不是太难,用了半个上午时间大概会了一半的分数了;老师也还算和善。
希望不出什么岔子。

# 题目大意

给定一个长度为nn 的颜色数组aa, 对于一个区间[l,r][l,r], 称其是不好的当且仅当区间内存在一个颜色cc 且这个颜色恰好出现了kk 次。问数组中一共有多少个好的区间。

# 题解

对于每一个颜色 c,将其出现位置抽离出来。记 pos [c][i] 表示第 i 个 c 出现的位置。
考虑每一个恰好包含 k 个颜色 c 的区间,左端点为 pos [c][li], 右端点为 pos [c][ri],那么对于所有l[pos[c][li1]+1,pos[c][li]],r[pos[c][ri],pos[c][ri+1]1]l\in[pos[c][li-1]+1,pos[c][li]],r\in[pos[c][ri],pos[c][ri+1]-1],区间 [l,r] 都是不好的。这一步对每个颜色的位置扫一遍即可。
于是问题转化成了:在二维坐标系上,有一些矩形,求这些矩形的并集大小。最终答案就是所有区间数量减去不好的区间的数量(矩形的并)。经典的扫描线题目。

题目挺板子的,没啥好说的,这里就是记录一下这题卡了太久的离奇原因。
Alt text
只能怪是有些时日没写过扫描线了,具体的细节甚至今天查书才写得了的。
比较关键的一点是这样的:线段树上的每一个节点,记录 cnt 表示整个区间被覆盖的计数(自上而下,不从儿子合并),len 表示覆盖总长度。当 cnt 不为 0 时,len=r-l+1, 否则 len 自下合并。
Alt text
然后这里的逻辑没处理好。。
Alt text
这样就 ok
吭哧吭哧近一小时,一开始以为线段树数组开错了。

# 代码

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
int read(){
	int out(0),c(getchar());
	for(;c<'0' || c>'9';c=getchar());
	for(;c<='9' && c>='0';c=getchar())
		out=(out<<3)+(out<<1)+(c^48);
	return out;
}
const int MAXN=1e6+10;
int N,K;
int a[MAXN];
std::vector<int> pos[MAXN];
std::set<int> cs;
struct Op{
	int y,typ;
	int xl,xr;
	bool operator < (const Op &rv)const{
		return y==rv.y ? typ>rv.typ : y<rv.y;
	}
}op[MAXN<<2];
int opn;
struct Tr{
	int len,cnt;
}tr[MAXN<<2];
void mdf(int p,int l,int r,int v){
	tr[p].cnt+=v;
	if(tr[p].cnt)
		tr[p].len=r-l+1;
	else
		tr[p].len=(l==r?0:tr[p<<1].len+tr[p<<1|1].len);
}
void up(int p,int l,int r){
	if(tr[p].cnt)
		tr[p].len=r-l+1;
	else
		tr[p].len=(l==r?0:tr[p<<1].len+tr[p<<1|1].len);
}
void mdf(int p,int l,int r,int ll,int rr,int v){
	if(ll<=l && r<=rr)
		return mdf(p,l,r,v);
	int m=l+r>>1;
	if(ll<=m)
		mdf(p<<1  ,l  ,m,ll,rr,v);
	if(rr>m)
		mdf(p<<1|1,m+1,r,ll,rr,v);
	up(p,l,r);
}
signed main(){
	N=read(),K=read();
	for(int i=1;i<=N;++i){
		a[i]=read();
		if(cs.find(a[i])==cs.end())
			pos[a[i]].push_back(0);
		cs.insert(a[i]);
		pos[a[i]].push_back(i);
	}
	for(int c:cs){
		pos[c].push_back(N+1);
		for(int li=1,ri=li+K-1;ri<(int)pos[c].size()-1;++li,++ri){
			int xl=pos[c][li-1]+1,xr=pos[c][li];
			int yl=pos[c][ri],yr=pos[c][ri+1]-1;
			// printf("(%d %d) (%d %d)\n",xl,xr,yl,yr);
			op[++opn]={yl  ,+1,xl,xr};
			op[++opn]={yr+1,-1,xl,xr};
		}
	}
	std::sort(op+1,op+1+opn);
	int las=0;
	long long ans=1ll*N*(N+1)/2;
	for(int i=1;i<=opn;++i){
		ans-=1ll*tr[1].len*(op[i].y-las);
		las=op[i].y;
		int l=op[i].xl,r=op[i].xr;
		mdf(1,1,N,l,r,op[i].typ);
	}
	printf("%lld\n",ans);
	return 0;
}
更新于 阅读次数