题目Description
现在请求你维护一个数列，要求提供以下两种操作： 1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。 2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。
Input
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0
Output
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
Sample Input
5 100
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
96
分析
感觉就是个区间最值，写了个线段树就A了。 回头IFS的时候才发现还有树状数组，单调队列，单调栈的做法，但是不会QAQ
= =果然我还是太弱了
代码线段树using namespace std;typedef long long ll;int read(){int x=0,f=1;char ch=getchar();while(ch<‘0’||ch>’9′){if(ch==’-‘)f=-1;ch=getchar();}while(ch>=’0’&&ch<=’9’){x=x*10+ch-‘0′;ch=getchar();};}int m,mod,last,cnt;struct data{int l,r,mx;}tr[800005];void build(_){tr[k].l=x;tr[k].r=y;tr[k].mx=-INF;if(x==y)return;int mid=(x+y)>>1;build(k<<1,x,mid);build(k<<1|1,mid+1,y);}int ask(_){int l=tr[k].l,r=tr[k].r;if(l==x&&r==y)return tr[k].mx;int mid=(l+r)>>1;if(y<=mid)return ask(k<<1,x,y);else if(x>mid)return ask(k<<1|1,x,y);else return max(ask(k<<1,x,mid),ask(k<<1|1,mid+1,y));}void insert(_){int l=tr[k].l,r=tr[k].r;if(l==r){tr[k].mx=y;return;}int mid=(l+r)>>1;if(x<=mid)insert(k<<1,x,y);else insert(k<<1|1,x,y);tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);}int main(){m=read(),mod=read();build(1,1,m);R1(i,m){char ch[5];scanf(“%s”,ch);int x;if(ch[0]==’A’){cnt++;x=(read()+last)%mod;insert(1,cnt,x);}else{last=ask(1,cnt-read()+1,cnt);printf(“%d\n”,last);}}return 0;}树状数组;N=200005;int num[N], c[N], cnt;int getk(int l, int r) { int ret=num[r]; while(l<=r) {ret=max(ret, num[r]);for(–r; r-l>=lowbit(r); r-=lowbit(r))ret=max(ret, c[r]); } return ret;}int main() { int n, d, t=0, a; char ch[3]; scanf(“%d%d”, &n, &d); while(n–) {scanf(“%s%d”, ch, &a);if(ch[0]==’A’) {num[++cnt]=(t+a)%d;c[cnt]=max(getk(cnt-lowbit(cnt)+1, cnt-1), num[cnt]);}else {printf(“%d\n”, t=getk(cnt-a+1, cnt));} } return 0;}单调栈n,d,t;int top,len,a[200001],num[200001];int main(){int x;char ch[1];scanf(“%d%d”,&n,&d);while(n–){scanf(“%s%d”,ch,&x);if(ch[0]==’A’){x=(x+t)%d;num[++len]=x;while(top&&num[a[top]]<=x)top–;a[++top]=len;}else{int y=std::lower_bound(a+1,a+top+1,len-x+1)-a;t=num[a[y]];printf(“%d\n”,t=num[a[y]]);}}return 0;};const int maxn=200000;int stack[maxn],top=0;int F[maxn],A[maxn];int find(int x){if(F[x]==x) return x; return F[x]=find(F[x]);}void Union(int x,int y){F[y]=x;}int main(){int last=0,m,d,x,n=0;char c;scanf(“%d %d\n”,&m,&d);while(m–){scanf(“%c %d\n”,&c,&x);if(c==’Q’)x=(n-x),printf(“%d\n”,last=A[find(x)]);else{F[n]=n;A[n]=(last+x)%d;while(top&&A[stack[top-1]]<=A[n])Union(n,stack[top-1]),top–;stack[top++]=n++;}}}单调队列,d,a[200001],t,max[200001],l=0,p;char q[1];int main(){scanf(“%d%d”, &m, &d);while (m–){scanf(“%s%d”,q,&p);if(q[0]==’A’){a[++t]=(l+p)%d;for(int i=t;i;i–)if(max[i]<a[t])max[i]=a[t];else break;}else printf(“%d\n”,l=max[t-p+1]);}return 0;}
只有坚韧不拔向着目标奋进，成功后将在不远处等待着你的到来。
