JZOJ5936. 【NOIP2018模拟10.29】逛公园

题意：

数据范围：

Analysis：

吼题啊。
这种题会有性质的，我们要根据性质去计算答案。
我们设$f(l,r,x)$f(l,r,x)表示以$x$x为初始值走完$l$l~$r$r最后的结果，贪心的想，在某个位置尽量大，结果越大，所以有：若$a &lt; b$a<b，则有$f(l,r,a)&lt;=f(l,r,b)$f(l,r,a)<=f(l,r,b)。
考虑一个区间以$x_0$x0​为初始值的答案怎么计算。
发现对于一个$x_0$x0​，它在第一次被上限卡满之后就是一般情况了，我们基于这个来分析一波性质。
若$x_0$x0​在某个位置被卡满，答案显然是$f(l,r,L_l)$f(l,r,Ll​)。为方便表示设：$G(l,r)=f(l,r,L_l)$G(l,r)=f(l,r,Ll​)。
若没被卡满，答案是$S(l,r)+x_0,S(l,r)$S(l,r)+x0​,S(l,r)表示$l$l~$r$r所有$D$D值之和。
发现一个区间的答案就是两者取$min$min。
那么考虑什么情况下一个区间不优：
对于两个区间$[l,r],[l1,r1]$[l,r],[l1,r1]。若$[l,r]$[l,r]的$G,S$G,S都大于$[l1,r1]$[l1,r1]的$G,S$G,S。那么$[l1,r1]$[l1,r1]就没用了。
若将有用的区间按$G$G从大到小排序，发现$G$G递减，$S$S递增，若以初值$x_0$x0​计算答案，不难发现最优值会是$G,S+x_0$G,S+x0​最接近的位置，又由于之前的单调性，故可以二分。
这样就可以快速计算一个区间的答案了。
这么做启发我们分块预处理。
我们处理出每一个块所有有用的区间，总数是$O(n\sqrt{n})$O(nn​)的。
那么一个块内的答案就可以二分了，散块的话，我们发现一个位置贪心的要取大，我们可以从$l$l开始取，若一个位置的值小于$x_0$x0​，那么将它变为$x_0$x0​即可。
考虑跨越块的怎么处理。肯定是一个前面后缀和当前前缀的拼接。
考虑后缀的答案为$y$y，那么也就是对当前块要求最大的前缀$f(l,r,y)$f(l,r,y)，这也可以二分了。
因为第一条性质，我们只需要最大的$y$y。那么对于所有块预处理出它的所有有用前缀后缀，散块暴力处理。
最大的$y$y怎么算，分类讨论：
1.由之前的$y$y跨过当前整块。
2.当前块的某个后缀(可以二分)。
3.$x_0$x0​
三者取$max$max即可，至此本题解决，复杂度$O((q+n)\sqrt{n}\log{n})$O((q+n)n​logn)。

Code：

# include<cstdio>
# include<cstring>
# include<algorithm>
# include<cmath>
using namespace std;
const int N = 4e4 + 5;
const int M = 2e2 + 5;
struct node
{
	int g,s;
}q[M][N],pre[M][M],suf[M][M],c[M],sta[N];
int d[N],lim[N],s[N],t[M][3];
int L[M],R[M],pos[N],ps[M][N],su[M][N];
int n,Q;
inline int read()
{
	int x = 0; char ch = getchar();
	for (; ch < '0' || ch > '9' ; ch = getchar());
	for (; ch >= '0' && ch <= '9' ; ch = getchar()) x = x * 10 + ch - '0';
	return x;
}
bool cmp(node a,node b) { return a.g < b.g; }
inline int Br(int l,int r,int x)
{
	int now = x,ans = x;
	for (int i = l ; i <= r ; ++i)
	{
		now += d[i]; if (now > lim[i]) now = lim[i];
		now = max(now,x),ans = max(ans,now);
	} return ans;
}
inline int Cl(node *a,int Le)
{
	int top = 0; sort(a + 1,a + Le + 1,cmp);
	for (int i = 1 ; i <= Le ; ++i)
	{
		while (top && sta[top].s < a[i].s) --top;
		sta[++top] = a[i];
	}
	for (int i = top ; i ; --i) a[top - i + 1] = sta[i];
	return top;
}
inline int find(node *a,int Le,int x)
{
	int l = 1,r = Le,ret = Le + 1; a[Le + 1].g = 0;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (a[mid].s + x >= a[mid].g) r = mid - 1,ret = mid;
		else l = mid + 1;
	} return max(a[ret].g,a[ret - 1].s + x);
}
int main()
{
	freopen("park.in","r",stdin);
	freopen("park.out","w",stdout);
	n = read(),Q = read(); int len = sqrt(n),m = n / len + (n % len ? 1 : 0);
	for (int i = 1 ; i <= n ; ++i) d[i] = read(),s[i] = s[i - 1] + d[i];
	for (int i = 1 ; i <= n ; ++i) lim[i] = read(),pos[i] = (i - 1) / len + 1;
	for (int i = 1 ; i <= m ; ++i) L[i] = R[i - 1] + 1,R[i] = min(n,len * i);
	for (int i = 1 ; i <= m ; ++i)
	{
		for (int j = L[i] ; j <= R[i] ; ++j)
		{
			int now = lim[j];
			for (int k = j ; k <= R[i] ; ++k)
			{
				now += d[k]; if (now > lim[k]) now = lim[k];
				q[i][++t[i][0]] = (node){now,s[k] - s[j - 1]};
			}
		}
		t[i][0] = Cl(q[i],t[i][0]);
		for (int j = R[i] ; j >= L[i] ; --j)
		{
			int now = lim[j];
			for (int k = j + 1 ; k <= R[i] ; ++k)
			{ now += d[k]; if (now > lim[k]) now = lim[k]; }
			suf[i][++t[i][1]] = (node){now,s[R[i]] - s[j - 1]},su[i][j] = now;
		} t[i][1] = Cl(suf[i],t[i][1]); int now = lim[L[i]];
		for (int j = L[i] ; j <= R[i] ; ++j)
		{ now += d[j]; if (now > lim[j]) now = lim[j]; pre[i][++t[i][2]] = (node){now,s[j] - s[L[i] - 1]},ps[i][j] = now; }
		t[i][2] = Cl(pre[i],t[i][2]);
	}
	while (Q--)
	{
		int l = read(),r = read(),x = read(),ans = x,y = 0;
		if (pos[l] == pos[r]) ans = max(ans,Br(l,r,x));
		else
		{
			ans = max(ans,max(Br(l,R[pos[l]],x),Br(L[pos[r]],r,x)));
			for (int i = pos[l] + 1 ; i < pos[r] ; ++i) ans = max(ans,find(q[i],t[i][0],x));
			int top = 0;
			for (int i = l ; i <= R[pos[l]] ; ++i) c[++top] = (node){su[pos[l]][i],s[R[pos[l]]] - s[i - 1]};
			top = Cl(c,top); y = max(x,find(c,top,x));
			for (int i = pos[l] + 1 ; i < pos[r] ; ++i)
			{
				ans = max(ans,find(pre[i],t[i][2],y));
				y = max(x,max(min(ps[i][R[i]],s[R[i]] - s[L[i] - 1] + y),find(suf[i],t[i][1],x)));
			} top = 0;
			for (int i = L[pos[r]] ; i <= r ; ++i) c[++top] = (node){ps[pos[r]][i],s[i] - s[L[pos[r]] - 1]};
			top = Cl(c,top); ans = max(ans,find(c,top,y));
		} printf("%d\n",ans);
	}
	return 0;
}