题目概述

给出一个长度为 $n$ 的序列，求每个长度为 $m$ 的序列中的最大值以及最大值被更新的次数。

解题报告

最大值单调队列，更新次数可以这么搞：先预处理 $nxt[i]$ 表示 $i$ 后面第一个比 $i$ 大的位置，然后每次讨论一下删除上次区间第一个元素造成的影响就行了，由于每个位置只会被选和删除一次所以复杂度是正常的。

不过听说第二问倒着做更简单……

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=10000000;

int te,n,m,a[maxn+5],K,P,Q,R,MOD,que[maxn+5];
int nxt[maxn+5],ti,vis[maxn+5];LL A,B;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    for (readi(te);te;te--){
        readi(n);readi(m);readi(K);readi(P);readi(Q);readi(R);readi(MOD);
        for (int i=1;i<=K;i++) readi(a[i]);A=B=0;
        for (int i=K+1;i<=n;i++) a[i]=(LL)P*a[i-1]%MOD,AMOD(a[i],(LL)Q*i%MOD),AMOD(a[i],R);
        int Head=1,Tail=0;
        for (int i=1;i<m;i++){
            while (Head<=Tail&&que[Head]<=i-m) Head++;
            while (Head<=Tail&&a[que[Tail]]<=a[i]) Tail--;
            que[++Tail]=i;
        }
        for (int i=m;i<=n;i++){
            while (Head<=Tail&&que[Head]<=i-m) Head++;
            while (Head<=Tail&&a[que[Tail]]<=a[i]) Tail--;
            que[++Tail]=i;A+=a[que[Head]]^(i-m+1);
        }
        int top=0;que[top]=n+1;
        for (int i=n;i;i--){
            while (top&&a[que[top]]<=a[i]) top--;
            nxt[i]=que[top];que[++top]=i;
        }
        int lst=0,cnt=0;ti++;
        for (int i=1;i<=m;i++) if (a[i]>a[lst]) lst=i,cnt++,vis[i]=ti;B+=cnt^1;
        for (int i=m+1;i<=n;B+=cnt^i-m+1,i++){
            cnt-=vis[i-m]==ti;if (i-m==lst) lst=0;
            if (vis[i-m]==ti&&a[i-m]>=a[i-m+1]){
                int pos=i-m+1;if (!a[pos]) pos=nxt[pos];
                while (pos<=i&&vis[pos]<ti){
                    if (a[pos]>a[lst]) lst=pos;
                    cnt++,vis[pos]=ti,pos=nxt[pos];
                }
            }
            if (a[i]>a[lst]) lst=i,cnt++,vis[i]=ti;
        }
        printf("%lld %lld\n",A,B);
    }
    return 0;
}