HJWJBSR's Blog

单独放题解了= =

题意：有n个整数，然后从中间选出k段不同的、长度在[L,R]之间的区间，使得所有区间的区间和加起来最大。n,k<=50w

题解：思路对于我这种想不到的弱逼还是蛮屌的。首先看上去很有堆的感觉，但是明显把不能枚举状态，于是考虑如何优化。。那可以维护对于每个点x以它为左端点的三元组[L,R,w]，表示从x到w的区间和是右端点在L到R里面最大的，那么就可以每次把n个左端点里面最大的加进来，然后分成[L,w-1,w1]以及[w+1,R,w2]加入堆中。而求w就是先搞出一个前缀和s[i]，然后询问L到R的s[i]最大值，即RMQ问题，我用了倍增解，然后复杂度就是差不多O(nlog^2 n)。。

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 500050
#define M 30
#define ll long long
#define INF 0x7f7f7f7f
struct Point
 {
 	int le,ri,bg,wz;ll t;
 	bool operator < (const Point &x) const
 	 {
 	 	return t>x.t||(t==x.t&&le>x.t)||(t==x.t&&le==x.le&&bg>x.bg);
 	 }
 };
multiset <Point> li;
set <Point> :: iterator it;
int n,m,st[N][M],L,R;
ll s[N],ans=0;
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
int Find(int x,int y,int z)
 {
 	if (x>y) return -INF;
 	if (y-x+1==(1 << z)) return st[x][z];
 	if (y-x+1<(1 << z)) return Find(x,y,z-1);
 	int i=Find(x+(1 << z),y,z-1);
 	return s[i]>s[st[x][z]]?i:st[x][z];
 }
inline Point Make(int x,int y,int z)
 {
 	Point i;
 	i.bg=x;i.le=y;i.ri=z;i.wz=Find(y,z,20);
 	i.t=s[i.wz]-s[i.bg-1];
 	return i;
 }
int main()
 {
 	int i,j,k,l;Point q,w,e;
 	memset(s,0,sizeof(s));memset(st,0,sizeof(st));
 	scanf("%d%d%d%d",&n,&m,&L,&R);
 	for (i=1;i<=n;i++)
 	  s[i]=s[i-1]+Read(),st[i][0]=i;
 	for (i=1;(1 << i)<=n;i++)
 	 for (j=1;j<=n-(1 << i)+1;j++)
 	   st[j][i]=s[st[j+(1 << (i-1))][i-1]]>s[st[j][i-1]]?
 	     st[j+(1 << (i-1))][i-1]:st[j][i-1];
 	for (i=1;i<=n-L+1;i++)
 	  li.insert(Make(i,i+L-1,min(i+R-1,n)));
 	while (m--)
 	 {
 	 	it=li.begin();q=*it;li.erase(it);ans+=q.t;
 	 	if (q.wz!=q.le)
 	 	  li.insert(Make(q.bg,q.le,q.wz-1));
 	 	if (q.wz!=q.ri)
 	 	  li.insert(Make(q.bg,q.wz+1,q.ri));
 	 }
 	cout <<ans<<endl;
 	return 0;
 }