正題

題目鏈接:https://www.luogu.com.cn/problem/P6477
話說這是luogu的冥間數(shù)據(jù)

---

題目大意

$n$個數(shù)的序列，$f(l,r)$表示$l～r$有多少個不同的數(shù)字。

求$$\sum _{l=1}^n\sum _{r=l}^n(f(l,r){)}^2$$

---

解題思路

考慮多一個數(shù)字會多出$2n+1$(n表示原來數(shù)字個數(shù))。

線段樹維護$f(1～i?1,i)$的和，然后每個數(shù)字能影響的范圍是i到上一個和它相同的數(shù)字的后一個位置處，我們修改這部分的數(shù)據(jù)然后每次統(tǒng)計答案即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #define lowbit(x) (x&-x) #define siz(x) (t[x].r-t[x].l+1) #define k(x) (((x)>XJQ)?((x)-XJQ):(x)) #define ll long long using namespace std; const ll N=1e6+10,XJQ=1e9+7; ll n,ans,answer; ll a[N],b[N],last[N],v[N]; ll read() {ll x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } struct Seq_Tree{struct Tree_node{ll l,r,val,lazy;}t[N*4];void Build(ll x,ll l,ll r){t[x].l=l;t[x].r=r;if(l==r)return;ll mid=(l+r)>>1;Build(x*2,l,mid);Build(x*2+1,mid+1,r);return;}void DownData(ll x){if(!t[x].lazy)return;(t[x*2].lazy+=t[x].lazy)%=XJQ;(t[x*2+1].lazy+=t[x].lazy)%=XJQ;(t[x*2].val+=t[x].lazy*siz(x*2))%=XJQ;(t[x*2+1].val+=t[x].lazy*siz(x*2+1))%=XJQ;t[x].lazy=0;return;}void Change(ll x,ll l,ll r,ll val){if(t[x].l==l&&t[x].r==r){(t[x].lazy+=val)%=XJQ;(t[x].val+=val*siz(x))%=XJQ;return;}DownData(x);ll mid=(t[x].l+t[x].r)>>1;if(r<=mid) Change(x*2,l,r,val);else if(l>mid) Change(x*2+1,l,r,val);else Change(x*2,l,mid,val),Change(x*2+1,mid+1,r,val);t[x].val=(t[x*2].val+t[x*2+1].val)%XJQ;return;}ll Ask(ll x,ll l,ll r){if(t[x].l==l&&t[x].r==r)return t[x].val;DownData(x);ll mid=(t[x].l+t[x].r)>>1;if(r<=mid) return Ask(x*2,l,r);if(l>mid) return Ask(x*2+1,l,r);return (Ask(x*2,l,mid)+Ask(x*2+1,mid+1,r))%XJQ;} }T; int main() {n=read();for(ll i=1;i<=n;i++)a[i]=b[i]=read();sort(b+1,b+1+n);ll m=unique(b+1,b+1+n)-b-1;for(ll i=1;i<=n;i++){a[i]=lower_bound(b+1,b+1+m,a[i])-b;last[i]=v[a[i]];v[a[i]]=i;}T.Build(1,1,n);T.Change(1,1,1,1);ans=answer=1;for(ll i=2;i<=n;i++){(ans+=2*T.Ask(1,last[i]+1,i)+i-last[i])%=XJQ;T.Change(1,last[i]+1,i,1);(answer+=ans)%=XJQ;}printf("%lld",answer); }

總結(jié)

以上是生活随笔為你收集整理的P6477-[NOI Online #2 提高组]子序列问题【线段树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。