BZOJ——1012: [JSOI2008]最大数maxnumber || 洛谷—— P1198 [JSOI2008]最大数
2024-08-27 15:29:36
http://www.lydsy.com/JudgeOnline/problem.php?id=1012||
https://www.luogu.org/problem/show?pid=1198
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 10824 Solved: 4735
[Submit][Status][Discuss]
Description
现在请求你维护一个数列,要求提供以下两种操作:1、 查询操作。语法:Q L 功能:查询当前数列中末尾L
个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。2、 插入操作。语法:A n 功能:将n加
上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取
模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有一个
数。
Input
第一行两个整数,M和D,其中M表示操作的个数(M <= 200,000),D如上文中所述,满足D在longint内。接下来
M行,查询操作或者插入操作。
Output
对于每一个询问操作,输出一行。该行只有一个数,即序列中最后L个数的最大数。
Sample Input
5 100
A 96
Q 1
A 97
Q 1
Q 2
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
96
93
96
HINT
数据如下http://pan.baidu.com/s/1i4JxCH3
Source
①区间查询最值考虑线段树、
#include <algorithm>
#include <iostream>
#include <cstdio> using namespace std; const int N();
int t,mod,n,x[N],ans;
char ch,s[N]; struct Tree
{
int l,r,sum;
}tr[N<<];
#define lc (now<<1)
#define rc (now<<1|1)
#define mid (tr[now].l+tr[now].r>>1)
inline void Tree_up(int now)
{
tr[now].sum=max(tr[lc].sum,tr[rc].sum);
}
void Tree_build(int now,int l,int r)
{
tr[now].l=l; tr[now].r=r;
if(l==r) return ;
Tree_build(lc,l,mid);
Tree_build(rc,mid+,r);
}
void Tree_change(int now,int to,int x)
{
if(tr[now].l==tr[now].r)
{
tr[now].sum=x;
return ;
}
if(to<=mid) Tree_change(lc,to,x);
else Tree_change(rc,to,x);
Tree_up(now);
}
int Tree_query(int now,int l,int r)
{
if(tr[now].l==l&&r==tr[now].r) return tr[now].sum;
if(r<=mid) return Tree_query(lc,l,r);
else if(l>mid) return Tree_query(rc,l,r);
else return max(Tree_query(lc,l,mid),Tree_query(rc,mid+,r));
} int main()
{
scanf("%d%d",&t,&mod);
for(int i=;i<=t;i++)
{
cin>>ch>>x[i]; s[i]=ch;
if(ch=='A') n++;
}
Tree_build(,,n);
int cnt=;
for(int i=;i<=t;i++)
{
if(s[i]=='A')
Tree_change(,++cnt,(ans+x[i])%mod);
else
{
ans=Tree_query(,cnt-x[i]+,cnt);
printf("%d\n",ans);
}
}
return ;
}
线段树AC
②单调递减栈,二分查找位于L处的值
#include <algorithm>
#include <cstdio> using namespace std; const int N();
int n,mod,ans,x;
int stack[N],top,num[N],len; int main()
{
scanf("%d%d",&n,&mod);
for(char ch[];n--;)
{
scanf("%s%d",ch,&x);
if(ch[]=='A')
{
x=(x+ans)%mod;
num[++len]=x;
for(;num[stack[top]]<=x&&stack[top]>&⊤) top--;
stack[++top]=len;
}
else
{
int l=,r=top;
for(int mid;l<=r;)
{
mid=l+r>>;
if(stack[mid]<len-x+) l=mid+;
else r=mid-,ans=num[stack[mid]];
}
printf("%d\n",ans);
}
}
return ;
}
单调栈AC
最新文章
- .Learning.Python.Design.Patterns.2nd.Edition之单实例模式
- javascript 自定义类型 属性,方法
- HaProxy+keepalived实现负载均衡
- Asp.net创建伪静态页面
- Ajax请求传递参数遇到的问题
- Payssion,海外本地支付_海外本地收款_小语种本地支付_外贸收款_外贸网店收款_欧洲本地支付_俄罗斯本地支付_巴西支付_跨境支付_PAYSSION,让跨境支付更轻松!
- Column Addition~DP(脑子抽了,当时没有想到)
- linux下git常用命令
- java多继承
- Python 函数调用&;定义函数&;函数参数
- java+Selenium+TestNg搭建自动化测试架构(3)实现POM(page+Object+modal)
- GUI:GUI的方式创建/训练/仿真/预测神经网络—Jason niu
- javascript与jquery的区别
- CBV FBV rest framework
- GC 提前晋升
- Mysql 日期类型 date、datetime、timestamp.
- android studio生成aar包并在其他工程引用aar包
- python list添加元素的几种方法
- 这些小工具让你的Android 开发更高效
- android多线程-AsyncTask之工作原理深入解析(下)