Description

Input

Output

Sample Input

4

1 2 3 3

Sample Output

4

Data Constraint

對于30%的數據，N<=5000

對于100%的數據，N<=10^5

Solution

• 這題看上去有些熟悉，但卻無從下手……

• 在賽后，才猛然醒悟到——權值線段樹！

• 線段樹上維護一個值 a[i] ，以 a[i] 為結尾的上升子序列的方案數。

• 為了處理方便，可以將長度為 1 的也記進去。

• 那么 a[i] 顯然可以由 1~a[i] 的值推出，再加上自己一個獨立的，即：

  fai=1+∑j=1i?1faj

• 就等于在權值線段樹上查詢值為 [1,a[i]?1] 和即可，在用單點修改把結果賦到 a[i] 上。

• 那么這些每個位置的值都可以一次 O(NlogN) 推出（掃描+查詢）。

• 接著來統計答案，掃一遍，查詢當前 a[i] 的值，減一后累加進答案（把之前多算的減去）

• 然后將 a[i] 這個位置上的值用單點修改清零，避免重復計算。

• 所以總時間復雜度為 O(NlogN) 。

Code

#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int N=100001,mo=1e9+7; struct data {int x,y; }a[N]; int tot=1; LL ans,sum; LL f[N*4]; int b[N]; inline int read() {int data=0,w=1; char ch=0;while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') ch=getchar(),w=-1;while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data*w; } inline bool cmp(data a,data b) {return a.x<b.x; } inline void find(LL v,LL l,LL r,LL x,LL y) {if(l==x && r==y){ans=(ans+f[v])%mo;return;}int mid=(l+r)>>1;if(y<=mid) find(v*2,l,mid,x,y); elseif(x>mid) find(v*2+1,mid+1,r,x,y); else{find(v*2,l,mid,x,mid);find(v*2+1,mid+1,r,mid+1,y);} } inline void change(LL v,LL l,LL r,LL x,LL y) {if(l==r){f[v]=y;return;}int mid=(l+r)>>1;if(x<=mid) change(v*2,l,mid,x,y); else change(v*2+1,mid+1,r,x,y);f[v]=(f[v*2]+f[v*2+1])%mo; } int main() {int n=read();for(int i=1;i<=n;i++) a[a[i].y=i].x=read();sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(a[i].x!=a[i-1].x) tot++;b[a[i].y]=tot;}for(int i=1;i<=n;i++){ans=0;if(b[i]>1) find(1,1,tot,1,b[i]-1);change(1,1,tot,b[i],ans+1);}for(int i=1;i<=n;i++){ans=0;find(1,1,tot,b[i],b[i]);if(ans){sum=(sum+ans-1)%mo;change(1,1,tot,b[i],0);}}printf("%lld",sum);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3742. 【TJOI2014】上升子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。