Luogu P2048 [NOI2010] Super piano （RMQ+ Priority queue ）

The question ：

Yes n A note , The number is 1 to n . The first i The beauty of a note is $A_i$

We need to find k A piece of music composed of super chords , The number of consecutive notes per paragraph x Satisfy $L\le x\le R$ , Find the maximum value of the music's beauty .

Ideas ：

A triple (x,l,r) Indicates that the left endpoint is x, Right endpoint (l,r). Set the subscript of the maximum value as t, Then the problem turns into a solution $sum[t]-sum[i-1]$, because sum[i-1] Is the fixed value , So we need sum stay (l,r) The maximum value in the interval

Also pay attention to , Put the biggest (x,l,r) After use , To put (x,l,t-1) and (x,t+1,r) Put into the pile , Because the second largest value may exist

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
ll sum[maxn],a[maxn],ans;
int n,L,R,k,table[maxn][30];
struct node{
    
	int s,l,r,t;
	ll val;
	bool operator < (const node &x)const {
    
		return val<x.val;
	}
};
priority_queue<node>p;

void init() {
    
    for (int i = 1; i <= n; i++) table[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
    
            int x = table[i][j - 1], y = table[i + (1 << (j - 1))][j - 1];
            table[i][j] = sum[x] > sum[y] ? x : y;
        }
}
int get(int l, int r) {
    
    int d = log2(r - l + 1);
    int x = table[l][d], y = table[r - (1 << d) + 1][d];
    return sum[x] > sum[y] ? x : y;
}

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();
    for(int i=1;i+L-1<=n;i++){
    
    	int y=min(i+R-1,n);
    	int d=get(i+L-1,y);
    	p.push({
    i,i+L-1,y,d,sum[d]-sum[i-1]});
    }
    while(k--){
    
    	node x=p.top();
    	p.pop();
    	ans+=x.val;
    	if(x.t-1>=x.l){
    
    		int d1=get(x.l,x.t-1);
    	    p.push({
    x.s,x.l,x.t-1,d1,sum[d1]-sum[x.s-1]});
		}
    	if(x.t+1<=x.r){
    
    		int d2=get(x.t+1,x.r);
    	    p.push({
    x.s,x.t+1,x.r,d2,sum[d2]-sum[x.s-1]});
		}
	}
    printf("%lld",ans);
}