結果
| 問題 | No.833 かっこいい電車 |
| ユーザー |
 Oland
|
| 提出日時 | 2019-11-01 18:43:21 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 333 ms / 2,000 ms |
| コード長 | 10,364 bytes |
| コンパイル時間 | 2,599 ms |
| コンパイル使用メモリ | 79,468 KB |
| 実行使用メモリ | 51,676 KB |
| 最終ジャッジ日時 | 2024-09-14 22:48:36 |
| 合計ジャッジ時間 | 11,451 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
import java.io.*;import java.util.*;@SuppressWarnings("unused")public class Main {private FastScanner in;private PrintWriter out;final int MOD = (int)1e9+7;long ceil(long a, long b){return (a + b - 1) / b;}long gcd(long a, long b){return b == 0 ? a : gcd(b, a % b);}long lcm(long a, long b){return a / gcd(a, b) * b; /*オーバーフローに注意*/}void solve(){int N = in.nextInt(), Q = in.nextInt();long[] A = in.nextLongArray(N);SegmentTree segSum = new SegmentTree(A);long[] rl = new long[N+2];long D = (long)1e5;for(int i = 0; i < N; i++) rl[i] = i + D * (i+1);DualSegmentTree segLR = new DualSegmentTree(rl);for (int i = 0; i < Q; i++) {int q = in.nextInt(), x = in.nextInt()-1;long S1 = segLR.getPoint(x), S2 = segLR.getPoint(x+1);int L1 = (int)(S1 % D), R1 = (int)(S1 / D);int L2 = (int)(S2 % D), R2 = (int)(S2 / D);int L = Math.min(L1, L2), R = Math.max(R1, R2);if(q == 1){segLR.setSegment(L, R, L + D * R);}if(q == 2){segLR.setSegment(L, x+1, L + D * (x+1));segLR.setSegment(x+1, R, (x+1) + D * R);}if(q == 3){segSum.setPoint(x, 1);}if(q == 4){out.println(segSum.getSegment(L1, R1));}}}//end solvestatic class SegmentTree{int n;long[] node;/*二項演算で使える単位元*/private long e = 0;/*結合律が成り立つ、要素同士の二項演算*/private long f(long e1, long e2){return e1 + e2; //区間和}/*要素更新用の演算(可換でなくてもよい)*/private long g(long nodeVal, long val){return nodeVal + val; //加算}/* 単位元で初期化 */public SegmentTree(int sz){n = 1;while(n < sz) n *= 2;node = new long[2*n];Arrays.fill(node, e);}/* 元配列vでセグメント木を初期化 */public SegmentTree(long[] v){this(v.length);for(int i = 0; i < v.length; i++)node[i+n] = v[i];for(int i = n-1; i > 0; i--)node[i] = f(node[2*i+0], node[2*i+1]);}public long getPoint(int x){return node[x + n];}/* 0-indexed:xの要素をg(node[x], val)に更新 */public void setPoint(int x, long val){x += n;node[x] = g(node[x], val);while(x > 1){x = x / 2;node[x] = f(node[2*x+0], node[2*x+1]);}}/* 指定した区間[L,R)の区間演算の結果を求めるクエリ */public long getSegment(int L, int R){L += n;R += n;long resL = e, resR = e;while (L < R) {if ((L & 1) != 0){resL = f(resL, node[L]);L++;}if ((R & 1) != 0){--R;resR = f(resR, node[R]);}L >>= 1;R >>= 1;}return f(resL, resR);}}static class DualSegmentTree {int n;long[] node;int[] stamp;int count;/* 単位元で初期化 */public DualSegmentTree(int sz){n = 1;while(n < sz) n *= 2;node = new long[2*n];Arrays.fill(node, 0);stamp = new int[2*n];count = 0;}/* 元配列vをセグメント木で表現する */public DualSegmentTree(long[] v){this(v.length);for(int i = 0; i < v.length; i++)node[i+n] = v[i];}/* 0-indexed:xの要素を取得する */public long getPoint(int x){x += n;long res = node[x];int maxCount = stamp[x];while(x > 1){x = x / 2;if(maxCount < stamp[x]){maxCount = stamp[x];res = node[x];}}return res;}/* 指定した区間[a,b)に含まれるすべての要素に作用素を適用するクエリ */public void setSegment(int L, int R, long val){count++;//時間を更新L += n;R += n;while (L < R) {if ((L & 1) != 0){node[L] = val;stamp[L] = count;//タイムスタンプL++;}if ((R & 1) != 0){--R;node[R] = val;stamp[R] = count;//タイムスタンプ}L >>= 1;R >>= 1;}}}public static void main(String[] args) {new Main().m();}private void m() {in = new FastScanner(System.in);out = new PrintWriter(System.out);solve();out.flush();in.close();out.close();}static class FastScanner {private Reader input;public FastScanner() {this(System.in);}public FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}public void close() {try {this.input.close();} catch (IOException e) {e.printStackTrace();}}public int nextInt() {return (int) nextLong();}public long nextLong() {try {int sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}long ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) return ret * sign;ret *= 10;ret += b - '0';}} catch (IOException e) {e.printStackTrace();return -1;}}public double nextDouble() {try {double sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}double ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) break;ret *= 10;ret += b - '0';}if (b != '.') return sign * ret;double div = 1;b = input.read();while ('0' <= b && b <= '9') {ret *= 10;ret += b - '0';div *= 10;b = input.read();}return sign * ret / div;} catch (IOException e) {e.printStackTrace();return Double.NaN;}}public char nextChar() {try {int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}return (char) b;} catch (IOException e) {e.printStackTrace();return 0;}}public String nextStr() {try {StringBuilder sb = new StringBuilder();int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}while (b != -1 && !Character.isWhitespace(b)) {sb.append((char) b);b = input.read();}return sb.toString();} catch (IOException e) {e.printStackTrace();return "";}}public int[] nextIntArray(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt();}return res;}public int[] nextIntArrayDec(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt() - 1;}return res;}public int[] nextIntArray1Index(int n) {int[] res = new int[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextInt();}return res;}public long[] nextLongArray(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong();}return res;}public long[] nextLongArrayDec(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong() - 1;}return res;}public long[] nextLongArray1Index(int n) {long[] res = new long[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextLong();}return res;}public double[] nextDoubleArray(int n) {double[] res = new double[n];for (int i = 0; i < n; i++) {res[i] = nextDouble();}return res;}}}