20191031总结

其实今天本来想写点图论的，结果写成杂题练习了Orz。

• [] woj1060 贪婪大陆 对于每一条线段，我们维护它的两个段点，就是+1与-1标记，然后树状2个数组直接统计答案就好了。套路：对于线段，我们可以把它转化成2个端点，同样的，矩形也可以转化成2个线段
• [] CH2601 电路维修 毒瘤搜索建图
• [] woj1717 郁闷的小J 分块暴力版没想到暴力分块直接草过去了，其实这道题需要离线，针对每种颜色用树状数组统计，考虑贡献，日后千万写一下
• [] woj3843 Intervals 差分约束 前缀和定义的差分约束，了解一下
• [] woj3936 路径的交 千万记到一个结论，两条链相交，那么其中一条链一定过另一条链的最浅的点，然后树状数组维护差分标记就好了，但是注意一点：代码里面维护链的时候本来是lca-1 fa[lca]-1的，但是lca会被重复统计，所以为了方便，直接lca上-2，效果一样
• [] woj4674 金牌选手 D1T1.5 小容斥+枚举。枚举每个o统计总贡献，维护就用n o i出现次数的前后缀解决，对于某区间，就是后面的oi和前面的n与前面的no与后面的i的贡献扣去，然后前面的n后面的i的贡献加上，容斥完了。