牛客挑战赛64 D_牛客博客

大家好这里是赛时调不出代码的小丑 myee。

这里我给出 T4 一个理论线性但肯定没人会去写的垃圾做法。

当然，如果你懒了，可以和我一样带只 $\log$ ，反正也能过。

首先容斥，贡献为

\sum_{l=1}^n\sum_{r=l+1}^n[f(l,r)=a_l\lor f(l,r)=a_r]\max_{l\le i\le r}a_i \\=\sum_{l=1}^n\sum_{r=l+1}^n[f(l,r)=a_l]\max_{l\le i\le r}a_i\\ +\sum_{l=1}^n\sum_{r=l+1}^n[f(l,r)=a_r]\max_{l\le i\le r}a_i\\ -\sum_{l=1}^n\sum_{r=l+1}^n[f(l,r)=a_l=a_r]\max_{l\le i\le r}a_i

容易发现前两部分形式类似，于是我们考虑如何计算第一部分。

按 $l$ 递减序枚举，维护出 $a_{p}$ 的单调栈，然后还要支持合并两个区间的操作，于是用链表实现。

这么说很模糊，因此我们给出代码示例：

    for(uint i=n-1;~i;i--){
        modint&w=W[i]=A[i];
        End[i]=R[i]=i,Nxt[i]=i+1;
        while(R[i]!=n-1&&(A[i]&A[R[i]+1])==A[i]){
            w+=W[R[i]+1];
            uint&e=End[i];uint&p=Nxt[e];
            while(A[e]>A[p]&&p<=R[R[i]+1])
                w+=modint(Nxt[p]-p)*(A[e]-A[p]),p=Nxt[p];
            if(p<=R[R[i]+1])e=End[R[i]+1];
            R[i]=R[R[i]+1];
        }
        ans+=w;
    }

注意这个会把 $l = r$ 的答案算入，要除去。

然后第二部分贡献我们翻转一下区间即可同理解决。

容易用均摊分析证明这两部分复杂度都是 $\Theta(n)$ 的。

然后考虑第三部分。

我们注意到，如果 $a_{i} = a_{j} = a_{k}, i < j < k$ ，且 $i, j$ 与 $j, k$ 之间都满足 $f (l, r) = a_{l} = a_{r}$ ，我们总有对 $i, k$ 间也满足。

一般的，若前面链表部分的 $R_l\ge r$ ，则两者属于同一等价类。

对于一个等价类内的答案，我们考虑先写一个 ST 表/四毛子，找到相邻两个区间最值，然后建笛卡尔树，暴力计算，即可。

这部分复杂度若实现 $\Theta(n)$ 找等价类，则可以通过四毛子实现严格 $\Theta(n)$ 。然后这个找等价类的过程显然可以哈希表维护。

于是总复杂度实现了 $\Theta(n)$ 。

但是肯定没人这么写，我是直接 map 套 vector，然后写 ST 表了，建树也没写线性。

复杂度于是变成 $O(n\log n)$ 。但是还是能过的。

以下是代码。

