• 心中真正有光明的人，即使仰望茫茫宇宙，意识到自己生活的一切痕迹都将被抹去，不解自己为何被离弃，也会安然坦然地走下去。
• 我极喜欢张晓风的那句“我在”：

	《旧约·创世纪》里，堕落后的亚当在凉风乍至的伊甸园把自己藏匿起来。上帝说：“亚当，你在哪里？”
	他噤而不答。
	如果是我，我会走出，说：“上帝，我在，我在这里，请你看着我，我在这里。不比一个凡人好，也不比一个凡人坏，我有我的逊顺祥和，也有我的叛逆凶戾，我在我无限的求真求美的梦里，也在我脆弱不堪一击的人性里。上帝啊，俯察我，我在这里。”

• 同样，尽管退役，我依然在这里。

题意

• 题目链接。
• 长为 $n$ 的数列 $a_i$，与一个恒定的数列 $c_i$，支持区间加操作，但是每次操作之后，所有 $a_i$ 与 $0$ 取较大值，与 $c_i$ 取较小值，要求在所有操作之后输出 $a_i$。

分析

• “在所有操作之后输出结果”是经典的离线问题，有这句话几乎意味着在线不可做，与这个类似的还有rprmq，这篇例题 3等一系列神秘题目。
• 把时间维度与数列下标维度交换（如果您不了解这个技巧，可以参照上面的第二道例题）（具体而言：我们打算对于每个元素 $a_i$，用数据结构维护对应的操作序列，那么只需要 $O(q)$ 次增加或删除“修改操作”的操作），我们得到了一个问题：给定（对于一个单独元素的）操作序列，求最后的结果。
• 由于原来的问题不太好思考，可以尝试去掉上界思考：
• 因此，如果去掉上界，我们只需要在线段树上二分找到最小的前缀和，如果大于等于零，对 $0$ 取 $\max$ 没有发生，否则操作序列的后缀和就是答案。
• 接下来，考虑上界 $c_i$：
• 如果找到左端点最右的一段区间满足这个条件，那么它一定是成功对 $0$ 取 $\max$ 和对 $c_i$ 取 $\min$ 两者交替（或者在它的后面一段），而在这之后的的区间只会出现其中一种情况，这种情况只需要再次取操作序列的极值即可。

代码实现

• 利用区间前缀最大值，前缀最小值和区间和这三个变量可以表示一切（注意两者相减就是绝对值最大子段和）。
• 我们需要找到最右的，绝对值大于 $c$ 的区间的左端点，在线段树上，二分的同时维护后缀信息，容易在 $O(\log q)$ 的时间内查询得到结果。
• 找到最右的左端点之后，可以利用该点的正负说明这个操作是上面四种情况的哪一种（触底后碰顶，碰顶后触底，触底后半段，碰顶后半段），然后找到极值点，再判断要不要清 $0$，最终的代码是简短的：

#include<bits/stdc++.h>
#include"candies.h"
using ll=long long;
const int N=22e4;
using namespace std;
using van=vector<int>; 
int n,q;
struct ask
{
	int x,y;
};
struct node
{
	ll pmx,pmn,sm;
	node(ll a,ll b,ll c)
	{
		pmx=a,pmn=b,sm=c;
	}
	node(ll x=0)
	{
		*this=node(max(0ll,x),min(0ll,x),x);
	}
	node operator + (const node &b) const
	{
		return node(max(pmx,sm+b.pmx),min(pmn,sm+b.pmn),sm+b.sm);
	}
}g[N<<2];
vector<ask>f[N];
void add(int u,int l,int r,int x,int y)
{
	if(l==r)g[u]=node(g[u].sm+y);
	else
	{
		int mid=(l+r)>>1;
		x<=mid?add(u<<1,l,mid,x,y):add(u<<1|1,mid+1,r,x,y);
		g[u]=g[u<<1]+g[u<<1|1];
	}
}
ll qry(int u,int l,int r,int c,node ri)
{
	if(l==r)
		if(g[u].sm<=0)
			if(ri.pmx>c)return c+ri.sm-ri.pmx;
			else return ri.sm-ri.pmn;
		else
			if(ri.pmn<-c)return ri.sm-ri.pmn;
			else return c+ri.sm-ri.pmx;
	else
	{
		int mid=(l+r)>>1;
		node nw=g[u<<1|1]+ri;
		return nw.pmx-nw.pmn<=c?qry(u<<1,l,mid,c,nw):qry(u<<1|1,mid+1,r,c,ri);
	}
}
van distribute_candies(van c,van l,van r,van v)
{
	n=c.size(),q=l.size();
	van res(n);
	for(int i=0;i<q;++i)
		f[l[i]].push_back({i+1,v[i]}),
		f[r[i]+1].push_back({i+1,-v[i]});
	for(int i=0;i<n;res[i]=qry(1,0,q,c[i],0),++i)
		for(auto z:f[i])
			add(1,0,q,z.x,z.y);
	return res;
}