【UOJ UNR #1】争夺圣杯

时间：2023-02-05 15:43:46

来自FallDream的博客，未经允许，请勿转载，谢谢。

传送门

考虑直接对每个数字，统计它会产生的贡献。

单调栈求出每个数字左边第一个大等于他的数，右边第一个大于他的 （注意只能有一边取等）

假设左右两边分别有x1,x2个数，较大的是mx,较小的是mn

对于长度在(mx+1,mn+mx+1]的x，会产生mn+mx+1 - x - 1的贡献

对于长度在(mn,mx+1]的数，会产生 mn+1的贡献

对于长度在[1,mn]中的数x，会产生x的贡献。

差分维护即可

#include<iostream>

#include<cstdio>

#define MN 1000000

#define mod 998244353

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,a[MN+],s[MN+],g[MN+],top=,q[MN+],Lt[MN+],Rt[MN+],ans=;

inline void R(int&x,int y){x+=y;x>=mod?x-=mod:;}

int main()

{

    n=read();

    for(int i=;i<=n;++i) a[i]=read();

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

    {

        while(top&&a[i]>=a[q[top]]) --top;

        Lt[i]=q[top]+;q[++top]=i;

    }

    q[top=]=n+;

    for(int i=n;i;--i)

    {

        while(top&&a[i]>a[q[top]]) --top;

        Rt[i]=q[top]-;q[++top]=i;

    }

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

    {

        int mn=min(i-Lt[i],Rt[i]-i),y=mod-(a[i]%mod),mx=max(i-Lt[i],Rt[i]-i),z=a[i]%mod;

        if(mn>) R(s[],z),R(s[mn+],y);

        R(g[mn+],1LL*(mn+)*z%mod),R(g[mx+],1LL*(mod-mn-)*z%mod);

        R(g[mx+],1LL*(mn+mx+)*z%mod);R(s[mx+],y);

        R(g[mn+mx+],1LL*(mod-mn-mx-)*a[i]%mod);R(s[mn+mx+],z);

    }

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

    {

        R(g[i],g[i-]);R(s[i],s[i-]);

        ans^=(1LL*s[i]*i+g[i])%mod;

    }

    printf("%d\n",ans);

    return ;

}

相关文章