最大数

NC50455. 最大数

描述

给定一个正整数数列 $a_1,a_2,a_3, \cdots,a_n$ ，每一个数都在 $0 \sim p–1$ 之间。可以对这列数进行两种操作：
添加操作：向序列后添加一个数，序列长度变成n+1；询问操作：询问这个序列中最后L个数中最大的数是多少。程序运行的最开始，整数序列为空。写一个程序，读入操作的序列，并输出询问操作的答案。

输入描述

第一行有两个正整数m,p，意义如题目描述；
接下来m行，每一行表示一个操作。如果该行的内容是QL，则表示这个操作是询问序列中最后L个数的最大数是多少；如果是At，则表示向序列后面加一个数，加入的数是。其中，t是输入的参数，a是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则a=0）。
第一个操作一定是添加操作。对于询问操作，且不超过当前序列的长度。

输出描述

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

示例1

输入:

输出:

说明:

最后的序列是97,14,60,96。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 92ms, 内存消耗: 18796K, 提交时间: 2020-05-30 14:12:32

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll p;
ll f[1<<22][22];
void change(ll x,int m)
{
	f[m][0]=x;
	for(int i=1;(1<<i)<=m;i++)
		f[m][i]=max(f[m][i-1],f[m-(1<<(i-1))][i-1]);
}
ll ans(int l,int r)
{
	int k=log(r-l+1)/log(2);
	return max(f[l+(1<<k)-1][k],f[r][k]);
}
char op;
ll t,a;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>p;
	while(n--)
	{
		cin>>op>>t;
		if(op=='A')
		{
			change((t+a)%p,++m);
		}
		else
		{
			a=ans(m-t+1,m);
			cout<<a<<"\n";
		}
	}
	return 0;
}

上一题

下一题

详情