• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

51Nod算法马拉松28C题栈单调队列

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

去博客园看该题解


题目传送门 - 51Nod1952


题意概括

  有一个栈,有3种操作:

  Ο 从栈顶加入一个元素

  Ο 从栈底加入一个元素

  Ο 从栈顶弹出一个元素

  现在,求每次操作后栈内元素的最大值和mod (1e9+7)

  n次操作,n<=1e7


 

题解

  这题对于博主这样的蒟蒻,做出来了,万分欣喜。

  我们在搞一个栈的同时,维护一个单调不降的队列。

  然后在弹出栈的时候,如果队尾元素等于当前弹出的元素,那么队尾出队。

  至于两种进队,都是最基础的维护队列的方法。

  每次,最大值就是队尾元素值。


 

代码

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=1e7+5;
const int mod=1e9+7;
int n,a[N],b[N];
int q[N*2],head,tail,st[N*2],first,last;
LL A,B,C,x,aa,bb,MOD;
int main(){
	scanf("%d%lld%lld%lld%lld%lld%lld%lld",&n,&A,&B,&C,&x,&aa,&bb,&MOD);
	for (int i=1,tot=0;i<=n;i++){
		x=(x*aa+bb)%MOD;
		LL xx=x%(A+B+C);
		if (tot<=1||xx<A)
			a[i]=0,b[i]=x,tot++;
		else if (A<=xx&&xx<A+B)
			a[i]=1,b[i]=x,tot++;
		else
			a[i]=2,tot--;
	}
	head=1e7+2,tail=head;
	first=head,last=tail;
	int ans=0;
	for (int i=1;i<=n;i++){
		if (a[i]==0){
			st[++last]=b[i];
			if (q[tail]<=b[i])
				q[++tail]=b[i];
		}
		else if (a[i]==1){
			st[first--]=b[i];
			while (head<tail&&q[head+1]<b[i])
				head++;
			q[head--]=b[i];
		}
		else {
			if (q[tail]==st[last])
				tail--;
			last--;
		}
		ans=(ans+q[tail])%mod;
	}
	printf("%d",ans);
	return 0;
}

  


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#远程数据库备份还原发布时间:2022-07-13
下一篇:
C#(99):一、并行编程 - 数据并行Tasks.Parallel 类发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap