扫描线题集

板子  P5490 【模板】扫描线

简单的扫描线大概就是在一个二维平面上对整点的一种降维处理

一维暴力枚举,另一位用线段树维护,就可以在nlogn的时间里处理一些原来要n^2解决的问题

比如说板子里处理的是面积

T227327 不要相邻 – 洛谷 (对构造扫描线的建模)

题意 一棵树上求没有相邻编号节点的路径的个数(n<=3e5)

例如 1-4-2为有相邻编号的路径,1-7-3-13则不是

sol:可以发现,要判断相邻编号节点的路径是一件比较容易的事情

于是正难则反,统计相邻编号节点的路径个数cnt。

对于两个相邻编号的节点u,v,如果他们没有父子关系则cnt+=siz[u]*siz[v]

如果有父子关系则让v上跳到u的直接儿子w,cnt+=siz[v]*(siz[u]-siz[w])

很明显还是会有重复的,但是对于一棵子树内的所有结点,其深搜序具有连续性,故把他们丢到二维平面上,然后计算[没有被覆盖到的面积大小]即为答案。

trick:区间相斥 → 扫描线

CF526F Pudding Monsters (对扫描线维护信息的建模)

题意 n^2平面上有n个布丁(保证横纵坐标互不相同),求有多少个k^k的区域内有k的布丁(n<=3e5)

sol:建立一个横着的扫描线维护每一个后缀,从左往右扫,每次扫到p时处理k^k的右边界在p的答案数

发现当且仅当后缀max-min=len+1时对答案有贡献

用线段树维护即可。

CF1151E Number of Components

题意 在一个带点权链上规定f(l,r)为权值在[l,r]区间的联通块数量,求所有f(l,r)之和(n<=1e5)

sol :枚举每一个权值前缀

发现当前缀+1(1~l→1~l+1)时

该前缀的后缀和变化为

+权值仅为l+1的联通块数量

-权值为l+1的联通块向小点权连的边影响导致减少的联通块数量

结束。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n=read();
rep(i,1,n) {
   a[i]=read();
   if(a[i]!=a[i-1]) {
        b[a[i]]++;
        if(a[i]>a[i-1]) c[a[i]]+=a[i-1];
        else c[a[i-1]]+=a[i];
    }
}
int tot=0;
rep(i,1,n){
    tot+=b[i]*i-c[i];
    ans+=tot;
}
printf("%lld\n",ans);