Description:
给定一个正整数数列 a1,a2,…,an,每一个数都在 0∼p−1 之间。
可以对这列数进行两种操作:
添加操作:向序列后添加一个数,序列长度变成 n+1;
询问操作:询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始,整数序列为空。
一共要对整数序列进行 m 次操作。
写一个程序,读入操作的序列,并输出询问操作的答案。
Solution:
大部分大佬用的是线段树(我第一次也用的线段树)
现在发现用st超级容易
每次插入只需要修改与最后一个点有关的值即可
典型的空间换时间;
线段树空间复杂度O(4N),查询插入都是O(logN),不过时间里面还有许多浪费的成分
st空间复杂度O(NlogN),查询O(1),插入O(logN),比线段树快至少一半
代码如下
Code:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e5+10,M=log2(N)+10;
int f[N][M];
int query(int l,int r){
int k=log2(r-l+1);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int n;
int insert(int a){
f[++n][0]=a;
for(int i=1;1<<i<=n;i++)
f[n-(1<<i)+1][i]=max(f[n-(1<<i)+1][i-1],f[n-(1<<i-1)+1][i-1]);
}
int q,p,a;
char op[2];
int x;
int main(){
scanf("%d%d",&q,&p);
for(;q--;){
scanf("%s%d",op,&x);
if(op[0]=='A')
insert((ll(x)+a)%p);
else{
printf("%d\n",a=query(n-x+1,n));
}
}
return 0;
}