南外DAY9

（我也曾在比赛的某一时刻排在第4）

总结：

A，B，D 水题，比赛时30分钟
C题一个看起来比较大的模拟，其实没什么，栈都不用（赛时没打啊啊啊啊！）

E题，一个枚举子矩阵数量的新思路（赛时80，已过）

正常情况下是枚举两个角（n^4)，但也可以枚举上，下，右区间，o(1)判断有多少种符合题意的矩阵数

F题，树上差分（赛时80，已过）

用DFS遍历整颗数，当一个点遍历到时有且只有它的所有长辈节点被遍历到，所以遍历到一个点时修改差分数组，回溯时删除，跑前缀和就行

G题，贪心加线段树（40）

贪心易得优惠要给优惠力度最大的用，所以先排序，枚举前m个用优惠券，后面不用；前半部分总和很好求，后半部分用线段树维护

H题，不会！！！！！