結果
| 問題 | No.876 Range Compress Query |
| ユーザー |
 kusomushi
|
| 提出日時 | 2019-09-08 05:35:25 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 580 ms / 2,000 ms |
| コード長 | 11,774 bytes |
| コンパイル時間 | 4,771 ms |
| コンパイル使用メモリ | 77,232 KB |
| 実行使用メモリ | 63,940 KB |
| 最終ジャッジ日時 | 2023-09-09 22:21:43 |
| 合計ジャッジ時間 | 8,829 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 45 ms
49,664 KB |
| testcase_01 | AC | 75 ms
51,816 KB |
| testcase_02 | AC | 49 ms
49,712 KB |
| testcase_03 | AC | 93 ms
53,056 KB |
| testcase_04 | AC | 59 ms
50,996 KB |
| testcase_05 | AC | 57 ms
50,864 KB |
| testcase_06 | AC | 84 ms
52,528 KB |
| testcase_07 | AC | 77 ms
51,780 KB |
| testcase_08 | AC | 82 ms
52,164 KB |
| testcase_09 | AC | 81 ms
52,480 KB |
| testcase_10 | AC | 82 ms
51,900 KB |
| testcase_11 | AC | 530 ms
62,372 KB |
| testcase_12 | AC | 484 ms
63,072 KB |
| testcase_13 | AC | 514 ms
62,012 KB |
| testcase_14 | AC | 537 ms
63,096 KB |
| testcase_15 | AC | 459 ms
62,116 KB |
| testcase_16 | AC | 563 ms
63,940 KB |
| testcase_17 | AC | 558 ms
62,976 KB |
| testcase_18 | AC | 580 ms
63,440 KB |
ソースコード
import java.io.*;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.function.Function;
public class Main {
static int N, Q;
static int[] A;
public static void main(String[] args) {
FastScanner sc = new FastScanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
N = sc.nextInt();
Q = sc.nextInt();
A = sc.nextIntArray(N);
FenwickTree between = new FenwickTree(N-1, FenwickTree.SUM);
RangeUpdate seg = new RangeUpdate(N, RangeUpdate.ADD);
for (int i = 0; i < N; i++) {
if( i != N-1 && A[i] != A[i+1] ) {
between.add(i, 1);
}
seg.update(i, i+1, A[i]);
}
for (int q = 0; q < Q; q++) {
int type = sc.nextInt();
if( type == 1 ) {
int l = sc.nextInt()-1;
int r = sc.nextInt()-1;
int v = sc.nextInt();
// [l, r]をv増やす
// -> between(l-1, l)とbetween(r, r+1)が変化する
if( l != 0 ) {
long prev = seg.get(l-1);
long left = seg.get(l);
if( prev == left ) {
// 切れる
between.add(l-1, 1);
}
}
if( r != N-1 ) {
if( seg.get(r) == seg.get(r+1) ) {
// 切れる
between.add(r, 1);
}
}
seg.update(l, r+1, v);
if( l != 0 ) {
long prev = seg.get(l-1);
long left = seg.get(l);
if( prev == left ) {
// つながった
between.add(l-1, -1);
}
}
if( r != N-1 ) {
if( seg.get(r) == seg.get(r+1) ) {
// つながった
between.add(r, -1);
}
}
} else {
int l = sc.nextInt()-1;
int r = sc.nextInt()-1;
int bet = (int)between.query(l, r); // [l, r] -> between[l, r-1] -> between[l, r)
pw.println(bet+1);
}
}
pw.flush();
}
static class FenwickTree {
interface Monoid {
long identity();
long apply(long a, long b);
long inverse(long a);
}
static Monoid SUM = new Monoid() {
public long identity() { return 0; }
public long apply(long a, long b) { return a+b; }
public long inverse(long a) { return -a; }
};
static Monoid MAX = new Monoid() {
public long identity() { return 0; }
public long apply(long a, long b) { return Math.max(a, b); }
public long inverse(long a) { throw new RuntimeException("no inverse"); }
};
int size;
long[] bit;
Monoid m;
long identity;
FenwickTree(int size, Monoid m) {
this.size = 1;
while( this.size < size ) this.size *= 2;
this.bit = new long[this.size+1];
this.identity = m.identity();
if( this.identity != 0 ) {
Arrays.fill(this.bit, this.identity);
}
this.m = m;
}
void add(int i, long v) {
i++; // 0 index -> 1 index
while( i <= size ) {
bit[i] = m.apply(bit[i], v);
i += i & -i;
}
}
// [0, r)
long query(int r) {
// 0 index -> 1 index -> -1
long ret = identity;
while(r > 0) {
ret = m.apply(ret, bit[r]);
r -= r & -r;
}
return ret;
}
long query(int l, int r) {
return query(r) + m.inverse(query(l));
}
int lowerBound(int v) {
if( bit[size] < v ) return size;
int x = 0;
for (int k = size/2; k > 0; k /= 2 ) {
if( bit[x + k] < v ) {
v -= bit[x+k];
x += k;
}
}
return x;
}
}
static class RangeGet {
interface Monoid {
long identity();
long apply(long a, long b);
}
static Monoid MOD_SUM(int mod) {
return new Monoid() {
public long identity() { return 0; }
public long apply(long a, long b) {
long c = a + b;
if( c >= mod ) {
c %= mod;
}
return c;
}
};
}
static Monoid SUM = new Monoid() {
public long identity() { return 0; }
public long apply(long a, long b) { return a + b; }
};
static Monoid MAX = new Monoid() {
public long identity() { return Long.MIN_VALUE / 2; }
public long apply(long a, long b) { return Math.max(a, b); }
};
static Monoid MIN = new Monoid() {
public long identity() { return Long.MAX_VALUE / 2; }
public long apply(long a, long b) { return Math.min(a, b); }
};
int size;
long[] tree;
Monoid m;
long identity;
RangeGet(int size, Monoid m) {
this.size = 1;
while( this.size < size ) this.size *= 2;
this.tree = new long[this.size*2];
this.m = m;
this.identity = m.identity();
if( this.identity != 0 ) {
Arrays.fill(this.tree, this.identity);
}
}
void update(int idx, long v) {
idx += size;
tree[idx] = v;
while(idx > 0) {
idx /= 2;
tree[idx] = m.apply(tree[idx*2], tree[idx*2+1]);
}
}
// [from, to)
long query(int from, int to) {
return _query(from, to, 1, 0, size);
}
private long _query(int from, int to, int idx, int l, int r) {
if (r <= from || to <= l) return identity;
if (from <= l && r <= to) {
return tree[idx];
} else {
int mid = (l+r)/2;
long vl = _query(from, to, idx*2, l, mid);
long vr = _query(from, to, idx*2+1, mid, r);
return m.apply(vl, vr);
}
}
long get(int idx) {
return tree[idx+size];
}
}
static class RangeUpdate {
interface Monoid {
long identity();
long apply(long a, long b);
}
static Monoid ADD = new Monoid() {
public long identity() { return 0; }
public long apply(long a, long b) { return a + b; }
};
static Monoid MAX = new Monoid() {
public long identity() { return Long.MIN_VALUE / 2; }
public long apply(long a, long b) { return Math.max(a, b); }
};
static Monoid MIN = new Monoid() {
public long identity() { return Long.MAX_VALUE / 2; }
public long apply(long a, long b) { return Math.min(a, b); }
};
int size;
long[] tree;
Monoid m;
long identity;
RangeUpdate(int size, Monoid m) {
this.size = 1;
while( this.size < size ) this.size *= 2;
this.tree = new long[this.size*2];
this.m = m;
this.identity = m.identity();
if( this.identity != 0 ) {
Arrays.fill(this.tree, this.identity);
}
}
// [from, to)
void update(int from, int to, long v) {
_update(from, to, 1, 0, size, v);
}
void _update(int from, int to, int idx, int l, int r, long v) {
if (from <= l && r <= to) {
tree[idx] = m.apply(tree[idx], v);
return;
}
int mid = (l+r)/2;
if (from < mid) _update(from, to, idx*2, l, mid, v);
if (mid < to) _update(from, to, idx*2+1, mid, r, v);
}
long get(int idx) {
long ret = identity;
idx += size;
while( idx > 0 ) {
ret = m.apply(tree[idx], ret);
idx /= 2;
}
return ret;
}
}
@SuppressWarnings("unused")
static class FastScanner {
private BufferedReader reader;
private StringTokenizer tokenizer;
FastScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = null;
}
String next() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
String nextLine() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
long nextLong() {
return Long.parseLong(next());
}
int nextInt() {
return Integer.parseInt(next());
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
int[] nextIntArray(int n, int delta) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt() + delta;
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
}
static <A> void writeLines(A[] as, Function<A, String> f) {
PrintWriter pw = new PrintWriter(System.out);
for (A a : as) {
pw.println(f.apply(a));
}
pw.flush();
}
static void writeLines(int[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (int a : as) pw.println(a);
pw.flush();
}
static void writeLines(long[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (long a : as) pw.println(a);
pw.flush();
}
static int max(int... as) {
int max = Integer.MIN_VALUE;
for (int a : as) max = Math.max(a, max);
return max;
}
static int min(int... as) {
int min = Integer.MAX_VALUE;
for (int a : as) min = Math.min(a, min);
return min;
}
static void debug(Object... args) {
StringJoiner j = new StringJoiner(" ");
for (Object arg : args) {
if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
else j.add(arg.toString());
}
System.err.println(j.toString());
}
}