#include <algorithm>
#include <map>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace ConstMod
{
    template<const ullt p>
    class mod_ullt
    {
        private:
            ullt v;
            inline ullt chg(ullt w){return(w<p)?w:w-p;}
            inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
        public:
            mod_ullt():v(0){}
            mod_ullt(ullt v):v(v%p){}
            bol empty(){return!v;}
            inline ullt val(){return v;}
            friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}
            friend bol operator>(mod_ullt a,mod_ullt b){return a.v>b.v;}
            friend bol operator<=(mod_ullt a,mod_ullt b){return a.v<=b.v;}
            friend bol operator>=(mod_ullt a,mod_ullt b){return a.v>=b.v;}
            friend bol operator==(mod_ullt a,mod_ullt b){return a.v==b.v;}
            friend bol operator!=(mod_ullt a,mod_ullt b){return a.v!=b.v;}
            inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a.v+b.v);}
            inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a._chg(a.v+a.chg(p-b.v));}
            inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a.v*b.v;}
            friend mod_ullt operator/(mod_ullt a,mod_ullt b){return b._power(p-2)*a.v;}
            friend mod_ullt operator^(mod_ullt a,ullt b){return a._power(b);}
            inline mod_ullt operator-(){return _chg(p-v);}
            mod_ullt sqrt()
            {
                if(power(v,(p-1)>>1,p)!=1)return 0;
                mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);
                ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
                mod_ullt x=_power((t+1)>>1),e=_power(t);
                while(k<s)
                {
                    if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
                    e=_power(p-2)*x*x,k++;
                }
                return _min(x,-x),x;
            }
            mod_ullt inv(){return _power(p-2);}
            mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
            voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');v%=p;}
            voi print()
            {
                static chr C[20];uint tp=0;
                ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
                while(tp--)putchar(C[tp]);
            }
            voi println(){print(),putchar('\n');}
            mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
        public:
            inline ullt&operator()(){return v;}
            inline mod_ullt&operator+=(mod_ullt b){return*this=_chg(v+b.v);}
            inline mod_ullt&operator-=(mod_ullt b){return*this=_chg(v+chg(p-b.v));}
            inline mod_ullt&operator*=(mod_ullt b){return*this=v*b.v;}
            mod_ullt&operator^=(ullt b){return*this=_power(b);}
            mod_ullt&operator/=(mod_ullt b){return*this=b._power(p-2)*v;}
            mod_ullt&operator++(){return v=chg(v+1),*this;}
    };
}
const ullt Mod=998244353,g=3;
typedef ConstMod::mod_ullt<Mod>modint;
struct ST
{
    std::vector<uint>Log2;
    std::vector<std::pair<uint,uint> >Val[21];
    voi build(uint*A,uint n){
        Val[0].resize(n);for(uint i=0;i<n;i++)Val[0][i]={A[i],i};
        Log2.resize(n+1);Log2[0]=-1;for(uint i=1;i<=n;i++)Log2[i]=Log2[i>>1]+1;
        for(uint dep=1;dep<=Log2[n];dep++){
            Val[dep].resize(n-(1u<<dep)+1);
            for(uint i=0;i+(1u<<dep)<=n;i++)
                Val[dep][i]=std::max(Val[dep-1][i],Val[dep-1][i+(1u<<(dep-1))]);
        }
    }
    voi build(std::vector<uint>A){
        uint n=A.size();
        Val[0].resize(n);for(uint i=0;i<n;i++)Val[0][i]={A[i],i};
        Log2.resize(n+1);Log2[0]=-1;for(uint i=1;i<=n;i++)Log2[i]=Log2[i>>1]+1;
        for(uint dep=1;dep<=Log2[n];dep++){
            Val[dep].resize(n-(1u<<dep)+1);
            for(uint i=0;i+(1u<<dep)<=n;i++)
                Val[dep][i]=std::max(Val[dep-1][i],Val[dep-1][i+(1u<<(dep-1))]);
        }
    }
    std::pair<uint,uint>find(uint l,uint r){
        return std::max(Val[Log2[r-l]][l],Val[Log2[r-l]][r-(1u<<Log2[r-l])]);
    }
}S,SMain;
modint dfs(uint l,uint r,std::vector<uint>&V){
    if(l>=r)return 0;
    uint p=S.find(l,r).second;
    return modint(r-p)*(p-l+1)*V[p]+dfs(l,p,V)+dfs(p+1,r,V);
}
modint get(std::vector<uint>&V){
    if(V.empty())return 0;
    S.build(V);return dfs(0,V.size(),V);
}
modint W[500005];
uint Nxt[500005],End[500005],A[500005],R[500005];
std::map<uint,std::vector<uint> >M;
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    modint ans=0;
    uint n;scanf("%u",&n);for(uint i=0;i<n;i++)scanf("%u",A+i),ans-=A[i]*2;
    for(uint i=n-1;~i;i--){
        modint&w=W[i]=A[i];
        End[i]=R[i]=i,Nxt[i]=i+1;
        while(R[i]!=n-1&&(A[i]&A[R[i]+1])==A[i]){
            w+=W[R[i]+1];
            uint&e=End[i];uint&p=Nxt[e];
            while(A[e]>A[p]&&p<=R[R[i]+1])
                w+=modint(Nxt[p]-p)*(A[e]-A[p]),p=Nxt[p];
            if(p<=R[R[i]+1])e=End[R[i]+1];
            R[i]=R[R[i]+1];
        }
        ans+=w;
    }
    // ans.println();
    std::reverse(A,A+n);
    for(uint i=n-1;~i;i--){
        modint&w=W[i]=A[i];
        End[i]=R[i]=i,Nxt[i]=i+1;
        while(R[i]!=n-1&&(A[i]&A[R[i]+1])==A[i]){
            w+=W[R[i]+1];
            uint&e=End[i];uint&p=Nxt[e];
            while(A[e]>A[p]&&p<=R[R[i]+1])
                w+=modint(Nxt[p]-p)*(A[e]-A[p]),p=Nxt[p];
            if(p<=R[R[i]+1])e=End[R[i]+1];
            R[i]=R[R[i]+1];
        }
        ans+=w;
    }
    // ans.println();
    for(uint i=0;i<n;i++)M[A[i]].push_back(i);
    SMain.build(A,n);
    for(auto v:M){
        auto V=v.second;
        for(uint l=0,r;l<V.size();l=r){
            std::vector<uint>W;
            r=l+1;
            while(r<V.size()&&R[V[l]]>=V[r]){
                W.push_back(SMain.find(V[r-1],V[r]).first);
                r++;
            }
            ans-=get(W);
        }
    }
    ans.println();
    return 0;
}