在毒瘤的bzoj上似乎是道权限题。。。但是这不影响我们用一些奇奇怪怪的途径找到这道题
【题目描述】
DCrusher有一个数列,初始值均为$0$,他进行$N$次操作,每次将数列$[a,b)$这个区间中所有比$k$小的数改为$k$,他想知道$N$次操作后数列中所有元素的和。他还要玩其他游戏,所以这个问题留给你解决。
【输入格式】
第一行一个整数$N$,然后有$N$行,每行三个正整数$a,b,k$。
$N\leq 40000 , a,b,k\leq 10^9$
【输出格式】
一个数,数列中所有元素的和。
题解
我们把所有修改操作按照$k$从大到小排序 那么每次修改操作实际上就变成了 把$[a,b)$区间内所有的$0$(即之前没有修改过的元素)改成$k$因为之前就修改过的元素肯定是大于$k$的
那用线段树每次查询$[a,b)$有多少个$0$记为$cnt$实际上$cnt$就等于 区间长度减去区间内有多少个非$0$元素 由于询问按$k$从大到小排序 所以现在区间内的$0$在$N$次操作结束后肯定都会是$k$所以$ans$加上$cnt*k$
再把$[a,b)$中所有的$0$改成$k$注意 不用真的去改 因为我们实际上只关心每个区间内有多少个非$0$元素 所以我们只需要查询完后把整个区间都填成$1$就可以了 询问也就变成了区间内有多少个$1$
所以现在我们需要支持两个操作
- 查询区间内有多少个$1$
- 把整个区间修改成$1$
就正常打标记 都很好实现吧
$a,b\le 10^9$怎么办?动态开点
ps.我一般都是单点修改的时候用到动态开点 这种区间修改打标记能不能动态开点呢?
注意到修改一段区间$[l,r]$在线段树上可以通过修改不超过$\log n$个节点实现 每个节点的深度又最多是$\log n$所以极限情况下每次修改新创建的节点数也不会超过$\log^2 n$个 这题是$\log^2 10^9 \approx 1000$但是这个上限根本达不到 更别说修改区间还会有交集 所以不用担心内存不够
缺点是常数略大。。。应该有更简单的方法 但是这个方法好就好在它十分的模板
注意一下修改的区间是$[a,b)$。。。左闭右开
代码
1 |
|