# [题解] ICPC2023 HongKong Sum of Numbers [线段树][扫描线]
也是好久没写博客了。最近学校各种事情太多了，基本每周都有事。
下周更是：CCSP 要来了，在此之前还有网综实验考试。。
好在网综实验貌似并不是太难，用了半个上午时间大概会了一半的分数了；老师也还算和善。
希望不出什么岔子。
# 题目大意
给定一个长度为 的颜色数组, 对于一个区间, 称其是不好的当且仅当区间内存在一个颜色 且这个颜色恰好出现了 次。问数组中一共有多少个好的区间。
# 题解
对于每一个颜色 c，将其出现位置抽离出来。记 pos [c][i] 表示第 i 个 c 出现的位置。
考虑每一个恰好包含 k 个颜色 c 的区间，左端点为 pos [c][li], 右端点为 pos [c][ri]，那么对于所有，区间 [l,r] 都是不好的。这一步对每个颜色的位置扫一遍即可。
于是问题转化成了：在二维坐标系上，有一些矩形，求这些矩形的并集大小。最终答案就是所有区间数量减去不好的区间的数量（矩形的并）。经典的扫描线题目。
题目挺板子的，没啥好说的，这里就是记录一下这题卡了太久的离奇原因。
只能怪是有些时日没写过扫描线了，具体的细节甚至今天查书才写得了的。
比较关键的一点是这样的：线段树上的每一个节点，记录 cnt 表示整个区间被覆盖的计数（自上而下，不从儿子合并），len 表示覆盖总长度。当 cnt 不为 0 时，len=r-l+1, 否则 len 自下合并。
然后这里的逻辑没处理好。。
这样就 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; | |
} |
