单调双端队列beta

单调双端队列第二弹 :-)

题目链接

是2018年杭电多校的第三场 HDU6319

http://acm.hdu.edu.cn/showproblem.php?pid=6319

题解链接

https://acm.taifua.com/archives/hdu6319.html

看到这个区间长度为m的最值,的确是应该马上想到单调双端队列啊 :-|

我的代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;
const int maxn=1e7+70;
int T,n,m,k,P,Q,R,MOD,i,a[maxn],q[maxn],s,t;
ll A,B;

#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++)
char c;
namespace io {
    const int L=(1<<21)+1;
    char ibuf[L],*iS,*iT,obuf[L],*oS=obuf,*oT=obuf+L-1,c,st[55];int f,tp;
    inline char getc() {
        char tc=gc();
        while(tc==10)tc=gc();
        return tc;
    }
    inline void flush() {
        fwrite(obuf,1,oS-obuf,stdout);
        oS=obuf;
    }
    inline void putc(char x) { *oS++=x; if (oS==oT) flush(); }
    template<class I> inline void gi(I&x) {
        for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
        for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15); x*=f;
    }
    template<class I> inline void print(I x) {
        if (!x) putc('0');
        if (x<0) putc('-'),x=-x;
        while (x) st[++tp]=x%10+'0',x/=10;
        while (tp) putc(st[tp--]);
    }
    inline void gs(char*s, int&l) {
        for (c=gc();c<'a'||c>'z';c=gc());
        for (l=0;c<='z'&&c>='a';c=gc()) s[l++]=c;
        s[l]=0;
    }
    inline void ps(const char*s) { for (int i=0,n=strlen(s);i<n;i++) putc(s[i]); }
    struct IOFLUSHER{ ~IOFLUSHER() { flush(); } } _ioflusher_;
};
using io::getc;
using io::putc;
using io::gi;
using io::gs;
using io::ps;
using io::print;

int main()
{
   // freopen("data.in","r",stdin);

    //freopen("A.in","r",stdin);
    //freopen("data.out","w",stdout);
    gi(T);
    while(T--){
        gi(n);gi(m);gi(k);gi(P);gi(Q);gi(R);gi(MOD);
        for(int i=1;i<=k;i++) gi(a[i]);
        for(int i=k+1;i<=n;i++) a[i]=(1LL*P*a[i-1]+1LL*Q*i+R)%MOD;
        ll A=0,B=0;
        s=t=0;
        A=B=0;
        for(int i=n;i>=1;i--){
// 维护的是单调递减的单调双端队列
// 所以当队列中的元素<= 要放入的元素时,要进行pop_back()的操作
            while(s<t&&a[q[t-1]]<=a[i]) t--;
            q[t++]=i;

            if(i+m-1<=n){
               while(q[s]>=i+m) s++;
              // printf("%d %d %d\n",i,a[q[s]],t-s);
               A+=i^a[q[s]];
               B+=i^(t-s);
            }
          //  show();
        }
        printf("%lld %lld\n",A,B);
    }
    return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!