【BZOJ3110】【ZJOI2013】K大数查询

显然可以用整体二分做

不过这道题由于是区间修改所以要用线段树

线段树太慢啦!还是用树状数组!

区间修改区间查询的树状数组:令s[i]表示[i,n]的共同增量

那么显然每次修改可以变成修改两个s[i]值

关键在于怎么求前i项的和ask(i):

$$ask(i)=(i+1)\sum_{i\in [1,i]}s[i]-\sum_{i\in [1,i]}i\times s[i]$$

那么用两个树状数组维护s[i]和i*s[i]的前缀和就可以啦!

另外本题数据中c都是正整数。。

负数有是有,只不过答案都是正整数。。

不过听说可以树套树。。

没写过树套树。。还是要尝试一下

大概就是维护一个二分结构,然后每个位置存一棵线段树

当然这个线段树要动态开结点不然空间吃不消。。

跑的慢成狗。。整体二分不到2s这个要18s。。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz