51Nod 算法马拉松12 移数博弈

时间：2023-03-10 04:46:32
51Nod 算法马拉松12 移数博弈

点进去发现并不是博弈QAQ

一开始考虑单调队列什么乱七八糟的发现根本做不出来

(没错我一直在想枚举最大值求次大值QAQ

不妨换个思路：

我们考虑枚举次大值求最大值

设当前为now，

设now之前第一个比他大的数的位置为L1，L1之前第一个比他大的数的位置为L2

设now之后第一个比他大的数的位置为R1，R1之前第一个比他大的数的位置为R2

那么对于now而言，其作为次大值存在的区间

1、左端点在[L2+1，L1]之间，右端点在[now,R1-1]之间

2、左端点在[L1+1，now]之间，右端点在[R1,R2-1]之间

这也就是说我们可以O(1)的算每个位置的贡献

具体求L1，L2，R1，R2的做法如下：

我们先对于数据做一遍桶排序(注意相同的数位置越小优先级越高）

之后维护一个链表，从小到大枚举数，每枚举一个删掉一个

链表中的L1，L2，R1，R2就是上述的L1，L2，R1，R2

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=10000010;

const int mod=1000000007;

typedef long long LL;

int n,A,B,p;

int a[maxn],b[maxn];

int t[maxn];

int next[maxn],pre[maxn];

int L1,R1,L2,R2;

void del(int now){

    next[pre[now]]=next[now];

    pre[next[now]]=pre[now];

}

int main(){

    scanf("%d%d%d%d%d",&n,&a[0],&A,&B,&p);

    for(int i=1;i<=n;++i)a[i]=(1LL*A*a[i-1]+B)%p,t[a[i]]++;

    for(int i=1;i<p;++i)t[i]+=t[i-1];

    for(int i=n;i>=1;--i)b[t[a[i]]--]=i;

    for(int i=1;i<=n;++i)next[i]=i+1,pre[i]=i-1;

    pre[0]=0;next[n+1]=n+1;

    LL ans=0;

    for(int i=1;i<=n;++i){

        int now=b[i];

        L1=pre[now];R1=next[now];

        L2=pre[L1];R2=next[R1];

        ans=ans+1LL*a[L1]*a[now]%mod*(L1-L2)%mod*(R1-now)%mod;

        if(ans>=mod)ans-=mod;

        ans=ans+1LL*a[R1]*a[now]%mod*(R2-R1)%mod*(now-L1)%mod;

        if(ans>=mod)ans-=mod;

        del(now);

    }printf("%lld\n",ans);

    return 0;

}

　　

相关文章