1012: [JSOI2008]最大数maxnumber

    xiaoxiao2021-03-26  5

    题目链接

    题目大意:维护序列,资磁向末尾插入一个数,查询末尾往前几个数的最大值,强制在线(雾

    题解:线段树和乱搞树状数组做法都显然是模板,我写了个比较科学的单调队列做法,代码量小到不知道哪里去了 由单调队列性质以下两点 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; }
    转载请注明原文地址: https://ju.6miu.com/read-650135.html

    最新回复(0)