电商型网站开发多少钱,毕业设计网站前端代做,长沙网站设计培训机构,做封面的免费网站4504. K个串descriptionsolutioncodedescription
兔子们在玩k个串的游戏。首先#xff0c;它们拿出了一个长度为n的数字序列#xff0c;选出其中的一
个连续子串#xff0c;然后统计其子串中所有数字之和#xff08;注意这里重复出现的数字只被统计一次#xff09;。
兔…
4504. K个串descriptionsolutioncodedescription
兔子们在玩k个串的游戏。首先它们拿出了一个长度为n的数字序列选出其中的一
个连续子串然后统计其子串中所有数字之和注意这里重复出现的数字只被统计一次。
兔子们想知道在这个数字序列所有连续的子串中按照以上方式统计其所有数字之和第
k大的和是多少。
Input
第一行两个整数n和k分别表示长度为n的数字序列和想要统计的第k大的和
接下里一行n个数a_i表示这个数字序列
Output
一行一个整数表示第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数据保证存在第 k 大的和
solution
一个[l,r][l,r][l,r]的子串的和定义为不同数的和一个数多次出现只算一次
可以联想到Rmq Problem / mex的处理
以每个iii为子串右端点rrr建立一个新版本的主席树
每个版本的叶子结点的值就是该点做左端点时这个子串的和
先继承上一个i−1i-1i−1版本
再记录上一次该值的出现位置lstilst_ilsti那么aia_iai只会对(lsti,i](lst_i,i](lsti,i]内的数产生aia_iai贡献
唯一不同的是这里的修改是对一段区间的修改为了线段树的复杂度正确必须使用懒标记
而主席树的懒标记因为某些节点的共用后面版本的懒标记下传可能会影响前面版本的答案
所以每个新版本的懒标记下放的时候都需要复制原点在新点上操作
问题不是求最大而是第KKK大
这又联想到[NOI]超级钢琴从最佳点进行左右区间切割的处理
先往有先队列里面丢每个版本最大值ans以及最大值选取的左端点位置pos还要记录是哪个版本线段树i以及可选取为左端点的区间l,r
当取出当前的最大值(ans,i,l,r,pos)
就会分裂成两个区间(*,i,l,pos-1,*) (*,i,pos1,r,*)
*需要对该版本的线段树进行查询查询区间内的最大值及最大值位置
code
调懒标记的问题调麻了
#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;
}
