1 solutions
-
0
难度: 绿
算法: 线段树,或其它数据结构
单点修改(把在最后插一个数的操作视为将最后一位从 改为 ),区间查询最大值,直接线段树。
没什么好说的,自己看代码吧。
#include<bits/stdc++.h> using namespace std; int q,x,n,a=0,p; int s[840000],l[840000],r[840000]; char c; void build(int le,int ri,int id){ l[id]=le,r[id]=ri; if(le==ri) return ; build(le,(le+ri)/2,2*id); build((le+ri)/2+1,ri,2*id+1); } void upd(int pos,int num,int id){ int nl=l[id],nr=r[id],mid=(nl+nr)/2; if(nl==pos&&nr==pos){ s[id]=max(s[id],num); return; } if(pos<=mid) upd(pos,num,id*2); if(pos>mid) upd(pos,num,id*2+1); s[id]=max(s[id*2],s[id*2+1]); } int que(int le,int ri,int id){ int nl=l[id],nr=r[id],mid=(nl+nr)/2; if(le<=nl&&nr<=ri) return s[id]; int res=0; if(le<=mid) res=max(res,que(le,ri,id*2)); if(ri>mid) res=max(res,que(le,ri,id*2+1)); return res; } int main(){ ios::sync_with_stdio(0); cin>>q>>p; build(1,q,1); while(q--){ cin>>c>>x; if(c=='A'){ x=((long long)x+a)%p; upd(++n,x,1); } else{ a=que(n-x+1,n,1); printf("%d\n",a); } } }
- 1
Information
- ID
- 129
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 9
- Tags
- # Submissions
- 9
- Accepted
- 4
- Uploaded By