Codeforces Round #381 (Div. 2) E. Alyona and towers
問題
http://codeforces.com/contest/740/problem/E
N 個の非負の数列{a}があります。クエリが M 個あり、各クエリでは、l 番目から r 番目までの数字にそれぞれ v を足し、数列に含まれる最大の hill の幅を答えてください。
ただし、hill とはを満たす部分列です。
解法
hill の左側、すなわち単調増加する部分列の始点と終点をmapで管理し、各クエリごとに、部分列を分割したり連結したりします。右側についても同様です。
hill が組み変わるごとにセグ木に保存しておき、最大値を出力します。
コード
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.*; /* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \\| |// `. / \\||| : |||// \ / _||||| -:- |||||- \ | | \\\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pass System Test! */ public class E { private static class Task { void solve(FastScanner in, PrintWriter out) throws Exception { int N = in.nextInt(); long[] a = in.nextLongArray(N); TreeMap<Integer, Integer> left = new TreeMap<>(); int from = 0; for (int i = 0; i < N; i++) { if (i == N - 1 || a[i] >= a[i + 1]) { left.put(from, i); from = i + 1; } } TreeMap<Integer, Integer> right = new TreeMap<>(); from = N - 1; for (int i = N - 2; i >= -1; i--) { if (i < 0 || a[i] <= a[i + 1]) { right.put(i + 1, from); from = i; } } RMQ rmq = new RMQ(N); for (Map.Entry<Integer, Integer> entry : left.entrySet()) { from = entry.getKey(); int to = entry.getValue(); if (!right.containsKey(to)) continue; int to2 = right.get(to); int width = to2 - from + 1; rmq.update(to, width); } long[] d = new long[N - 1]; for (int i = 0; i < N - 1; i++) { d[i] = a[i + 1] - a[i]; } int M = in.nextInt(); TreeSet<Integer> tmp = new TreeSet<>(); for (int i = 0; i < M; i++) { int l = in.nextInt() - 1; int r = in.nextInt() - 1; long v = in.nextInt(); if (l > 0) { long prev = d[l - 1]; d[l - 1] += v; if (prev <= 0 && d[l - 1] > 0) { // left merge from = left.floorKey(l - 1); int to = left.get(l); left.remove(l); rmq.update(l, 0); left.put(from, to); tmp.add(from); } if (prev < 0 && d[l - 1] >= 0) { // right cut Map.Entry<Integer, Integer> entry = right.floorEntry(l - 1); from = entry.getKey(); int to = entry.getValue(); right.put(from, l - 1); right.put(l, to); rmq.update(from, 0); tmp.add(left.floorKey(from)); tmp.add(left.floorKey(l)); } } if (r < N - 1) { long prev = d[r]; d[r] -= v; if (prev > 0 && d[r] <= 0) { // left cut Map.Entry<Integer, Integer> entry = left.floorEntry(r); from = entry.getKey(); int to = entry.getValue(); left.put(from, r); left.put(r + 1, to); rmq.update(to, 0); tmp.add(from); tmp.add(r + 1); } if (prev >= 0 && d[r] < 0) { // right merge from = right.floorKey(r); int to = right.get(r + 1); right.remove(r + 1); right.put(from, to); rmq.update(from, 0); tmp.add(left.floorKey(from)); } } for (int f : tmp) { int k = left.get(f); Integer to = right.get(k); if (to==null) continue; rmq.update(k, to - f + 1); } tmp.clear(); out.println(rmq.query(0, N + 1)); } } class RMQ { private int N; private long[] seg; RMQ(int M) { N = Integer.highestOneBit(M) * 2; seg = new long[N * 2]; } public void update(int k, long value) { seg[k += N - 1] = value; while (k > 0) { k = (k - 1) / 2; seg[k] = Math.max(seg[k * 2 + 1], seg[k * 2 + 2]); } } //[a, b) long query(int a, int b) { return query(a, b, 0, 0, N); } long query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; long x = query(a, b, k * 2 + 1, l, (l + r) / 2); long y = query(a, b, k * 2 + 2, (l + r) / 2, r); return Math.max(x, y); } } } /** * ここから下はテンプレートです。 */ public static void main(String[] args) throws Exception { OutputStream outputStream = System.out; FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(in, out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) array[i] = next().toCharArray(); return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }