Honorable Mention[gym102331H]

发表于 2020-05-29 分类于 CF ， jzoj

题目链接

jzoj

题意

一个长度为 $n$ 的序列，$m$ 个询问，每次询问在 $[l,r]$ 内选出 $k$ 段互不相交的子段，使得子段和最大。

$n,m\leq 35000,k\leq r-l+1,|a_i|\leq 35000$。

题解

这跟之前某道题有点像啊。

$k$ 很小时，一个非常简单的做法是模拟费用流，每次在线段树中找出区间内的最大子段，然后加进答案里，再把这个子段的所有数变成其相反数。

这样的单次询问时间复杂度是 $O(k\log n)$ 的。

能在jzoj上获得大概 $28\sim 40$ 的分数。

这个做法无法再扩展下去了，我们考虑换另一种。

考虑DP，设 $f_i$ 表示在该区间中选 $i$ 段的最大值。

显然有 $f_{i+1}-f_i\leq f_i-f_{i-1}$，也就是说，$f_i$ 会形成一个上凸包的形式。

考虑如何将两个区间合并到一起。

设这两个区间为 $a,b$，假设先不考虑两个区间衔接的地方是否将选两次合成一次，那么就有：

$$f_{ab}(i)=\max_{j+k=i}{f_a(j)+f_b(k)}$$

又由于这个 $f$ 是一个上凸包的形式，这个式子相当于是对 $f_a$ 和 $f_b$ 两个凸包做了一次闵科夫斯基和。

那么就可以用归并的思路，将 $f_a,f_b$ 合并到一起。

考虑两个区间衔接的地方是否将选两次合成一次：对于每个区间，记录 $g_{0/1,0/1}$ 表示左右端点是否选择时的 $f$ 数组，当 $a$ 的右端点和 $b$ 的左端点均选择的时候，实际上就是将 $f_{ab}$ 向左移了一位。

那么就可以将这两个区间在线性时间内的答案合并到一起。

可以开一个线段树。预处理出线段树中区间的答案。

这一部分的时间复杂度是 $O(n\log n)$ 的，有个 $2^4$ 的常数。

然后考虑如何计算一个区间的答案。

显然这个区间可以表示成线段树中 $O(\log n)$ 的区间。

显然我们不能直接将这写区间合并到一起。

由于斜率是单调不增的，我们可以考虑使用wqs二分，二分答案对应的斜率，然后对于线段树中的每个区间，再来一次二分，找到斜率所对应的贡献即可。

时间复杂度是 $O(q\log^ n\log V)$ 的，还有至少是 $8$ 的常数。

这个显然过不了。

因为可以离线，我们使用整体二分也应是可以的。

但我们也可以一起二分，将这些询问的 $mid$ 值从大到小排序，然后对于每个那样的上凸包，都记录一个指针表示当前在哪里。对于每次外面的二分，这个指针只会向右移动。因此，每次外面的二分，所有的指针移动次数是 $O(n\log n)$ 级别的。

那么这样就不需要线段树里面的二分了。

时间复杂度 $O(n\log n+q\log v\log q+n\log n\log v)$，有个 $16$ 左右的常数。

二分范围搞错了，导致调了好久。。。

程序

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=35004;
ll sum;
const ll inf=N*N;
const ll INF=inf*N;
#define Vec vector<ll>
#define lc (x<<1)
#define rc (x<<1|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
Vec g[N<<2][2][2];
inline void get(Vec &A,Vec b,Vec c)
{
	int n=b.size()-1,m=c.size()-1,nl=0,ml=0,tot=1;
	A.resize(n+m+1);
	ll dec;
	dec=A[0]=b[0]+c[0];
	for(;nl<n&&ml<m;tot++)
		if(b[nl+1]-b[nl]>c[ml+1]-c[ml])
		{
			dec+=b[nl+1]-b[nl];
			nl++; A[tot]=dec;
		}
		else
		{
			dec+=c[ml+1]-c[ml];
			ml++; A[tot]=dec;
		}
	for(;nl<n;tot++,nl++) dec+=b[nl+1]-b[nl],A[tot]=dec;
	for(;ml<m;tot++,ml++) dec+=c[ml+1]-c[ml],A[tot]=dec;
}
inline void merge(Vec &A,Vec B,bool opt)
{
	ff(i,0,B.size())
	{
		A[i]=max(A[i],B[i]);
		if(opt&&i) A[i-1]=max(A[i-1],B[i]);
	}
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		int t;
		fo(i,0,1) fo(j,0,1)
		{
			g[x][i][j].resize(2);
			fo(k,0,1) g[x][i][j][k]=-inf;
		}
		g[x][0][0][0]=0; t=g[x][1][1][1]=read();
		sum+=abs(t);
		return;
	}
	int mid=l+r>>1;
	build(ls); build(rs);
	Vec A;
	int len=r-l+1;
	fo(u,0,1) fo(v,0,1)
	{
		g[x][u][v].resize(len+1);
		fo(i,0,len) g[x][u][v][i]=-INF;
	}
	fo(u,0,1) fo(v,0,1) fo(w,0,1) fo(t,0,1)
	{
		A.clear();
		get(A,g[lc][u][v],g[rc][w][t]);
		merge(g[x][u][t],A,v&&w);
	}
}
//calc(g)
struct node{
	ll x; int y;
	friend inline bool operator<(const node &A,const node &B)
	{
		if(A.x!=B.x) return A.x<B.x;
		return A.y<B.y;
	}
	friend inline node operator+(const node &A,const node &B)
	{
		return (node){A.x+B.x,A.y+B.y};
	}
};
int now,pos[N<<2][2][2];
node f[2],pre[2];
inline void find(Vec &A,int &p)
{
	for(;p<A.size()-1&&A[p+1]-A[p]>=now;p++);
}
inline void calcf(int u)
{
	fo(i,0,1) pre[i]=f[i],f[i]=(node){-inf,-inf};
	fo(x,0,1) fo(y,0,1)
	{
		find(g[u][x][y],pos[u][x][y]);
		node tmp=(node){g[u][x][y][pos[u][x][y]],pos[u][x][y]},las;
		fo(z,0,1)
		{
			las=tmp+pre[z]; las.x-=1ll*tmp.y*now;
			f[y]=max(f[y],las);
			if(z&&x)
			{
				las.y--; las.x+=now;
				f[y]=max(f[y],las);
			}
		}
	}
}
void ask(int x,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return (void)(calcf(x));
	int mid=l+r>>1;
	if(L<=mid) ask(ls,L,R);
	if(mid<R)  ask(rs,L,R);
}
int n,m;
struct query{
	int l,r,k,L,R;
}q[N];
ll ans[N];
int id[N],mid[N];
inline void init()
{
	fo(i,1,m) mid[i]=((ll)q[i].L+q[i].R)>>1,id[i]=i;
	sort(id+1,id+m+1,[&](const int &x,const int &y){return mid[x]>mid[y];});
	fo(i,1,n<<2) fo(j,0,1) fo(k,0,1) pos[i][j][k]=0;
}
inline void work()
{
	for(int x,flag;;)
	{
		init(); flag=1;
		fo(i,1,m)
		{
			x=id[i];
			if(q[x].L>q[x].R) continue;
			flag=0; now=mid[x];
			f[0]=(node){0,0}; f[1]=(node){-inf,inf};
			ask(1,1,n,q[x].l,q[x].r);
			f[0]=max(f[0],f[1]);
			if(f[0].y>=q[x].k) q[x].L=mid[x]+1;
			else q[x].R=mid[x]-1;
		}
		if(flag) break;
	}
	int x;
	fo(i,1,m) mid[i]=q[i].L-1,id[i]=i;
	sort(id+1,id+m+1,[&](const int &x,const int &y){return mid[x]>mid[y];});
	fo(i,1,n<<2) fo(j,0,1) fo(k,0,1) pos[i][j][k]=0;
	fo(i,1,m)
	{
		x=id[i];
		now=mid[x];
		f[0]=(node){0,0}; f[1]=(node){-inf,inf};
		ask(1,1,n,q[x].l,q[x].r);
		f[0]=max(f[0],f[1]);
		ans[x]=f[0].x+1ll*q[x].k*now;
	}
}
int main()
{
	n=read(); m=read();
	build(1,1,n);
	fo(i,1,m)
	{
		q[i].l=read(),q[i].r=read(),q[i].k=read();
		q[i].L=-35000; q[i].R=sum/q[i].k;
	}
	work();
	fo(i,1,m) printf("%lld\n",ans[i]);
	return 0;
}