B: Sprinkler - ウクーニャたんお誕生日コンテスト | AtCoder
お誕生日おめでとうございます（こっそり）
問題概略
N個の数が並んでいる。連続した数を選択して、1減らす作業がM回できる。
ただし、0は選択できない
減らした数の合計最大値を求めよう
制約
- 1≤N≤105
- 1≤M≤1014
- 1≤Ai≤109
- i≠j ならば Ai≠Aj
- 入力は全て整数
解法
貪欲にやれば解ける(証明できない)
広い区間のものを優先的に選んで水をやりたい。
手順
1
区間の長さ、lとr、dec(前回区間における最小の数(初期化時は0とする。次の区間の数はそれだけ減る)をプライオリティキューに入れる。（区間の長さを元にソートさせる。また、取り出す時に区間の長さが同じならどっちを選んでもスコアは変わらない）
最小の数decはセグメント木で求める
2
キューから取り出す
3
渡された区間の最小の数 - dec(前回の最小値)回水を撒けるので、回数 * 長さをスコアに加算して、Mを回数分減らす(撒ける残り回数が少ない時に注意)
4
3の操作でAi≠Ajより区間は２つにしか分かれない。
２つの区間について、手順1にのっとってキューに追加する。
この時decの値は２つが分かれる前の区間の最小値であり、どちらも同じ数を入れることに注意
Mが0になるか、キューが空になるまで続ける おしまい
class SegmentTree
{
int[] originalData;
int[] mins;
long[] sums;
int N;
int INT_MAX = Integer.MAX_VALUE / 2;
SegmentTree(int[] nums)
{
originalData = nums.clone();
int n = nums.length;
N = Integer.highestOneBit(n-1) << 1;
mins = new int[N * 2];
sums = new long[N * 2];
for (int i = 0; i < mins.length; i++)
mins[i] = INT_MAX;
build();
}
public void build()
{
for (int i = 0; i < originalData.length; i++)
{
update(i, originalData[i]);
}
}
public void update(int i, int v)
{
i = N + i - 1;
mins[i] = v;
sums[i] = v;
while (i > 0)
{
i = (i - 1) / 2;
mins[i] = marge(mins[i * 2 + 1], mins[i * 2 + 2]);
sums[i] = sums[i * 2 + 1] + sums[i * 2 + 2];
}
}
public long querySum(int start, int end)
{
return querySum(start, end, 0, 0, N);
}
private long querySum(int a, int b, int k, int l, int r)
{
if (b <= l || r <= a) return 0;
if (a <= l && r <= b) return sums[k];
else
{
long lv = querySum(a, b, 2 * k + 1, l, (l + r) / 2);
long rv = querySum(a, b, 2 * k + 2, (l + r) / 2, r);
return lv + rv;
}
}
public int queryMin(int start, int end)
{
return queryMin(start, end, 0, 0, N);
}
private int queryMin(int a, int b, int k, int l, int r)
{
if (b <= l || r <= a) return INT_MAX;
if (a <= l && r <= b) return mins[k];
else
{
int lv = queryMin(a, b, 2 * k + 1, l, (l + r) / 2);
int rv = queryMin(a, b, 2 * k + 2, (l + r) / 2, r);
return marge(lv, rv);
}
}
public int marge(int l, int r)
{
return Math.min(l, r);
}
}
class Dis implements Comparable<Dis>
{
int l, r, size;
long dec ;
Dis(int a, int b, int s,long dec)
{
l = a;
r = b;
size = s;
this.dec = dec;
}
@Override
public boolean equals(Object o)
{
if (this == o) return true;
if (!(o instanceof Dis)) return false;
Dis p = (Dis) o;
return l == p.l && size == p.size;
}
@Override
public int hashCode()
{
return Objects.hash(l, size);
}
@Override
public int compareTo(Dis p)
{
return p.size - size;
}
}
public class Main
{
static StringBuilder sb = new StringBuilder();
static FastScanner sc = new FastScanner(System.in);
static int INF = 12345678;
static long LINF = 123456789123456789L;
static long MINF = -123456789123456789L;
static long MOD = 1000000007;
static int[] y4 = {0, 1, 0, -1};
static int[] x4 = {1, 0, -1, 0};
static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
static long[] F;
static boolean[] isPrime;
static int[] primes;
static char[][] map;
static int N;
static long M;
static int[] A;
public static void main(String[] args)
{
N = sc.nextInt();
M = sc.nextLong();
A = sc.nextIntArray(N);
HashMap<Integer,Integer> va_in = new HashMap<>();
for (int i = 0; i < N; i++)
{
va_in.put(A[i],i);
}
SegmentTree st = new SegmentTree(A);
PriorityQueue<Dis> que = new PriorityQueue<>();
que.add(new Dis(0, N, N,0));
long res = 0;
while (M > 0 && !que.isEmpty())
{
Dis dis = que.poll();
int l = dis.l;
int r = dis.r;
int size = dis.size;
if(size == 0)break;
long dec = dis.dec;
int ma = st.queryMin(l, r);
int mi = va_in.get(ma);
long kaisu = ma-dec;
if (M >= kaisu)
{
res += kaisu* size;
M -= kaisu;
}
else
{
res += M * size;
M = 0;
}
if(mi-l > 0)
que.add(new Dis(l, mi, mi - l, ma));
if(r- mi-1 > 0)
que.add(new Dis(mi + 1, r, r - mi - 1,ma));
}
System.out.println(res);
}
