4504. K個串

• description
• solution
• code

description

兔子們在玩k個串的游戲。首先，它們拿出了一個長度為n的數(shù)字序列，選出其中的一

個連續(xù)子串，然后統(tǒng)計其子串中所有數(shù)字之和（注意這里重復(fù)出現(xiàn)的數(shù)字只被統(tǒng)計一次）。

兔子們想知道，在這個數(shù)字序列所有連續(xù)的子串中，按照以上方式統(tǒng)計其所有數(shù)字之和，第

k大的和是多少。

Input

第一行，兩個整數(shù)n和k，分別表示長度為n的數(shù)字序列和想要統(tǒng)計的第k大的和

接下里一行n個數(shù)a_i，表示這個數(shù)字序列

Output

一行一個整數(shù)，表示第k大的和

Sample Input

7 5
3 -2 1 2 2 1 3 -2

Sample Output

4

Hint

1 <= n <= 100000, 1 <= k <= 200000, 0 <= |a_i| <= 10^9數(shù)據(jù)保證存在第 k 大的和

solution

一個$[l,r]$的子串的和定義為不同數(shù)的和，一個數(shù)多次出現(xiàn)只算一次

可以聯(lián)想到Rmq Problem / mex的處理

以每個$i$為子串右端點$r$建立一個新版本的主席樹

每個版本的葉子結(jié)點的值就是該點做左端點時，這個子串的和

先繼承上一個$i?1$版本

再記錄上一次該值的出現(xiàn)位置$ls{t}_i$，那么$a_i$只會對$(ls{t}_i,i]$內(nèi)的數(shù)產(chǎn)生$a_i$貢獻(xiàn)

唯一不同的是，這里的修改是對一段區(qū)間的修改，為了線段樹的復(fù)雜度正確必須使用懶標(biāo)記

而主席樹的懶標(biāo)記，因為某些節(jié)點的共用，后面版本的懶標(biāo)記下傳可能會影響前面版本的答案

所以，每個新版本的懶標(biāo)記下放的時候都需要復(fù)制原點，在新點上操作

問題不是求最大，而是第$K$大

這又聯(lián)想到[NOI]超級鋼琴從最佳點進(jìn)行左右區(qū)間切割的處理

先往有先隊列里面丟每個版本最大值ans，以及最大值選取的左端點位置pos，還要記錄是哪個版本線段樹i，以及可選取為左端點的區(qū)間l,r

當(dāng)取出當(dāng)前的最大值(ans,i,l,r,pos)

就會分裂成兩個區(qū)間(*,i,l,pos-1,*) (*,i,pos+1,r,*)

*需要對該版本的線段樹進(jìn)行查詢，查詢區(qū)間內(nèi)的最大值及最大值位置

code

調(diào)懶標(biāo)記的問題，調(diào)麻了

#include <map> #include <queue> #include <cstdio> #include <iostream> using namespace std; #define Pair pair < int, int > #define int long long #define maxn 100005 map < int, int > mp; struct Node { int ans, i, l, r, pos;bool operator < ( const Node &t ) const {return ans < t.ans;} }; priority_queue < Node > q; struct node { int lson, rson, Max, tag, pos; }t[maxn * 160]; int n, k, cnt; int lst[maxn], a[maxn], root[maxn];void pushup( int now ) {if( t[t[now].lson].Max > t[t[now].rson].Max ) t[now].Max = t[t[now].lson].Max, t[now].pos = t[t[now].lson].pos;elset[now].Max = t[t[now].rson].Max, t[now].pos = t[t[now].rson].pos; }void pushdown( int now ) {if( ! t[now].tag ) return;node lson = t[t[now].lson];node rson = t[t[now].rson];t[t[now].lson = ++ cnt] = lson;t[t[now].rson = ++ cnt] = rson; t[t[now].lson].Max += t[now].tag;t[t[now].lson].tag += t[now].tag;t[t[now].rson].Max += t[now].tag;t[t[now].rson].tag += t[now].tag;t[now].tag = 0; }void build( int &now, int l, int r ) {now = ++ cnt;if( l == r ) { t[now].Max = 0, t[now].pos = l; return; }int mid = ( l + r ) >> 1;build( t[now].lson, l, mid );build( t[now].rson, mid + 1, r );pushup( now ); }void modify( int &now, int lst, int l, int r, int L, int R, int val ) {if( r < L or R < l ) return;if( L <= l and r <= R ) {t[now = ++ cnt] = t[lst];t[now].Max += val;t[now].tag += val;return;}pushdown( lst );t[now = ++ cnt] = t[lst];int mid = ( l + r ) >> 1;modify( t[now].lson, t[lst].lson, l, mid, L, R, val );modify( t[now].rson, t[lst].rson, mid + 1, r, L, R, val );pushup( now ); }Pair query( int now, int l, int r, int L, int R ) {if( r < L or R < l ) return make_pair( -1e18, 0 );if( L <= l and r <= R ) return make_pair( t[now].Max, t[now].pos );pushdown( now );int mid = ( l + r ) >> 1;Pair lson = query( t[now].lson, l, mid, L, R );Pair rson = query( t[now].rson, mid + 1, r, L, R );return max( lson, rson ); }signed main() {scanf( "%lld %lld", &n, &k );for( int i = 1;i <= n;i ++ ) {scanf( "%lld", &a[i] );if( mp[a[i]] ) lst[i] = mp[a[i]];mp[a[i]] = i;}build( root[0], 1, n );for( int i = 1;i <= n;i ++ ) {modify( root[i], root[i - 1], 1, n, lst[i] + 1, i, a[i] );Pair it = query( root[i], 1, n, 1, i );q.push( { it.first, i, 1, i, it.second } );}int ans, pos, l, r, i; Pair it;while( k -- ) {Node now = q.top(); q.pop();ans = now.ans, pos = now.pos, i = now.i, l = now.l, r = now.r;if( pos ^ l ) {it = query( root[i], 1, n, l, pos - 1 );q.push( { it.first, i, l, pos - 1, it.second } );}if( pos ^ r ) {it = query( root[i], 1, n, pos + 1, r );q.push( { it.first, i, pos + 1, r, it.second } );}}printf( "%lld\n", ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ4504. K个串（主席树+优先队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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