結果
| 問題 | No.619 CardShuffle |
| ユーザー |
 uwi
|
| 提出日時 | 2017-12-19 00:25:27 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 595 ms / 3,000 ms |
| コード長 | 7,103 bytes |
| コンパイル時間 | 4,567 ms |
| コンパイル使用メモリ | 85,636 KB |
| 実行使用メモリ | 70,700 KB |
| 最終ジャッジ日時 | 2024-12-22 21:27:37 |
| 合計ジャッジ時間 | 15,993 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 35 |
ソースコード
package adv2017;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.InputMismatchException;public class N619 {InputStream is;PrintWriter out;String INPUT = "";void solve(){int n = ni();int[] vs = new int[n/2+1];char[] os = new char[n/2];for(int i = 0;i < n;i++){char c = nc();if(i % 2 == 0){vs[i/2] = c-'0';}else{os[i/2] = c;}}SegmentTree4Tuple st = new SegmentTree4Tuple(vs, os);for(int Q = ni();Q > 0;Q--){int t = nc();int x = ni()-1;int y = ni()-1;if(t == '!'){if(x % 2 == 0){x /= 2; y /= 2;int d = vs[x]; vs[x] = vs[y]; vs[y] = d;st.update(x, vs[x]);st.update(y, vs[y]);}else{x /= 2; y /= 2;char d = os[x]; os[x] = os[y]; os[y] = d;st.updateo(x, os[x]);st.updateo(y, os[y]);}}else{long[] res = st.smax(x/2, y/2+1);if(res[3] == 1){out.println(res[0]);}else{out.println((res[0]+res[1]+res[2])%1000000007);}}}}public static class SegmentTree4Tuple {public int M, H, N;public long[][] st;public long I = Long.MIN_VALUE/3 + 30000;public int mod = 1000000007;// L M R Apublic char[] os;public SegmentTree4Tuple(int[] vs, char[] os){N = vs.length;M = Integer.highestOneBit(Math.max(N-1, 1))<<2;H = M>>>1;this.os = Arrays.copyOf(os, H);st = new long[M][4];for(int i = 0;i < H;i++){if(i < N){st[H+i][0] = vs[i];st[H+i][2] = vs[i];st[H+i][3] = 1;}else{st[H+i] = null;}}for(int i = H-1;i >= 1;i--){propagate(i);}}private void propagate(int i){int h = Integer.highestOneBit(2*i);int rind = (2*i+1-h)*(H/h);long[] P = st[i], L = st[2*i], R = st[2*i+1];char O = os[rind-1];propNC(P, L, R, O);}private long[] propNC(long[] P, long[] L, long[] R, char O){if(O == 0){if(L != null){P[0] = L[0];P[1] = L[1];P[2] = L[2];P[3] = L[3];return P;}else{return P;}}if(O == '+'){if(L[3] == 0){if(R[3] == 0){P[0] = L[0];P[1] = (L[1] + R[1] + L[2] + R[0]) % mod;P[2] = R[2];}else{P[0] = L[0];P[1] = (L[1] + R[1] + L[2]) % mod;P[2] = R[2];}}else{if(R[3] == 0){P[0] = L[0];P[1] = (L[1] + R[1] + R[0]) % mod;P[2] = R[2];}else{P[0] = L[0];P[1] = (L[1] + R[1]) % mod;P[2] = R[2];}}P[3] = 0;}else if(O == '*'){P[3] = 0;if(L[3] == 0){if(R[3] == 0){P[0] = L[0];P[1] = (L[1] + R[1] + L[2] * R[0]) % mod;P[2] = R[2];}else{P[0] = L[0];P[1] = (L[1] + R[1]) % mod;P[2] = L[2]*R[2]%mod;}}else{if(R[3] == 0){P[0] = L[0]*R[0]%mod;P[1] = (L[1] + R[1]) % mod;P[2] = R[2];}else{P[0] = P[2] = L[0]*R[0]%mod;P[1] = 0;P[3] = 1;}}}return P;}public void update(int pos, long v){st[H+pos][0] = v;st[H+pos][2] = v;st[H+pos][3] = 1;for(int x = H+pos>>>1;x != 0;x>>>=1){int h = Integer.highestOneBit(2*x);int rind = (2*x+1-h)*(H/h);char O = os[rind-1];propNC(st[x], st[2*x], st[2*x+1], O);}}public void updateo(int pos, char c){os[pos] = c;int x = (H>>>Integer.numberOfTrailingZeros(pos+1)+1)+(pos+1>>>Integer.numberOfTrailingZeros(pos+1)+1);for(;x != 0;x>>>=1){int h = Integer.highestOneBit(2*x);int rind = (2*x+1-h)*(H/h);char O = os[rind-1];propNC(st[x], st[2*x], st[2*x+1], O);}}public long[] smax(int l, int r){ return smax(l, r, 0, H, 1); }private long[] smax(int l, int r, int cl, int cr, int cur){if(l <= cl && cr <= r){return Arrays.copyOf(st[cur], st[cur].length);}else{int mid = cl+cr>>>1;long[] L = null, R = null;if(cl < r && l < mid){L = smax(l, r, cl, mid, 2*cur);}if(mid < r && l < cr){R = smax(l, r, mid, cr, 2*cur+1);}if(L != null && R != null){int h = Integer.highestOneBit(2*cur);int rind = (2*cur+1-h)*(H/h);char O = os[rind-1];return propNC(new long[4], L, R, O);}return L != null ? L : R;}}}void run() throws Exception{is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);long s = System.currentTimeMillis();solve();out.flush();if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){// @Override// public void run() {// long s = System.currentTimeMillis();// solve();// out.flush();// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// }// };// t.start();// t.join();}public static void main(String[] args) throws Exception { new N619().run(); }private byte[] inbuf = new byte[1024];public int lenbuf = 0, ptrbuf = 0;private int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private double nd() { return Double.parseDouble(ns()); }private char nc() { return (char)skip(); }private String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')sb.appendCodePoint(b);b = readByte();}return sb.toString();}private char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private long[] nal(int n){long[] a = new long[n];for(int i = 0;i < n;i++)a[i] = nl();return a;}private char[][] nm(int n, int m) {char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private int[][] nmi(int n, int m) {int[][] map = new int[n][];for(int i = 0;i < n;i++)map[i] = na(m);return map;}private int ni() { return (int)nl(); }private long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }}