蒟蒻刚学OI,求助手写堆
  • 板块灌水区
  • 楼主Lazy_Labs
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/12/5 16:23
  • 上次更新2023/11/3 22:50:34
查看原帖
蒟蒻刚学OI,求助手写堆
376137
Lazy_Labs楼主2021/12/5 16:23

这是两张照片,之间只按下了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

2021/12/5 16:23
加载中...