problem

luogu-link

solution

顯然單獨考慮每個 $i$ 的貢獻(xiàn)，即被多少個合法上升子序列包含。

令 $x=\max \{j|j>i\wedge a_j>a_i\}$，則包含 $i$ 的合法子序列的結(jié)尾元素最遠(yuǎn)只能到 $x?1$。

發(fā)現(xiàn)，重要的不是值本身，而是大小關(guān)系。所有可以離散化。從小到大標(biāo)號 $1～n$，權(quán)值小的放前面；權(quán)值相同下標(biāo)大的放前面。

下面的 $a$ 均表示離散化后的序列。

同時將合法上升子序列拆分成正著以 $i$ 結(jié)尾的上升子序列和倒著以 $i$ 結(jié)尾的下降子序列兩個部分，分別求出方案數(shù)后乘法原理即可。

$1～i$ 以 $i$ 結(jié)尾的上升子序列，在已經(jīng)離散化后，預(yù)處理就非常簡單了。樹狀數(shù)組維護(hù) $f_i:i$ 結(jié)尾的上升子序列個數(shù)。

然后考慮 $x?1～i$ 以 $i$ 結(jié)尾的下降子序列。

因為每個 $i$ 對應(yīng)的 $x$ 不一樣，不能像預(yù)處理一樣只掃描一遍整個 $1～n$，也不可能每次都去遍歷這個區(qū)間。

不妨考慮轉(zhuǎn)化成$n～i$ 以 $i$ 結(jié)尾的下降子序列個數(shù)減去以 $x$ 開頭以 $i$ 結(jié)尾的個數(shù)。

$n～i$ 以 $i$ 結(jié)尾的下降子序列個數(shù)，預(yù)處理方法同上。

最后就只剩下以 $x$ 開頭以 $i$ 結(jié)尾的下降子序列個數(shù)的計算了，開頭和結(jié)尾都已經(jīng)定了，是可做的。

設(shè) $y:a_y=\max \{a_j|x<j\le n\}$，即 $x$ 以后的后綴最大值的下標(biāo)。

必然有 $a_y<a_i<a_x$。

也就是說，當(dāng)我們利用棧維護(hù)出后綴最大值序列后，這個下降子序列的所有元素 $k$ 都滿足$a_y<a_k<a_x$。

那么，我們可以對于維護(hù)出來的后綴最大值上的每個節(jié)點開一個 $\text{vector}$。

把所有滿足上述限制的 $k$，全都掛在一個節(jié)點上。

暴力地按照預(yù)處理的計算方式，計算下降子序列個數(shù)。

因為每個 $i$ 只會掛在一個 $x$ 上面，所以時間復(fù)雜度是可以保證的。

code

#include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define int long long #define maxn 300005 vector < int > v[maxn]; int T, n, top; int id[maxn], t[maxn], a[maxn], f[maxn], g[maxn], h[maxn], s[maxn];void clear() { for( int i = 1;i <= n;i ++ ) t[i] = 0; } void Add( int i, int x ) { for( ;i <= n;i += i & -i ) ( t[i] += x ) %= mod; } int Ask( int i ) { int ans = 0; for( ;i;i -= i & -i ) ( ans += t[i] ) %= mod; return ans; }signed main() {scanf( "%lld", &T );while( T -- ) {top = 0; for( int i = 1;i <= n;i ++ ) v[i].clear();scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] ), id[i] = i;sort( id + 1, id + n + 1, []( int x, int y ) { return a[x] == a[y] ? x > y : a[x] < a[y]; } );for( int i = 1;i <= n;i ++ ) a[id[i]] = i; //離散化clear();for( int i = 1;i <= n;i ++ ) Add( a[i], f[i] = Ask( a[i] ) + 1 );//f[i]:1~i以i結(jié)尾的上升子序列個數(shù) //f[i]=1+\sum_{j=1}^{i-1}f[j](a_j<a_i)clear();for( int i = n;i;i -- ) Add( n - a[i] + 1, g[i] = Ask( n - a[i] + 1 ) + 1 );//g[i]:n~i以i結(jié)尾的下降子序列個數(shù)//g[i]=1+\sum_{j=n}^{i+1}g[j](a_j>a_i)for( int i = n;i;i -- ) if( a[i] > a[s[top]] ) s[++ top] = i;//后綴最大值的有用點for( int i = n;i;i -- ) { //必須倒序int l = 1, r = top, pos;while( l <= r ) {int mid = ( l + r ) >> 1;if( a[i] <= a[s[mid]] ) r = mid - 1, pos = mid;else l = mid + 1;}if( i ^ s[pos] ) v[pos].push_back( i );//將滿足a_{s[pos-1]}<a_i<a_{s[pos]}的i歸屬于s[pos]集合}for( int i = 1;i <= n;i ++ ) t[i] = 0;for( int i = 1;i <= top;i ++ ) {Add( n - a[s[i]] + 1, h[s[i]] = 1 );//h[k]:k~k隸屬的s[i] 以s[i]開始k結(jié)尾的下降子序列//h[k]=\sum_{j=k+1}^{s[i]}h[j](a_j>a_k)for( int k : v[i] ) Add( n - a[k] + 1, h[k] = Ask( n - a[k] + 1 ) );//所有下標(biāo)>k的j都已經(jīng)加入了 這也是為什么上面必須倒序儲存//相當(dāng)于clear() 但每次k數(shù)量很少 從1~n都清一遍浪費時間for( int k : v[i] ) Add( n - a[k] + 1, -h[k] );Add( n - a[s[i]] + 1, -1 );}int ans = 0;//g[i]-h[i]:合法的n~i以i結(jié)尾的下降子序列數(shù)量 f[i]:合法的1~i以i結(jié)尾的上升子序列數(shù)量for( int i = 1;i <= n;i ++ ) ( ans += ( g[i] - h[i] ) % mod * f[i] ) %= mod;printf( "%lld\n", ( ans + mod ) % mod );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1621G Weighted Increasing Subsequences（离散化+树状数组优化dp+栈维护后缀最大值+计数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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