本文主要是介绍洛谷p1198最大数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题
数据大小是1e6,实现单调修改和区间最大值,和树状数组模板类似,不过有地方需要注意。
求最后l个值得最大值,只需要反着装值,到x求后l,那么求x+l之前的最值就可以了(x到n的值已求)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define in(x) scanf("%lld",&x);
using namespace std;
long long m,d,c[2000005];
void updata(long long pos,long long v)
{for(int i=pos;i<=m;i+=i&(-i))c[i]=max(c[i],v);
}
long long quary(long long pos)
{long long anse=-9999999;for(int i=pos;i;i-=i&(-i))anse=max(anse,c[i]);return anse;
}
int main()
{in(m);in(d);long long cnt=m,k=0;for(int i=1;i<=m;++i){char s;long long x;cin>>s;in(x);if(s=='A'){x=(x+k)%d;updata(cnt,x);cnt--;}else{k=quary(x+cnt);printf("%lld\n",k);}}return 0;
}
这篇关于洛谷p1198最大数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!