「fjWC2015」k个串 kstring

2015年2月3日6,3004

「题目描述」

兔子们在玩k个串的游戏。首先,它们拿出了一个长度为n的数字序列,选出其中的一个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次)。

兔子们想知道,在这个数字序列所有连续的子串中,按照以上方式统计其所有数字之和,第k大的和是多少。

「输入格式」

第一行,两个整数n和k,分别表示长度为n的数字序列和想要统计的第k大的和

接下里一行n个数a_i,表示这个数字序列

「输出格式」

一行一个整数,表示第k大的和

「样例输入」

7 5

3 -2 1 2 2 1 3 -2

「样例输出」

4

「数据范围」

对于20%的数据,1 <= n <= 2000

对于另外20%的数据,0 <= a_i <= 10^9

对于100%的数据,1 <= n <= 100000, 1 <= k <= 200000, 0 <= |a_i| <= 10^9

数据保证存在第k大的和

题解

我竟然写了个40分T T

前20的暴力随便map+sort水过

对于全是正数的情况,若固定右端点,则左端点等于1时一定最大

将1- i (1<=i<=n) 的值放入堆

每次从堆中取出最大值,若其区间为 l ~ r  ,加入 l+1 ~ r,重复此操作K次

查询一个区间不重复值的权值和,只要记录每个数下次出现的位置nxt[x],然后将nxt[x]和v[x]放进主席树里就可以解决了

复杂度n(logn)^2

40分

 

avatar
1 Comment threads
3 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
hzwerqwer Recent comment authors
  Subscribe  
提醒
qwer
qwer

求这题标算>_<