結果
| 問題 | No.1558 Derby Live |
| ユーザー |
 cyclerecycle9
|
| 提出日時 | 2021-09-12 08:02:49 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 544 ms / 2,000 ms |
| コード長 | 8,571 bytes |
| コンパイル時間 | 2,646 ms |
| コンパイル使用メモリ | 84,148 KB |
| 実行使用メモリ | 61,896 KB |
| 最終ジャッジ日時 | 2024-06-23 19:50:21 |
| 合計ジャッジ時間 | 20,575 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 33 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.math.BigDecimal;import java.math.RoundingMode;import java.util.*;public class Main {static final long MOD1=1000000007;static final long MOD=998244353;static int ans=0;static int N;public static void main(String[] args){PrintWriter out = new PrintWriter(System.out);InputReader sc=new InputReader(System.in);N = sc.nextInt();int M = sc.nextInt();int Q = sc.nextInt();int[] e = new int[N];for (int i = 0; i < e.length; i++) {e[i] = i;}SegTree<S> segTree = new SegTree<S>(M, S::map, new S(e));for (int i = 0; i < Q; i++) {int x = sc.nextInt();if (x==1) {int D = sc.nextInt();int[] P = sc.nextIntArray(N);Arrays.setAll(P, k -> P[k]-1);segTree.set(D-1, new S(P));}else if (x==2) {int S = sc.nextInt();S p = segTree.prod(0, S);int[] p_inv = new int[N];for (int j = 0; j < p_inv.length; j++) {p_inv[p.p[j]] = j;}for (int j = 0; j < N; j++){out.print((p_inv[j]+1)+" ");}out.println();}else {int L = sc.nextInt()-1;int R = sc.nextInt();int ans = 0;S pl = segTree.prod(0, L);S pr = segTree.prod(0, R);for (int j = 0; j < N; j++) {ans += Math.abs(pl.p[j] - pr.p[j]);}out.println(ans);}}out.flush();}static class S{int[] p;public S(int[] p){this.p = p;}static S map(S a,S b){int[] ps = new int[N];for (int i = 0; i < N; i++) {ps[i] = b.p[a.p[i]];}return new S(ps);}}static class InputReader {private InputStream in;private byte[] buffer = new byte[1024];private int curbuf;private int lenbuf;public InputReader(InputStream in) {this.in = in;this.curbuf = this.lenbuf = 0;}public boolean hasNextByte() {if (curbuf >= lenbuf) {curbuf = 0;try {lenbuf = in.read(buffer);} catch (IOException e) {throw new InputMismatchException();}if (lenbuf <= 0)return false;}return true;}private int readByte() {if (hasNextByte())return buffer[curbuf++];elsereturn -1;}private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}private void skip() {while (hasNextByte() && isSpaceChar(buffer[curbuf]))curbuf++;}public boolean hasNext() {skip();return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (!isSpaceChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public int nextInt() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}int res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public long nextLong() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}long res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public double nextDouble() {return Double.parseDouble(next());}public int[] nextIntArray(int n) {int[] a = new int[n];for (int i = 0; i < n; i++)a[i] = nextInt();return a;}public double[] nextDoubleArray(int n) {double[] a = new double[n];for (int i = 0; i < n; i++)a[i] = nextDouble();return a;}public long[] nextLongArray(int n) {long[] a = new long[n];for (int i = 0; i < n; i++)a[i] = nextLong();return a;}public char[][] nextCharMap(int n, int m) {char[][] map = new char[n][m];for (int i = 0; i < n; i++)map[i] = next().toCharArray();return map;}}}//funはlamda式で定義//prodで取得,setで更新(一点加算なら更新でおｋ)//二ブタンも出来る//SegTree<Integer> segTree=new SegTree<Integer>(N, (x,y)->x+y, 0);使用例class SegTree<S> {final int MAX;final int N;final java.util.function.BinaryOperator<S> op;final S E;final S[] data;@SuppressWarnings("unchecked")public SegTree(int n, java.util.function.BinaryOperator<S> op, S e) {this.MAX = n;int k = 1;while (k < n) k <<= 1;this.N = k;this.E = e;this.op = op;this.data = (S[]) new Object[N << 1];java.util.Arrays.fill(data, E);}public SegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e) {this(dat.length, op, e);build(dat);}private void build(S[] dat) {int l = dat.length;System.arraycopy(dat, 0, data, N, l);for (int i = N - 1; i > 0; i--) {data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]);}}public void set(int p, S x) {exclusiveRangeCheck(p);data[p += N] = x;p >>= 1;while (p > 0) {data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]);p >>= 1;}}public S get(int p) {exclusiveRangeCheck(p);return data[p + N];}public S prod(int l, int r) {if (l > r) {throw new IllegalArgumentException(String.format("Invalid range: [%d, %d)", l, r));}inclusiveRangeCheck(l);inclusiveRangeCheck(r);S sumLeft = E;S sumRight = E;l += N; r += N;while (l < r) {if ((l & 1) == 1) sumLeft = op.apply(sumLeft, data[l++]);if ((r & 1) == 1) sumRight = op.apply(data[--r], sumRight);l >>= 1; r >>= 1;}return op.apply(sumLeft, sumRight);}public S allProd() {return data[1];}public int maxRight(int l, java.util.function.Predicate<S> f) {inclusiveRangeCheck(l);if (!f.test(E)) {throw new IllegalArgumentException("Identity element must satisfy the condition.");}if (l == MAX) return MAX;l += N;S sum = E;do {l >>= Integer.numberOfTrailingZeros(l);if (!f.test(op.apply(sum, data[l]))) {while (l < N) {l = l << 1;if (f.test(op.apply(sum, data[l]))) {sum = op.apply(sum, data[l]);l++;}}return l - N;}sum = op.apply(sum, data[l]);l++;} while ((l & -l) != l);return MAX;}public int minLeft(int r, java.util.function.Predicate<S> f) {inclusiveRangeCheck(r);if (!f.test(E)) {throw new IllegalArgumentException("Identity element must satisfy the condition.");}if (r == 0) return 0;r += N;S sum = E;do {r--;while (r > 1 && (r & 1) == 1) r >>= 1;if (!f.test(op.apply(data[r], sum))) {while (r < N) {r = r << 1 | 1;if (f.test(op.apply(data[r], sum))) {sum = op.apply(data[r], sum);r--;}}return r + 1 - N;}sum = op.apply(data[r], sum);} while ((r & -r) != r);return 0;}private void exclusiveRangeCheck(int p) {if (p < 0 || p >= MAX) {throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX));}}private void inclusiveRangeCheck(int p) {if (p < 0 || p > MAX) {throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX));}}}