写线段树的话太裸了,但是题意非常难搞,认真读题:其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。–>重新赋值
从题解上看到一种单调栈的写法觉得非常巧妙
利用了题目的特性:每次都是在最后询问,用单调栈维护,开两个栈一个保存下标,一个保存他的值,在插入的时候把栈中比这个值小的都弹出,查询时二分答案即可
线段树
//并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾 #include#include #include using namespace std; const int maxn=1e6; const int inf=1e9; int n,mod,last; char opt[10]; struct Node{ int mx; }tree[maxn<<1|1]; void pushup(int rt) { tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx); } void change(int x,int C,int l,int r,int rt) { if (l==r) {tree[rt].mx+=C; return;} int mid=(l+r)>>1; if (x<=mid) change(x,C,l,mid,rt<<1); else change(x,C,mid+1,r,rt<<1|1); pushup(rt); } int ques(int L,int R,int l,int r,int rt) { if (L<=l && r<=R) return tree[rt].mx; int mid=(l+r)>>1; int ans=0; if (L<=mid) ans=max(ans,ques(L,R,l,mid,rt<<1)); if (R>mid) ans=max(ans,ques(L,R,mid+1,r,rt<<1|1)); return ans; } int main() { int sz=0; scanf("%d%d",&n,&mod); for (int i=1; i<=n; i++) { scanf("%s",opt); int x; scanf("%d",&x); if (opt[0]=='A') change(++sz,(x+last)%mod,1,n,1); else { if (!x) {printf("0\n"); continue;} last=ques(sz-x+1,sz,1,n,1); printf("%d\n",last); } } return 0; }
单调栈
#include#include #include using namespace std; const int maxn=1e6; const int inf=1e9; int n,mod,zhan[maxn][2],top,last,sz; char opt[10]; void change(int x) { while (x>zhan[top][1]&&top>0) top--; zhan[++top][0]=++sz; zhan[top][1]=x; } int ques(int x,int l,int r) { while (l >1; if (x>zhan[mid][0]) l=mid+1; else r=mid; } return zhan[l][1]; } int main() { scanf("%d%d",&n,&mod); for (int i=1; i<=n; i++) { scanf("%s",opt); int x; scanf("%d",&x); if (opt[0]=='A') change((x+last)%mod); else { if (!x) {printf("0\n"); continue;} last=ques(sz-x+1,1,top); printf("%d\n",last); } } return 0; }