洛谷 P1198 [JSOI2008]最大数——单调栈/线段树
2024-10-07 19:19:34
先上一波题目 https://www.luogu.org/problem/P1198
题目要求维护后缀最大值 以及在数列的最后面添加一个数
这道题呢我们有两种做法
1.单调栈
因为只需要维护后缀最大值 而我们每次插入都是在最后面添加一个数 所以我们可以维护一个单调栈
栈底到栈顶逐渐增大 因为如果一个数他的位置在你的前面且他比你小 那么他便不会对前面位置的最大值产生影响 可以直接省略
我们在查询的时候只需要二分一下答案 找到比查询位置后的最接近查询位置的数的值就是答案了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
long long read(){
long long ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
char c;
int stk[M],top=;
int n,cnt=;
long long mod,s[M],T=,x;
int main(){
n=read(); mod=read();
for(int i=;i<=n;i++){
c=getchar();
while(c!='Q'&&c!='A') c=getchar();
x=read();
if(c=='Q'){
x=cnt-x+;
long long l=,r=top;
while(l<r){
int mid=(l+r)>>;
if(stk[mid]>=x) r=mid;
else l=mid+;
}
T=s[r];
printf("%lld\n",T);
}
else{
cnt++;
x=(x+T)%mod;
x=(x+mod)%mod;
while(top&&s[top]<=x) top--;
s[++top]=x; stk[top]=cnt;
}
}
return ;
}
2.线段树
线段树就很明显了 设计的操作有单点插入 区间求最大值
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
long long read(){
long long ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
char c;
int n,cnt=;
long long mod,T=,now,s[M*];
void up(int x){s[x]=max(s[x<<],s[x<<^]);}
void insert(int x,int l,int r){
if(l==r){
s[x]=now;
return ;
}
int mid=(l+r)>>;
if(cnt<=mid) insert(x<<,l,mid);
else insert(x<<^,mid+,r);
up(x);
}
long long pmx(int x,int l,int r){
if(now<=l&&r<=cnt) return s[x];
int mid=(l+r)>>;
long long ans=-;
if(now<=mid) ans=max(ans,pmx(x<<,l,mid));
if(cnt>mid) ans=max(ans,pmx(x<<^,mid+,r));
return ans;
}
int main(){
n=read(); mod=read();
for(int i=;i<=n;i++){
c=getchar();
while(c!='Q'&&c!='A') c=getchar();
now=read();
if(c=='Q'){
now=cnt-now+;
T=pmx(,,n);
printf("%lld\n",T);
}
else{
cnt++;
now=(now+T)%mod;
insert(,,n);
}
}
return ;
}
最新文章
- Git 分支合并
- javascript 火狐event.keyCode不能使用event is not defined
- Linux VPS 基本命令
- Background Worker Component
- 关于Tesseract3.01的使用方法
- wp8 自定义相机+nokia滤镜+录制amr音频
- eMMC尺寸
- Android中调用Paint的measureText()方法取得字符串显示的宽度值
- 福建省队集训被虐记——DAY4
- java web 之 BeanUtils.populate的作用
- Java版连连看
- python基础—装饰器
- STM32F10x的启动汇编分析
- Codeforces.472F.Design Tutorial: Change the Goal(构造 线性基 高斯消元)
- 100BASE-TX、100Base-FX等含义
- 用IntelliJ IDEA编译,编译之后提示 无效的标记: -release
- 图标网站,IcoMoon,自己动手做一个 font
- poj 1184
- Maven 环境隔离实践
- bzoj千题计划199:bzoj1055: [HAOI2008]玩具取名
热门文章
- Cocos2d Box2D之浮动刚体
- Ubuntu18.10下出现Could not get lock /var/lib/dpkg/lock的错误
- 关于html 修改滚动条的问题
- 51.Lowest Common Ancestor of a Binary Tree(二叉树的最小公共祖先)
- kubernetes集群的安装异常汇---docker的驱动引擎
- 分支结构if 语句举例
- http请求访问响应慢问题解决的基本思路
- 四、yml文件的写法
- jQuery 菜单 垂直菜单实现
- CNN基础四:监测并控制训练过程的法宝——Keras回调函数和TensorBoard