题目描述
现在请求你维护一个数列, 要求提供以下两种操作:
1, 查询操作.
语法: Q L
功能: 查询当前数列中末尾 L 个数中的最大的数, 并输出这个数的值.
限制: L 不超过当前数列的长度.(L>=0)
2, 插入操作.
语法: A n
功能: 将 n 加上 t, 其中 t 是最近一次查询操作的答案(如果还未执行过查询操作, 则 t=0), 并将所得结果对一个固定的常数 D 取模, 将所得答案插入到数列的末尾.
限制: n 是整数 (可能为负数) 并且在长整范围内.
注意: 初始时数列是空的, 没有一个数.
输入输出格式
输入格式:
第一行两个整数, M 和 D, 其中 M 表示操作的个数(M <= 200,000),D 如上文中所述, 满足(0<D<2,000,000,000)
接下来的 M 行, 每行一个字符串, 描述一个具体的操作. 语法如上文所述.
输出格式:
对于每一个查询操作, 你应该按照顺序依次输出结果, 每个结果占一行.
输入输出样例
输入样例 #1: 复制
- 5 100
- A 96
- Q 1
- A 97
- Q 1
- Q 2
输出样例 #1: 复制
96
93
96
说明
[JSOI2008]
本题数据已加强
分析
做法挺多的: 线段树, 单调栈, 分块, ST 表
我只用了线段树与单调栈两种 ^_^
(才不是懒)
代码
线段树做法:
- /*
- ID: Mandy
- language:c++
- problem:luogu 1198
- */
- #include<bits/stdc++.h>
- #define N 1002
- #define M 200005
- #define maxl 8446744073709551616
- #define Max(x,y) (x)>(y)?(x):(y)
- #define Min(x,y) (x)<(y)?(x):(y)
- #define up(i,l,r) for(int i=l;i<=r;++i)
- #define down(i,l,r) for(int i=r;i>=l;--i)
- using namespace std;
- const int maxm=262143;
- long long m,mod,lenth,maxn[M<<2],last,dep=0;
- bool vis[M<<2];
- template<class T>inline void read(T &x)
- {
- x=0;bool flag=0;char ch=getchar();
- while(ch<'0'||ch>'9') flag|=(ch=='-'),ch=getchar();
- while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
- if(flag) x=-x;
- }
- template<class T>void putch(const T x)
- {
- if(x>9) putch(x/10);
- putchar(x%10|48);
- }
- template<class T>inline void put(const T x)
- {
- if(x<0) putchar('-'),putch(-x);
- else putch(x);
- }
- void docu()
- {
- freopen("1198.in","r",stdin);
- freopen("1198.out","w",stdout);
- }
- void readdata()
- {
- read(m);
- read(mod);
- }
- long long ask(int k,int l,int r,int x,int y)
- {
- if(l>y||r<x) return -maxl;
- if(l>=x&&r<=y) return maxn[k];
- else
- {
- int mid=(l+r)>>1;
- long long ans=ask(k<<1,l,mid,x,y);
- long long ans1=ask((k<<1)+1,mid+1,r,x,y);
- if(ans<ans1) ans=ans1;
- return ans;
- }
- }
- void modify(int pos,long long val)
- {
- int l=1,r=200000,k=1;
- while(l!=r)
- {
- int mid=(l+r)>>1;
- if(pos<=mid) r=mid,k<<=1;
- else l=mid+1,k=(k<<1)+1;
- }
- maxn[k]=val;
- k>>=1;
- while(k>=1)
- {
- maxn[k]=max(maxn[k<<1],maxn[(k<<1)+1]);
- k>>=1;
- }
- }
- void work()
- {
- up(i,1,m)
- {
- char judge=getchar();
- while(judge!='A'&&judge!='Q') judge=getchar();
- long long x; read(x);
- if(judge=='Q')
- {
- if(lenth==0)
- {
- putchar('0');
- putchar('\n');
- continue;
- }
- dep=0;
- last=ask(1,1,200000,lenth-(x-1),lenth)%mod;
- printf("%lld\n",last);
- }
- else
- {
- ++lenth;
- x=(x+last)%mod;
- modify(lenth,x);
- }
- }
- }
- int main()
- {
- //docu();
- readdata();
- work();
- return 0;
- }
- View Code
单调栈做法:
- /*************************
- User:Mandy.H.Y
- Language:c++
- Problem:luogu1198 JSOI2008 最大数
- Algorithm:
- *************************/
- #include<bits/stdc++.h>
- #define Max(x,y) ((x)>(y)?(x):(y))
- using namespace std;
- const int maxm = 2e5 + 5;
- int m,d,tp,cnt;
- int s1[maxm],s2[maxm];
- //s1 中单调递减, 进了大数后, 前面的小数就没用了
- //s2 中存下相应的位置
- char *TT,*mo,but[(1 <<15) + 2];
- #define getchar() ((TT == mo && (mo = ((TT = but) + fread(but,1,1 << 15,stdin)),TT == mo)) ? -1 : *TT++)
- template<class T>inline void read(T &x){
- x = 0;bool flag = 0;char ch = getchar();
- while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
- while(isdigit(ch)) x = (x <<1) + (x << 3) + (ch ^ 48),ch = getchar();
- if(flag) x = -x;
- }
- template<class T>void putch(const T x){
- if(x> 9) putch(x / 10);
- putchar(x % 10 | 48);
- }
- template<class T>void put(const T x){
- if(x <0) putchar('-'),putch(-x);
- else putch(x);
- }
- void file(){
- freopen("1198.in","r",stdin);
- // freopen("1198.out","w",stdout);
- }
- void readdata(){
- read(m);read(d);
- }
- int erfen(int x){
- int l = 0,r = tp - 1;
- while(l < r){
- int mid = (l + r)>> 1;
- if(s2[mid] <x) l = mid + 1;// 找第 1 个大于等于 x 的位置
- else r = mid;
- }
- return s1[l];
- }
- void work(){
- int t = 0;
- for(int i = 1;i <= m; ++ i){
- char c = getchar();
- int l,n;
- while(c != 'Q' && c != 'A') c = getchar();
- if(c == 'Q'){
- read(l);
- int ans = erfen(cnt - l + 1);// 找位置
- put(ans);
- puts("");
- t = ans;
- } else {
- ++cnt;
- read(n);
- n = ((long long)n + t) % d;
- while(tp> 0 && s1[tp - 1] <= n) tp--;
- s1[tp++] = n;
- s2[tp - 1] = cnt;
- }
- }
- }
- int main(){
- // file();
- readdata();
- work();
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3158494.html