結果
| 問題 | No.426 往復漸化式 |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-09-30 01:14:13 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,548 ms / 5,000 ms |
| コード長 | 8,174 bytes |
| コンパイル時間 | 5,041 ms |
| コンパイル使用メモリ | 88,552 KB |
| 実行使用メモリ | 114,364 KB |
| 最終ジャッジ日時 | 2024-11-21 10:56:10 |
| 合計ジャッジ時間 | 19,583 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 22 |
ソースコード
package No400番台;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.Comparator;public class Q426 {public static void main(String[] args) {new Q426().run();}final long MOD = 1_000_000_000 + 7;static InputStream is;static PrintWriter out;static String INPUT = "";void run() {is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);solver();out.flush();}void solver() {int n = ni();long[][] a_0 = { { nl() }, { nl() }, { nl() } };long[][] b_n = { { nl() }, { nl() } };int q = ni();String[] s = new String[q];int[][] x = new int[q][];int[] shrink = new int[q];long[][][]as = new long[ q][][];long[][][] bs = new long[q][][];for (int i = 0; i < q; i++) {s[i] = ns();shrink[i] = ni();x[i] = new int[] { shrink[i], i };if (s[i].equals("a")) {as[i] = new long[][] { { nl(), nl(), nl() }, { nl(), nl(), nl() }, { nl(), nl(), nl() } };} else if (s[i].equals("b")) {bs[i] = new long[][] { { nl(), nl() }, { nl(), nl() } };}}Arrays.sort(x, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return Integer.compare(o1[0], o2[0]);}});int pos = -1;int[] ref = new int[2 * q + 1];Arrays.fill(ref, -1);for (int i = 0; i < q; i++) {if (i == 0 || x[i][0] != x[i - 1][0]) {if (i == 0 && x[i][0] != 0)pos += 2;else if (i == q - 1 && x[i][0] != n)pos += 2;else if (i != 0 && x[i][0] != x[i - 1][0] + 1)pos += 2;else if (i == 0 && x[i][0] == 0)pos += 1;else if (i != 0 && x[i][0] != x[i - 1][0])pos += 1;}shrink[x[i][1]] = pos;ref[pos] = x[i][0];}if (x[q - 1][0] != n)pos++;pos++;ref = Arrays.copyOf(ref, pos);SegmentTree seg = new SegmentTree(Arrays.copyOf(ref, pos), n);for (int i = 0; i < q; i++) {if (s[i].equals("a")) {seg.set(shrink[i], as[i], 0);} else if (s[i].equals("b")) {seg.set(shrink[i], bs[i], 1);} else if (s[i].equals("ga")) {print(seg.geta(i, a_0, shrink));} else if (s[i].equals("gb")) {if (shrink[i] == pos - 1) {print(b_n);} elseprint(seg.getb(i, a_0, b_n, shrink));}}}void print(long[][] a){for(int i=0;i<a.length;i++){System.out.print(a[i][0]+(i==a.length-1?"\n":" "));}}class SegmentTree {int n = 1;long[][][][] node;public SegmentTree(int[] ref, int N) {int n_ = ref.length;while (n < n_)n *= 2;node = new long[2 * n - 1][3][][];for (int i = 0; i < 2 * n - 1; i++) {node[i][0] = new long[][] { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };node[i][1] = new long[][] { { 1, 0 }, { 0, 1 } };}for (int i = 0; i < n_; i++) {if (ref[i] == -1) {int post = (i == n_ - 1 ? N + 1 : ref[i + 1]);int pre = (i == 0 ? -1 : ref[i - 1]);node[i + n - 1][2] = init(pre + 1, post - 1);} else {node[i + n - 1][2] = init(ref[i], ref[i]);}}for (int i = n - 2; i >= 0; i--) {node[i][2] = merge(node[2 * i + 1], node[2 * i + 2])[2];}}long[][] init(long a, long b) {long sum1 = (b - a + 1) % MOD * (b + a) % MOD * inv2 % MOD;long sum2 = b - a + 1;return new long[][] { { 6L * sum1, 6L * sum1 + 1 * sum2, 6L * sum1 + 2 * sum2 },{ 6L * sum1 + 3L * sum2, 6L * sum1 + 4L * sum2, 6L * sum1 + 5L * sum2 } };}void set(int k, long[][] val, int mode) {k += n - 1;node[k][mode] = val;while (k > 0) {k = (k - 1) / 2;node[k] = merge(node[2 * k + 1], node[2 * k + 2]);}}long[][][] query(int a, int b) {return query(a, b, 0, n, 0);}long[][][] query(int a, int b, int l, int r, int k) {if (r <= a || b <= l) {return new long[][][] { { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } }, { { 1, 0 }, { 0, 1 } }, null };} else if (a <= l && r <= b) {return node[k];} else {long[][][] vl = query(a, b, l, (l + r) / 2, 2 * k + 1);long[][][] vr = query(a, b, (l + r) / 2, r, 2 * k + 2);return merge(vl, vr);}}long[][][] merge(long[][][] vl, long[][][] vr) {long[][][] ret = new long[][][] { mul(vr[0], vl[0]), mul(vl[1], vr[1]), null };if (vl[2] == null && vr[2] == null)ret[2] = null;else if (vl[2] == null)ret[2] = vr[2];else if (vr[2] == null)ret[2] = vl[2];elseret[2] = sum(vl[2], mul(mul(vl[1], vr[2]), vl[0]));return ret;}long[][] geta(int i, long[][] a_0, int[] shrink) {return mul(query(0, shrink[i] - 1 + 1)[0], a_0);}long[][] getb(int i, long[][] a_0, long[][] b_n, int[] shrink) {return sum(mul(query(shrink[i] + 1, n + 1)[1], b_n),mul(mul(query(shrink[i]+1, n + 1)[2], query(0, shrink[i] + 1)[0]), a_0));}}long[][] sum(long[][] A, long[][] B) {long[][] C = new long[A.length][A[0].length];for (int i = 0; i < A.length; i++) {for (int j = 0; j < A[0].length; j++) {C[i][j] = (A[i][j] % MOD + B[i][j] % MOD) % MOD;}}return C;}long[][] mul(long[][] A, long[][] B) {long[][] C = new long[A.length][B[0].length];for (int i = 0; i < A.length; i++) {for (int j = 0; j < B[0].length; j++) {for (int k = 0; k < A[0].length; k++) {C[i][j] += A[i][k] % MOD * B[k][j] % MOD;C[i][j] %= MOD;}}}return C;}long inv2 = inv(2, MOD);long inv(long a, long mod) {a = a % mod;long b = mod;long p = 1, q = 0;while (b > 1) {long c = b / a;b = b % a;q = q - p * c;long d = b;b = a;a = d;d = p;p = q;q = d;}while (q < 0)q += mod;return q;}static long nl() {try {long num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}static char nc() {try {int b = skip();if (b == -1)return 0;return (char) b;} catch (IOException e) {}return 0;}static double nd() {try {return Double.parseDouble(ns());} catch (Exception e) {}return 0;}static String ns() {try {int b = skip();StringBuilder sb = new StringBuilder();if (b == -1)return "";sb.append((char) b);while (true) {b = is.read();if (b == -1)return sb.toString();if (b <= ' ')return sb.toString();sb.append((char) b);}} catch (IOException e) {}return "";}public static char[] ns(int n) {char[] buf = new char[n];try {int b = skip(), p = 0;if (b == -1)return null;buf[p++] = (char) b;while (p < n) {b = is.read();if (b == -1 || b <= ' ')break;buf[p++] = (char) b;}return Arrays.copyOf(buf, p);} catch (IOException e) {}return null;}public static byte[] nse(int n) {byte[] buf = new byte[n];try {int b = skip();if (b == -1)return null;is.read(buf);return buf;} catch (IOException e) {}return null;}static int skip() throws IOException {int b;while ((b = is.read()) != -1 && !(b >= 33 && b <= 126));return b;}static boolean eof() {try {is.mark(1000);int b = skip();is.reset();return b == -1;} catch (IOException e) {return true;}}static int ni() {try {int num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}