LuoguP2048「NOI2010」题解

发表于 更新于

贪心 + 主席树 + 堆

题目描述

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。

一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。

小Z决定创作一首由k个超级和弦组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

输入格式

输入第一行包含四个正整数n, k, L, R。其中n为音符的个数，k为乐曲所包含的超级和弦个数，L和R分别是超级和弦所包含音符个数的下限和上限。

接下来n行，每行包含一个整数Ai，表示按编号从小到大每个音符的美妙度。

输出格式

输出只有一个整数，表示乐曲美妙度的最大值。

Inputs and Outputs examples

Inputs’ e.g. #1

1
2
3
4
5
4 3 2 3
3
2
-6
8

Outputs’ e.g. #1

1
11

说明

所有数据满足：-1000 ≤ Ai ≤ 1000，1 ≤ L ≤ R ≤ n且保证一定存在满足要求的乐曲。

分析

双倍经验 三倍 四倍

其实一句话题意就是就是求出前$k$大的在$(l,r)$区间内的最大子串和.

我们发现这个题可以贪心一下,先找到最大值,然后把他删掉,然后接着找最大值.

然后我们枚举左端点$l$,我们发现对于给定的$l$,所有满足条件的$r$构成了一个区间.

显然我们要选区间的前缀和最大的$r$,因为一定要减去$l$的前缀和.

然后我们对于每一个给定的$l$,都求出了一个最大合法的子串和.

然后我们把这个值扔进堆里,就能得到最大值.

这个时候,我们发现很可能区间第二大就可能是当前最大值,那么我们把区间第二大扔进堆里,然后取出第二大就再插入第三大.

然后我们发现,这就是一个静态区间$k$大的问题,然后我们就可以来发主席树~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#include<ctime>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 3e7 + 10;
const int MAXM = 5e5 + 10;
std::priority_queue<std::pair<int,int> > Q;
long long ans;
int n,m,x,y,l,r,cnt;
int s[MAXM],t[MAXM],root[MAXN];
namespace Presistent_SegMentTree{
    struct SegMentTree{
        int ch[2],sum;
    }T[MAXN];
    inline void Update(int &rt,int pre,int l,int r,int k){
        rt = ++cnt;
        T[rt].sum = T[pre].sum + 1;
        T[rt].ch[0] = T[pre].ch[0]; T[rt].ch[1] = T[pre].ch[1];
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(k <= mid) Update(T[rt].ch[0],T[pre].ch[0],l,mid,k);
        else Update(T[rt].ch[1],T[pre].ch[1],mid+1,r,k);
    }
    inline int Query(int x,int y,int l,int r,int k){
        if(l == r) return l;
        int res = T[T[y].ch[1]].sum - T[T[x].ch[1]].sum;
        int mid = (l + r) >> 1;
        if(res < k) return Query(T[x].ch[0],T[y].ch[0],l,mid,k - res);
        else return Query(T[x].ch[1],T[y].ch[1],mid+1,r,k);
    }
}
/* functions */
using namespace Presistent_SegMentTree;
const int inf = 1e9;
const int qwq = 5e8;
int main(int argc,char *argv[]){
    scanf("%d%d%d%d",&n,&m,&l,&r);
    FOR(i,1,n,1){
        scanf("%d",&x);
        s[i] = s[i-1] + x;
        Update(root[i],root[i-1],0,inf,s[i] + 5e8);
    }
    FOR(i,1,n+1-l,1){
        t[i]++; x = Query(root[i+l-2],root[std::min(n,i+r-1)],0,inf,t[i]);
        Q.push(std::make_pair(x-s[i-1],i));
    }
    while(m){
        std::pair<int,int> pr = Q.top(); Q.pop(); m--;
        x = pr.first; y = pr.second;
        ans += 1ll * (x - 5e8);
        if(t[y] < std::min(n,y+r-1) - (y + l - 1) + 1){
            t[y]++;
            x = Query(root[y+l-2],root[std::min(n,y+r-1)],0,inf,t[y]);
            Q.push(std::make_pair(x-s[y-1],y));
        }
    }
    printf("%lld\n",ans);
    return 0;
}

THE END