uoj213 【UNR #1】争夺圣杯

╰半夏微凉° 2023-10-11 04:51 18阅读 0赞

[题目][Link 1]

设\\(f\_i\\)表示所有长度为\\(i\\)的区间的最大值的和，求\\(\\bigoplus \\sum\_\{i=1\}^nf\_i\\)

不难发现随机数据非常好做

由于一个随机序列的前缀最大值期望只会变化\\(\\log\\)次，所以完全可以从这个条件上入手

考虑维护一个合并式单调栈，每次插入一个数之后，单调栈中存在的都是当前这个前缀所有的后缀最大值，我们直接暴力扫一遍这些后缀最大值，于是有一些针对\\(f\\)数组的区间加，我们直接差分维护就好了

这样在数据随机意义下是\\(O(n\\log n)\\)的，一发跑过了除了\\(\\rm hack\\)数据以外的所有数据也是非常惊人

考虑正解，使用单调栈找到一个位置\\(i\\)左边第一个小于等于他的\\(j\\)，和右边第一个大于他的\\(k\\)，显然在左端点在\\(\[j,i\]\\)内，右端点在\\(\[i,k)\\)的区间的最大值都是\\(a\_i\\)，于是直接讨论一下\\(a\_i\\)对这些长度区间的贡献就好了

设\\(a=\\min(i-j+1,k-i),b=\\max(i-j+1,k-i)\\)

对于长度为\\(\[1,a\]\\)的区间，贡献是\\(x\\times a\_i\\)

对于长度为\\(\[a+1,b\]\\)的区间，贡献是\\(b\\times a\_i\\)

对于长度为\\(\[b+1,a+b-1\]\\)的区间，贡献为\\((b-x)\\times a\_i=b\\times a\_i-x\\times a\_i\\)

维护两个差分数组，一个用于维护这个位置实际上增加了多少，一个用于维护这个位置增加了多少倍的\\(x\\)

随便就做完了，复杂度是\\(O(n)\\)的

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int mod=998244353;
    const int maxn=1e6+5;
    int a[maxn],pre[maxn],mn[maxn],t[maxn],st[maxn],c[maxn];
    int n,top;LL ans;
    inline void calc(int pos) {
        int a=t[top]-mn[top]+1,b=pos-t[top]+1;
        if(a>b) std::swap(a,b);
        int v=st[top]%mod;
        if(a<b) {
            pre[a+1]=(pre[a+1]+1ll*a*v%mod)%mod;
            pre[b+1]=(pre[b+1]-1ll*a*v%mod+mod)%mod;
        }
        c[1]=(c[1]+v)%mod,c[a+1]=(c[a+1]-v+mod)%mod;
        if(b<a+b-1) {
            c[b+1]=(c[b+1]-v+mod)%mod,c[a+b]=(c[a+b]+v)%mod;
            pre[b+1]=(pre[b+1]+1ll*(a+b)*v%mod)%mod;
            pre[a+b]=(pre[a+b]-1ll*(a+b)*v%mod+mod)%mod;
        }
    }
    int main() {
        n=read();for(re int i=1;i<=n;++i) a[i]=read();top=0;
        for(re int i=1;i<=n;i++) {
            int now=i;
            while(top&&a[i]>=st[top]) calc(i-1),now=mn[top],top--;
            mn[++top]=now,t[top]=i,st[top]=a[i];
        }
        while(top) calc(n),top--;
        for(re int i=1;i<=n;i++) pre[i]=(pre[i-1]+pre[i])%mod;
        for(re int i=1;i<=n;i++) c[i]=(c[i-1]+c[i])%mod;
        for(re int i=1;i<=n;i++) 
            pre[i]=(pre[i]+1ll*c[i]*i%mod)%mod,ans^=pre[i];
        printf("%lld\n",ans);
    }

转载于:https://www.cnblogs.com/asuldb/p/11414455.html

[Link 1]: http://uoj.ac/problem/213