题目链接
题目大意：维护序列，资磁向末尾插入一个数，查询末尾往前几个数的最大值，强制在线(雾
题解：线段树和乱搞树状数组做法都显然是模板，我写了个比较科学的单调队列做法，代码量小到不知道哪里去了 由单调队列性质以下两点 1.如果一个节点在队列中既没有时间优势也没有值优势，那么显然无论在怎样的情况下都不会被选为最大值。 只在末尾选，可以满足以上的条件。 2.如果想要对这个数组进行二分查找满足条件的最大值，要求数组的值单调。 单调队列正好将以上两者完美的结合在一起。 维护一个单调递减队列，查询的时候二分就可以了
我的收获：单调队列大法吼啊
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define M 200005 int n,t,d,x,l,w,pos; int c[M],q[M]; inline void push(int s){ c[++l]=s; while(w&&c[q[w]]<s) w--; q[++w]=l; } void work() { char opt[5]; for(int i=1;i<=n;i++){ scanf("%s%d",opt,&x); if(opt[0]=='A') x=(t+x)%d,push(x); else pos=upper_bound(q+1,q+w+1,l-x)-q,printf("%d\n",t=c[q[pos]]); } } void init(){ scanf("%d%d",&n,&d); } int main() { init(); work(); return 0; }