HDU 6319 单调队列

 题目:http://acm.hdu.edu.cn/showproblem.php?pid=6319

题意:t个测试,第二行六个参数,第三行是k个元素从a[1]到a[k],一共有n个元素,不足的用给出的公式补齐。

要你输出从i=1开始,对于长度为m的区间,假设有number个。

                    要求求出这个区间最大值,以及从左向右扫描最大值变化的次数,注意遇到第一个数就算变化一次。

再把这number个数异或输出。

题解:逆向构造单调队列,从i+m-1<=n开始记录,此时若正向求是最后一个,逆向是第一个。

队列里的元素存储的是比当前大的,

这样的话,队首元素就是最大值,队列长度就是变化次数(因为每次逆向开始构造,存储的数比当前的数大,顺着看就是遇到了一个比当前数大的元素,变化次数就加一)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=10000005;
int a[maxn],Q[maxn];
int n,m,k,p,q,r,mod;
int head,tail;
ll res1,res2;
int main()
{
	int t;
	scanf("%d",&t);
	 while(t--){
        scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&q,&r,&mod);
        for(int i=1;i<=k;i++){
            scanf("%d",&a[i]);
        }
        for(int i=k+1;i<=n;i++){
            a[i]=(1ll*p*a[i-1]+1ll*q*i+r)%mod;
        }
       head=1; tail=0;
	   res1=res2=0;
	   for(int i=n;i>0;i--) 
          {
          	while(tail>=head&&a[Q[tail]]<=a[i])tail--;
          	    Q[++tail]=i;
          	if(i+m-1<=n)
          	{
          		while(Q[head]>=i+m)head++;
          		res1+=i^a[Q[head]];
          		res2+=i^(tail-head+1);
          		
			  }
		  }
		  printf("%lld %lld\n",res1,res2);
     }
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P2485 [SDOI2011]计算器

题目描述 你被要求设计一个计算器完成以下三项任务: 1、给定y、z、p,计算y^z mod p 的值; 2、给定y、z、p,计算满足xy ≡z(mod p)的最...

440100
来自专栏数据结构与算法

洛谷P2742 【模板】二维凸包

2、若$p_{i{(i > 3)}}$在直线$p_{i - 1}, p_{i - 2}$的右侧,则不断的弹出栈顶,直到该点在直线左侧

7420
来自专栏CDA数据分析师

excel公式中14种运算符,帮你整理齐了

文 | 赵志东 运算符是公式中最主要的组成部分,包括数学运算符、逻辑运算符和连接运算符等,下面我们就全面学习一下excel公式里的运算符。 一、运算符 1、 数...

21750
来自专栏函数式编程语言及工具

Scala Macros - 元编程 Metaprogramming with Def Macros

    Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具,可以通过它来解决一些用普通编程或者类层次编程(type level pr...

33390
来自专栏kalifaの日々

POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>...

36670
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

31910
来自专栏我是业余自学C/C++的

线性表——链式描述(双向链表)

15430
来自专栏五分钟学算法

每天一算:Minimum Size Subarray Sum

leetcode上第209号问题:Minimum Size Subarray Sum

7910
来自专栏Android知识点总结

03--图解数据结构之双链表实现容器

13550
来自专栏Hongten

一看就懂的快速排序方法_java版

=================================================

2.4K20

扫码关注云+社区

领取腾讯云代金券