absi2011's Blog & Daily Life.

全新的开始　　　　　　　我要省选翻盘　　　　　　　I wanna AK in 高考\化学　　　　　　　自此,生无可恋

173712

[破碎的状态] 101630G

没错还是这一场比赛,我好像和它杠上了

迟到一天的题解

题意:

你正在修城墙

一开始,所有城墙等级为1级

你可以指定两个长度为r的区间,让这两个区间的城墙各升1级

之后,你需要支付以下价格:

对于第i块城墙,1级城墙的价格为ai,2级为bi,3级为ci

保证1<=ai<bi<ci<=1e6,保证n<=30000,1<=r<n

那么你一共有(n-r)*(n-r+1)/2

求第k小的价格