【fjwc2015】k个串 kstring

2015年2月3日2,9434

【题目描述】

兔子们在玩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分

 

  • qwer2015年4月20日 上午10:50 回复

    求这题标算>_<

    #1  
    • hzwer2015年4月20日 上午10:52 回复
      admin

      我们对于每个位置i,维护以它为左端点的所有子串的和(注意这里的和均为重复的数字只统计一次),并令c 为其为左端点的子串和的最大值。
      对于全局最大的和,显然它是所有c 的最大值,不妨设为是c ,这时我们用j为左端点的所有子串中的次大值来更新c
      以上过程重复k次即可找出k大值。
      下面考虑如何维护c 。首先,我们令b 为[1, i]之间所有和,并以b 建立一棵线段树T。然后,我们发现,以2为右端点的子串所构成的线段树,就是T将[2, next )区间内所有数减a (next 表示a 在i之后下一次出现的位置),T中1位置赋为-inf的线段树,同理3,4…n为左端点的线段树,都可以由上一个修改而来。
      于是,可以使用可持久化线段树来维护他们,同时,删除最大值和查询最大值也可轻松实现。而所有c 的最大值,使用一个堆来维护就可以了。
      总的时间复杂度为O((n+k)lgn)

      #11
      • mazycode2015年6月16日 下午6:52 回复

        感觉不对啊,为什么重复那个操作K次就能找到K大值呢?第j-1个数如果是-1那么次大值不应该是以j-1为左端点的子串和么?= =

        #12
      • 杉崎键2015年11月18日 下午9:33 回复

        这是包括负数的情况吧?b[i]建树是以位置建树还是权值建树?

        #12