这是两张照片,之间只按下了F7进行下一步,但是n却莫名其妙的大了非常多:
附代码:
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,maxn[N][20];
long long sum[N];
void limit()
{
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<(j-1))-1<=n;i++)
{
int a=maxn[i][j-1],b=maxn[i+(1<<(j-1))][j-1];
if(sum[a]>sum[b])maxn[i][j]=a;
else maxn[i][j]=b;
}
}
int query(int l,int r)
{
int k=log2(r-l+1);
int a=maxn[l][k],b=maxn[r-(1<<k)+1][k];
if(sum[a]>sum[b])return a;
else return b;
}
struct node
{
int l,rl,rr,mx;
node(){}
node(int l,int rl,int rr):l(l),rl(rl),rr(rr),mx(query(rl,rr)){}
int ans(){return sum[mx]-sum[l-1];}
};
bool operator<(node a,node b)
{
return a.ans()<b.ans();
}
struct pq
{
private:
node h[N];long long n;
void up(long long x)
{
while(x>1&&h[x>>1]<h[x])
std::swap(h[x],h[x>>1]),x>>=1;
}
void down(long long x)
{
while(x<<1<=n)
{
long long t=x<<1;
if(t+1<=n&&h[t]<h[t+1])t++;
if(h[t]<h[x])break;
std::swap(h[x],h[t]);
x=t;
}
}
public:
pq(){n=0;}
void push(node x)
{
n++;
h[n]=x;
up(n);
}
node top()
{
return h[1];
}
void pop()
{
std::swap(h[1],h[n--]);down(1);
}
}p;
int main()
{
freopen("P2048_2.in","r",stdin);
int k,L,R;
scanf("%d%d%d%d",&n,&k,&L,&R);
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
maxn[i][0]=i;sum[i]=sum[i-1]+x;
}
limit();
for(int i=1;i<=n;i++)if(i+L-1<=n)p.push(node(i,i+L-1,min(i+R-1,n)));
long long ans=0;
while(k--)
{
node t=p.top();p.pop();
ans+=t.ans();
if(t.rl!=t.mx)p.push(node(t.l,t.rl,t.mx-1));
if(t.rr!=t.mx)p.push(node(t.l,t.mx+1,t.rr));
}
printf("%lld",ans);
return 0;
}
附数据: Link