开四个set，分别存切割的刀以及每个区间段，然后每次各自从行和列取最长的区间段，乘一起即可。
lp1438 无聊的数列
区间加上一个等差数列这件事情其实并不好维护。但既然是单点查询，那就可以考虑差分。我们考虑将数列差分，维护一个差 …
lp3313 SDOI2014 旅行
虽然这一题被划在主席树下面，但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。 树链剖分后我们考虑对每一 …
lp3168 CQOI2015 任务查询系统
观察题面，我们发现这是一道变态题：区间加点，单点查询第k大，强制在线——这tm不是变态题么！别的不说，权值怎么 …
lp3302 SDOI2013 森林
我们发现，树上的链上第k大是可以使用主席树来维护的。对于每一个节点，我们从它的父亲复制一个版本，然后每一次求出 …
lp2146 NOI2015 软件包管理器
简化题意： 存在一棵树，其上所有点的初始值为0。 存在两种操作，分别是，将一个点的所有父亲节点改为1，或者将一 …
lp2486 SDOI2011 染色
考虑这一题在链上的情况。 显然，可以建一棵线段树，修改是打标记下传，查询是左右相加特判左右相邻处颜色是否相同。 …
lp2590 ZJOI2008 树的统计
树剖套线段树裸题。
lp3676 小清新数据结构题
仔细考虑这道题，我们可以将问题转化为「修改」和「换根」两个操作。 对于修改操作，我们知道，每个点的权值对且仅对 …
CF487E Tourists
众所周知，圆方树是用来处理图上点双相关问题的。 同时，点双又是一个和简单路径密切相关的东西。故而这一题我们可以 …
lp2468 SDOI2010 粟粟的书架
简化题意。 有一个n*m的矩阵，q个询问，求问，在每个矩阵中最少取多少个数，使得和至少为h。 观察数据范围，我 …
lp1110 ZJOI2007 报表统计
事实上对于第一类询问和第二类询问我们可以分别处理。 第二类询问的处理方法是非常显然的。由于只有插入而没有删除操 …
lp1486 NOI2004 郁闷的出纳员
（似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话，是可以跑得飞快的。） 首先看一 …
lp2572 SCOI2010 序列操作
操作要求： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 …
lp1471 方差
大力上一个线段树。 将方差展开为由区间平方的和与区间和两项构成的多项式，然后维护区间平方的和与区间和。 具体来 …