「线段树」「单点修改」洛谷P1198 [JSOI2008]最大数

「线段树」「单点修改」洛谷P1198 [JSOI2008]最大数

题面描述

现在请求你维护一个数列,要求提供以下两种操作:

1、 查询操作。

语法:Q L

功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。

限制:L不超过当前数列的长度。(L>0)

2、 插入操作。

语法:A n

功能:将nnn加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。

限制:nnn是整数(可能为负数)并且在长整范围内。

注意:初始时数列是空的,没有一个数。

输入格式

第一行两个整数,M 和 D,其中 M 表示操作的个数,D 如上文中所述。

接下来的 M 行,每行一个字符串,描述一个具体的操作。语法如上文所述。

输出格式

对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。

样例

样例输入

5 100
A 96
Q 1
A 97
Q 1
Q 2

样例输出

96
93
96

解法1:线段树

没啥可说的,线段树基础题,细节见代码

/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2e5+5,INF=0x3f3f3f3f;
int m,mol;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int tree[maxn*2];
void pushup(int rt){
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
void modify(int rt,int l,int r,int x,int w){
if(l==r){
tree[rt]+=w;return;
}
int mid=(l+r)/2;
if(x<=mid)modify(rt*2,l,mid,x,w);
else modify(rt*2+1,mid+1,r,x,w);
pushup(rt);
}
int query(int rt,int l,int r,int s,int t){
if(s<=l&&r<=t){
return tree[rt];
}
int mid=(l+r)/2,ans=0;
if(s<=mid)ans=max(ans,query(rt*2,l,mid,s,t));
if(t>mid)ans=max(ans,query(rt*2+1,mid+1,r,s,t));
return ans;
}
int main(){
freopen("a.in","r",stdin);
m=read(),mol=read();
int now=0,last=0;
for(int i=1;i<=m;i++){
char str;
int x;
cin>>str>>x;
if(str=='A'){
modify(1,1,m,++now,(x+last)%mol);//动态建树 }else {
last=query(1,1,m,now-x+1,now);
cout<<last<<endl;
}
}
}

解法2:树状数组

#include <bits/stdc++.h>
const int maxn = 2e5+10;
int m,cnt;
int D,last,c[maxn];
int lowbit(int x) {return x&(-x);}
void update(int i,int value){//向下更新
for(;i;i-=lowbit(i))
c[i]=std::max(c[i],value);
}
int query(int i){//向上查询
int res = 0;
for(;i<=m;i+=lowbit(i))//m次操作最多有m个数,m之上就不用查询了
res=std::max(res,c[i]);
return res;
}
void Solve(){
scanf("%d%d",&m,&D);
for(int i=1;i<=m;i++){
char s[2];int x;
scanf("%s%d",s,&x);
if(s[0]=='A'){
cnt++;
update(cnt,(x+last)%D);
}
else{
last = query(cnt-x+1);
printf("%lld\n",last);
}
}
}
int main(){
Solve();
return 0;
}

(假装是自己的代码)

解法3:单调栈

/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2e5+5,INF=0x3f3f3f3f;
int m,mol,n,q[maxn],head,tail,id[maxn];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
void Add(int x){
while(q[tail]<=x&&tail)tail--;//最后一个大于前面的数,前面的稍小的数就没用了,这样也可以保证序列的单调性,才能二分
q[++tail]=x;id[tail]=++n;
}
int query(int x){
int key=n-x+1;//正序
return q[lower_bound(id+head,id+tail+1,key)-id];//二分找到第一个大于key的位置
}
int main(){
freopen("a.in","r",stdin);
m=read(),mol=read();
int now=0,last=0;
head=1;
tail=0;
for(int i=1;i<=m;i++){
char str;
int x;
cin>>str>>x;
if(str=='A'){
Add((x+last)%mol);
}else {
last=query(x);
cout<<last<<endl;
}
}
}
上一篇:我的编码习惯 - Controller规范


下一篇:UIView中的坐标转换