平衡树 – Tgotp-Blog

1058: [ZJOI2007]报表统计

读题观察发现:

操作一只用一个平衡数维护单调区间即可。

且差值绝对值变化一定是变小,那么在插入的时候更新即可。

操作二只用一个线段树维护区间最小值即可.

观察发现在某个位置增加数以后更改的差值只与这个位置上一次操作的数有关,以及下一个位置的第一个数有关.

线段树维护即可[......]

Read more

1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

首先化成max(|(a.x+a.y - (b.x + b.y)|,|a.x-a.y - (b.x-b.y)|);

然后对于x维护一个滑动窗口,对于y用set维护即可

c++代码如下:

 

1691: [Usaco2007 Dec]挑剔的美食家

将每次满足条件价格最小的w放入对应的。

用set维护即可

c++代码如下:

 

BZOJ 1588: && Luogu P2234 [HNOI2002]营业额统计

 

P3369/BZOJ3224 【模板】普通平衡树(Treap/SBT)

平衡树模板