[bzoj 1809][IOI2005] mou

Description

游乐园已经开始运行一个崭新的模拟过山车。模拟的轨道由n 段铁轨组成,并且首尾相连。第一段铁轨从高度0开始。操作员Byteman能通过调整连续几段的铁轨高度来改造这条轨道。在被改造的一段前面的铁轨高度不受影响。 每一次铁轨被调整。后面的轨必须升起或降低来保持连通,并保证起点高度为0。下页举例说明轨道改造过程。 每次开始时车都有足够能量到达高度h。也就是说,只要轨道的高度不超过 h车就一直开下去, 甚至直到结束。 给出每天的运行和改造情况, 为每次运行计算在车停止前,到达的铁轨数。铁轨以一个n个数的数列形式表示 ,一个数对应一段铁轨。第i个di表示在第i段铁轨上的高度变化。也就是说,在到达铁轨i前,如果车的高度是h,那么经过铁轨i后,高度变为h+di。最初轨道是一条水平线。就是说对于所有的i都是di=0。运行和改造交错进行。 每个改造用三个数表示: a , b 和 D。表示从a到b(包括a,b)的所有di改为di=D。每次运行给定一个数字h ——车能到达的最大高度。

Input

输入的第一行包括一个正整数n——铁轨的数目,1≤n≤1000000000。下面的行包括改造和运行,各有一个标识符: *改造——一个字母I,和整数a,b,D(1≤a≤b≤n,-1000000000≤D≤1000000000),中间用一个空格隔开。 *运行——一个字母Q,和一个整数h(0≤h≤1000000000),用一个空格隔开。 *一个字母E——结束符号,表示输入结束。 你可以假设任意时刻任意铁轨的高度在[1,1000000000]区间内。输入不超过10000行。 50%的数据n满足1≤n≤20000且输入不超过1000行。

Output

第i行需包含一个整数, 即第i次运行经过的铁轨数。

Sample Input

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E

Sample Output

4
1
0
3

Solution

题库里刚好有一道题名字重合了,导致一直交的是那题的代码,调了好久没发现,囧

采用动态开点的线段树,每个区间维护五个信息

左儿子,右儿子,右端点到左端点的距离,最高点到左端点的距离,这个线段的权值

count(L,R,X)表示[L,R]中第一个前缀和超过X的位置的前一个

那么显然如果当前的X>t[ls].max,则可以到达右孩子,否则留在左孩子。

发表评论