终于更博了, 之前有点摆
题目 https://www.luogu.org/problemnew/show/P2048
题意:
有一个长为 \(n\) 的数列 \(A\) , 定义区间 \([i, j]\) 的权值为 \(\sum_{k=i}^j A_k\)
现在选出 \(k?\) 个不相同的区间, 使得它们的权值和最大. 并满足每个选出的区间长度∈\([L, R]?\)
暴力 \(n^2?\) 不说了, 讲正解.
正解:
快速求出 "区间集" \((p,l,r)\) 的最大答案 (下文中会对此有解释)
首先区间 \([l,r]?\) 的答案为 \(sum[r]-sum[l-1]?\) .
那么如何确保区间长度 \(r-l+1\in [L,R]\) 呢?
显然, 对于一个确定的左端点 \(i?\) , 它的右端点的取值范围是 \([i+L-1,i+R-1]?\) .
在这 \(R-L+1\) 个左端点为 \(i\) 的区间中, 如何选出区间和最大的呢?
对于每一个区间, 其区间和为 \(sum[j]-sum[i]\space(j\in[i+L-1,i+R-1])?\)
其中 \(sum[i]\) 为定值, 那么问题转换为求 \(sum[i]\space(j\in[i+L-1,i+R-1])\) 的最值
既然是 \(RMQ\) (区间最值) 那么就可以用 ST 表来维护, 每次可以 \(\Theta(1)\) 求解.
那么现在, 我们可以求出区间集 {\([l,r]\)} \(\space(r\in[l+L-1,l+R-1])\) 中的最大区间.
用一个三元组 \((p,l,r)\) 来表示一个左端点为 \(p\), 右端点属于 \([l,r]\) 区间集 \(S\).
如何做到答案覆盖整个区间不遗漏
先以每个位置为左端点构造 \(n\) 个三元组, 注意边界.
同时对每个三元组记录出它的答案, 以及取到最大值区间时的右端点位置 (这个位置可以预处理倍增数组).
把它们丢到堆里面, 每次取出最大的弹掉, 进行 \(k\) 次.
其中要注意的是在弹掉一个三元组 \((p,l,r)?\) 后, 就意味着去掉了所有的区间 \([p,i]\space(i\in[l,r])?\)
然而实际上我们只取出了一个区间 \((p,mid)\) (\(mid?\) 即为 "取到最大值区间时的右端点位置").
所以还要保留区间 \([p,i]\space(i\in[l,mid-1])\) 以及 \([p,i]\space(i\in[mid+1,r])\) 的答案.
所以将这两个东西加入堆中, 并且要算出它们的 \(mid\) .
跑 \(k\) 次就可以了.
代码:
- #include<bits/stdc++.h>
- #define il inline
- #define RG register int
- #define ll long long
- #define gc getchar
- using namespace std;
- il int rd()
- {
- RG x=0,flag=1;
- char ch=0;
- while((ch>'9'||ch<'0')&&ch!='-')ch=gc();
- if(ch=='-')flag=-1,ch=gc();
- while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=gc();
- return x*flag;
- }
- const int N=500005,LOG=22;
- ll f[N][LOG],sum[N];
- int pos[N][LOG],Log[N];
- ll Ans;
- int n,k,L,R;
- ll query(int l0,int r0)
- {
- int t=Log[r0-l0+1];
- return max(f[l0][t],f[r0-(1<<t)+1][t]);
- }
- int query2(int l0,int r0)
- {
- int t=log2(r0-l0+1);
- return f[l0][t]>f[r0-(1<<t)+1][t]?pos[l0][t]:pos[r0-(1<<t)+1][t];
- }
- struct node {
- int p,l,r,mid; ll res;
- bool operator <(node x)const {return res<x.res;}
- };
- priority_queue<node> q;
- int main ()
- {
- scanf("%d%d%d%d",&n,&k,&L,&R);
- int LogN=log2(n)+1;
- for(RG i=1;i<=n;i++)sum[i]=sum[i-1]+rd();
- Log[0]=-1;
- memset(f,0xcf,sizeof(f));
- for(RG i=1;i<=n;i++) f[i][0]=sum[i],pos[i][0]=i,Log[i]=Log[i>>1]+1;
- for(RG j=1;j<=LogN;j++)
- for(RG i=1;i+(1<<j)<=n+1;i++)
- {
- if(f[i][j-1]>f[i+(1<<j-1)][j-1])
- {
- f[i][j]=f[i][j-1];
- pos[i][j]=pos[i][j-1];
- }
- else
- {
- f[i][j]=f[i+(1<<j-1)][j-1];
- pos[i][j]=pos[i+(1<<j-1)][j-1];
- }
- }
- for(RG i=1;i+L-1<=n;i++)
- {
- ll t=query(i+L-1,min(i+R-1,n))-sum[i-1];
- int midt=query2(i+L-1,min(n,i+R-1));
- q.push(node{i,i+L-1,min(i+R-1,n),midt,t});//
- }
- for(RG i=1;i<=k;i++)
- {
- Ans+=q.top().res;
- node t=q.top();
- int p0=t.p,l0=t.l,r0=t.r,mid0=t.mid;
- q.pop();
- if(mid0>l0)
- q.push(node{p0,l0,mid0-1,query2(l0,mid0-1),query(l0,mid0-1)-sum[p0-1]});
- if(mid0<r0)
- q.push(node{p0,mid0+1,r0,query2(mid0+1,r0),query(mid0+1,r0)-sum[p0-1]});
- }
- cout<<Ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2956095.html