[NOI 2010] Super piano

Luogu portal

thinking

My thinking of this problem is one step away from the positive solution QAQ

First, make a violent attack, and you can find almost all MLE s.

There is a group of special cases in the data: \ (k = 1 \), that is, find the sum of intervals with the maximum interval length between \ ([L,R] \).

For interval summation, it is not difficult to think of using prefix and optimization. Remember that the original array is \ (a \), and the prefix and array \ (sum \) are:

Then the prefix sum of interval \ ((L, R] \) can be expressed as \ (sum_r - sum_{l} \)

Therefore, we can enumerate the right endpoint \ (r \) and take the minimum \ (sum \) value in the \ ([r - R,r - L] \) interval.

It is found that \ (\ text{RMQ} \) optimization can be used, and the time complexity \ (O(N\log N) \) plus violence can get 30pts

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int maxn = 5e5 + 5;
int n,k,L,R;
typedef long long ll;
ll a[maxn],sum[maxn],f[maxn][20];
priority_queue<ll> q;
void ST() {
	for(int k = 1;(1 << k) < n;++ k) {
		for(int i = 0;i + (1 << k) - 1 < n;++ i) {
			f[i][k] = min(f[i][k - 1] , f[i + (1 << (k - 1))][k - 1]);
		}
	}
	return ;
}
int lg[maxn];
int RMQ(int l,int r) {
	int k = lg[r - l + 1];
	return min(f[l][k] , f[r - (1 << k) + 1][k]);
}
void work() {
	for(int i = 0;i < n;++ i)f[i][0] = sum[i];
	for(int i = 2;i <= n;++ i)lg[i] = lg[i >> 1] + 1;
	ST();
	ll ans = sum[L];
	for(int i = L;i <= R;++ i) {
		ans = max(ans , sum[i] - RMQ(i - L , max(i - R , 0)));
	}
	printf("%lld",ans);
	return ;
} 
int main() {
	scanf("%d%d%d%d",&n,&k,&L,&R);
	for(int i = 1;i <= n;++ i)scanf("%lld",&a[i]),sum[i] = sum[i - 1] + a[i];
	if(k == 1) {
		work();
		return 0;
	}
	for(int i = 1;i <= n - L + 1;++ i) {
		for(int j = i + L - 1;j <= min(n , i + R - 1);++ j) {
			ll val = sum[j] - sum[i - 1];
			q.push(val);
		}
	}
	ll ans = 0;
	for(int i = 1;i <= k;++ i) {
		ans += q.top();
		q.pop();
	}
	printf("%lld",ans);
	return 0;
}

Think again, can we optimize it again?

It is obviously greedy to take the sum of the previous \ (k \) large interval.

Combined with special examples, it seems that the author is implying to promote and try from the situation of \ (k=1 \).

When \ (k = 1 \), the maximum interval sum can be taken directly.

So what should we do when \ (k = 2 \)? How to find the next largest value?

Then I got stuck here

When the maximum interval \ ([T, r_0] \) is obtained, for all \ (R \ NEQ, r_0 \), \ (R \) is the end of the interval, the maximum interval sum of the interval can obviously be used as an alternative.

However, there is another case: when \ (r_0 \) is the end of the interval, the second largest interval sum of the interval can also be used as an alternative.

If the corresponding legal interval of \ (r_0 \) is \ ([l,r] \), a global sub maximum sum may also be generated in \ ([l,t-1] \) and \ ([t + 1,r] \).

In this case, it is obvious that you can directly enumerate and compare the larger of the two cases.

To generalize, it is not difficult to think of a positive solution:

• Create a large root heap \ (q \) with interval and as keywords. The structural elements in \ (q \) are the desirable interval boundary, \ (r \) and the corresponding \ (t \) values respectively

• Cycle \ (k \) times, take out the top of the heap \ (u \) each time, set the end of the corresponding interval as \ (r_0 \) and the boundary as \ ([l,r] \), add the answers to \ (sum {r_0} - sum_t \), then add \ ((l,t-1,r_0,\text{RMQ(l,t-1)})\),\((t+1,r,r_0,\text{RMQ(t+1,r)}) \) to the heap, and finally output the answers

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int maxn = 5e5 + 5;
int n,k,L,R;
typedef long long ll;
ll a[maxn],sum[maxn],f[maxn][20];
int pos[maxn][20];
struct Chtholly {
	int x,l,r,t;
	Chtholly() {
		x = l = r = t = 0;
	}
	Chtholly(int x,int l,int r,int t):x(x),l(l),r(r),t(t){};
	bool operator < (const Chtholly& p)const {
		return sum[x] - sum[t] < sum[p.x] - sum[p.t];
	}
};
priority_queue<Chtholly> q;
void ST() {
	for(int k = 1;(1 << k) <= n + 1;++ k) {
		for(int i = 0;i + (1 << k) - 1 <= n;++ i) {
			if(f[i][k - 1] < f[i + (1 << (k - 1))][k - 1]) {
				f[i][k] = f[i][k - 1];
				pos[i][k] = pos[i][k - 1];
			}
			else {
				f[i][k] = f[i + (1 << (k - 1))][k - 1];
				pos[i][k] = pos[i + (1 << (k - 1))][k - 1];
			}
		}
	}
	return ;
}
int lg[maxn];
int RMQ(int l,int r) {
	if(l > r)swap(l , r);
	int k = lg[r - l + 1];
	if(f[l][k] < f[r - (1 << k) + 1][k])return pos[l][k];
	return pos[r - (1 << k) + 1][k];
}
void init_RMQ() {
	for(int i = 0;i <= n;++ i)f[i][0] = sum[i],pos[i][0] = i;
	for(int i = 2;i <= n;++ i)lg[i] = lg[i >> 1] + 1;
	ST();
	for(int i = L;i <= n;++ i) {
		int l = i - L,r = max(i - R , 0);
		int t = RMQ(r , l);
		q.push(Chtholly(i , r , l , t));
	}
	return ;
} 
int main() {
	scanf("%d%d%d%d",&n,&k,&L,&R);
	for(int i = 1;i <= n;++ i)scanf("%lld",&a[i]),sum[i] = sum[i - 1] + a[i];
	init_RMQ();
	ll ans = 0;
	for(int i = 1;i <= k;++ i) {
		Chtholly u = q.top();
		q.pop();
		int l = u.l,r = u.r,t = u.t,x = u.x;
		ans += sum[x] - sum[t];
		if(l < t)q.push(Chtholly(x , l , t - 1 , RMQ(l , t - 1)));
		if(r > t)q.push(Chtholly(x , t + 1 , r , RMQ(t + 1 , r)));
	}
	printf("%lld",ans);
	return 0;
}