曲靖企业网站/排名检测

参考链接：NOI Online2 提高组 子序列问题

• 在做hdu第7场的1012题时想到的类似题目，用线段树去解决区间平方和问题，但是那题我还没调好我的代码。

accode:

#define maxn 1000010
#define mod 1000000007
#define ll long long
int n, a[maxn], f[maxn], last[maxn];
int Next[maxn];
ll tr1[maxn], tr2[maxn];
ll change(int x,int y){for(int i=x;i<=n;i+=(i&-i))tr1[i]=(tr1[i]+y)%mod,tr2[i]=(tr2[i]+y*(x-1)+mod)%mod;}
ll sum(int x){ll re=0;for(int i=x;i>=1;i-=(i&-i))re=(re+tr1[i]*x%mod-tr2[i]+mod)%mod;return re;}
ll getsum(int x,int y){return (sum(y)-sum(x-1)+mod)%mod;};
struct disc{int x,y;};
bool compp(disc x,disc y){return x.x<y.x;}
void discretization(int *darr,int dn) {static disc b[maxn];for(int i=1;i<=dn;i++)b[i].x=darr[i],b[i].y=i;sort(b+1,b+dn+1,compp);static int tot=0;b[0].x=-9666;for(int i=1;i<=dn;i++)if(b[i].x!=b[i-1].x)darr[b[i].y]=++tot;else darr[b[i].y]=tot;
}
inline char cn() {static char buf[1000010],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
#define cn getchar
void read(int &x) {x=0;int f1=1;char ch=cn();while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
int main() {read(n);ll last_ans=0,ans=0;for(int i=1;i<=n;i++)read(a[i]);discretization(a,n);for(int i=1;i<=n;i++) {f[i]=f[i-1];if(!last[a[i]])f[i]++;else Next[last[a[i]]]=i;last[a[i]]=i;last_ans=(last_ans+1ll*f[i]*f[i]%mod)%mod;}ans=last_ans;for(int i=1;i<=n;i++) {if(!Next[i])Next[i]=n+1;change(i,f[i]-f[i-1]);}for(int i=1;i<=n;i++) {last_ans=(1ll*last_ans-((2*getsum(i,Next[i]-1)%mod-Next[i]+mod)+i)%mod+mod)%mod;ans=(ans+last_ans)%mod;change(i,-1);change(Next[i],1);}printf("%d",ans);
}