bzoj 5055: 膜法师——树桩数组

#include<cstdio>
#include<cstring>
#include<algorithm>
const int M=1e6+7,mod=19260817;
char buf[11*M],*ptr=buf-1;
int read(){
    int ans=0,f=1,c=*++ptr;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=*++ptr;}
    while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=*++ptr;}
    return ans*f;
}
int n,k,ly,ans;
int s1[M],s2[M],v[M],x[M];
#define lowbit(x) x&-x
void ins(int x,int v,int w[]){while(x<=n) w[x]=(w[x]+v)%mod,x+=lowbit(x);}
int query(int x,int w[]){int sum=0; while(x) sum=(sum+w[x])%mod,x-=lowbit(x); return sum;}
int main(){
    fread(buf,1,sizeof(buf),stdin);
    n=read();
    for(int i=1;i<=n;i++) v[i]=read(),x[i]=v[i];
    std::sort(x+1,x+1+n);
    for(int i=1;i<=n;i++){
        k=std::lower_bound(x+1,x+1+n,v[i])-x;
        ly=query(k-1,s1); ins(k,v[i],s1);
        ans=(ans+1LL*v[i]*query(k-1,s2)%mod)%mod;
        ins(k,1LL*ly*v[i]%mod,s2);
    }printf("%d\n",ans);
    return 0;
}