原题地址https://www.spoj.pl/problems/GSS2/
思路：
听说这题很难，于是写此题自虐= =
看了题目，感觉像其他几题GSS直接用线段树维护不太可能。。。
又看了一遍题，发现只有Query没有Edit，想到了像Tarjan LCA之类的，先把所有的Query读进来，然后处理队列的同时处理Query。。。
于是大概想到了一个离线算法，先把Query按末端排序，然后一边加入节点一边通过某种方式处理Query。。。但这个“某种方式”只能大概想出是用线段树维护到当前节点的最大值，重复处理一直想不出，想不到怎么从线段树中选择重复的点。。。（这段话语法问题真多= =）
再然后，又没有思路了
后来膜拜了JZP神犇的blog，http://blog.163.com/oimaster@126/，惊讶的发现我前面的思路竟然是对的orz，然后看到一个巧妙的处理重复点的方法，就是记录该点上次出现的位置，然后“只对s[last[x]+1]到s[k]加上x”，orz。。。这样任意位置都可以保证只计算重复的点一次。
于是问题转化成了维护队列问题
维护一个队列，使其支持：
1.给一段数统一加上一个数
2.查询一段数中曾经的最大值
这两个操作都应该在lgn时间内完成
明显要打标记。。。
下面是我的线段树维护的域及其处理：
nowtag:掌管的段中当前最大值
maxtag:掌管的段中曾经的最大值
tag:即将下传的加入的数的和
mtag:设tag中加入的数依次为a[1],a[2],…a[tot]，则mtag=max{a[1]+a[2]+…+a[i]) 1<=i<=tot
细节非常多
详细处理过程见程序