結果
| 問題 |
No.2395 区間二次変換一点取得
|
| コンテスト | |
| ユーザー |
 hiromi_ayase
|
| 提出日時 | 2023-07-28 22:16:25 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,326 ms / 2,000 ms |
| コード長 | 6,069 bytes |
| コンパイル時間 | 2,240 ms |
| コンパイル使用メモリ | 91,312 KB |
| 実行使用メモリ | 109,772 KB |
| 最終ジャッジ日時 | 2024-10-06 19:19:51 |
| 合計ジャッジ時間 | 14,575 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
import java.util.*;
@SuppressWarnings("unused")
public class Main {
static class SegmentTreeRSQ {
public int M, H, N;
public long[] st;
public long[] plus;
public SegmentTreeRSQ(int n) {
N = n;
M = Integer.highestOneBit(Math.max(N - 1, 1)) << 2;
H = M >>> 1;
st = new long[M];
plus = new long[H];
}
public SegmentTreeRSQ(int[] a) {
N = a.length;
M = Integer.highestOneBit(Math.max(N - 1, 1)) << 2;
H = M >>> 1;
st = new long[M];
plus = new long[H];
for (int i = 0; i < N; i++) {
st[H + i] = a[i];
}
for (int i = (M >> 1) - 1; i >= 1; i--) {
propagate(i);
}
}
public void add(int pos, int v) {
for (int i = H + pos; i >= 1; i >>>= 1) {
st[i] += v;
}
}
private void propagate(int i) {
int count = H / Integer.highestOneBit(i);
st[i] = st[2 * i] + st[2 * i + 1] + plus[i] * count;
}
public void add(int l, int r, int v) {
if (l < r)
add(l, r, v, 0, H, 1);
}
private void add(int l, int r, int v, int cl, int cr, int cur) {
if (cur >= H) {
st[cur] += v;
} else if (l <= cl && cr <= r) {
plus[cur] += v;
propagate(cur);
} else {
int mid = cl + cr >>> 1;
if (cl < r && l < mid) {
add(l, r, v, cl, mid, 2 * cur);
}
if (mid < r && l < cr) {
add(l, r, v, mid, cr, 2 * cur + 1);
}
propagate(cur);
}
}
private long gsum;
public long sum(int l, int r) {
gsum = 0;
sum(l, r, 0, H, 1);
return gsum;
}
private void sum(int l, int r, int cl, int cr, int cur) {
if (l <= cl && cr <= r) {
gsum += st[cur];
} else {
int mid = cl + cr >>> 1;
if (cl < r && l < mid) {
sum(l, r, cl, mid, 2 * cur);
}
if (mid < r && l < cr) {
sum(l, r, mid, cr, 2 * cur + 1);
}
gsum += plus[cur] * (Math.min(r, cr) - Math.max(l, cl));
}
}
}
private static void solve() {
int n = ni();
int b = ni();
int q = ni();
int[][] mat = {
{ 1, 0, 0, 0, 1 },
{ 0, 3, 2, 2, 0 },
{ 0, 0, 3, 0, 0 },
{ 0, 0, 3, 3, 0 },
{ 0, 0, 0, 0, 1 }
};
int[][] e = {
{ 1, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1 }
};
int[] a = { 1, 1, 1, 1, 1 };
int[][][] list = new int[q + 1][][];
int[][] cur = e;
for (int i = 0; i <= q; i++) {
list[i] = cur;
cur = mul(cur, mat, b);
}
var st = new SegmentTreeRSQ(n);
for (int i = 0; i < q; i++) {
int l = ni() - 1;
int m = ni() - 1;
int r = ni();
st.add(l, r, 1);
long k = st.sum(m, m + 1);
int[] ret = mul(list[(int)k], a, b);
out.println(ret[0] + " " + ret[1] + " " + ret[2]);
}
}
public static int[] mul(int[][] A, int[] v, int mod)
{
int m = A.length;
int n = v.length;
int[] w = new int[m];
for(int i = 0;i < m;i++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * v[k];
sum %= mod;
}
w[i] = (int)sum;
}
return w;
}
public static int[][] mul(int[][] A, int[][] B, int mod) {
assert A[0].length == B.length;
int m = A.length;
int n = A[0].length;
int o = B[0].length;
int[][] C = new int[m][o];
for (int i = 0; i < m; i++) {
for (int j = 0; j < o; j++) {
long sum = 0;
for (int k = 0; k < n; k++) {
sum += (long) A[i][k] * B[k][j];
sum %= mod;
}
C[i][j] = (int) sum;
}
}
return C;
}
public static void main(String[] args) {
new Thread(null, new Runnable() {
@Override
public void run() {
long start = System.currentTimeMillis();
String debug = args.length > 0 ? args[0] : null;
if (debug != null) {
try {
is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
} catch (Exception e) {
throw new RuntimeException(e);
}
}
reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
solve();
out.flush();
tr((System.currentTimeMillis() - start) + "ms");
}
}, "", 64000000).start();
}
private static java.io.InputStream is = System.in;
private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
private static java.util.StringTokenizer tokenizer = null;
private static java.io.BufferedReader reader;
public static String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new java.util.StringTokenizer(reader.readLine());
} catch (Exception e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
private static double nd() {
return Double.parseDouble(next());
}
private static long nl() {
return Long.parseLong(next());
}
private static int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private static char[] ns() {
return next().toCharArray();
}
private static long[] nal(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nl();
return a;
}
private static int[][] ntable(int n, int m) {
int[][] table = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table[i][j] = ni();
}
}
return table;
}
private static int[][] nlist(int n, int m) {
int[][] table = new int[m][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table[j][i] = ni();
}
}
return table;
}
private static int ni() {
return Integer.parseInt(next());
}
private static void tr(Object... o) {
if (is != System.in)
System.out.println(java.util.Arrays.deepToString(o));
}
}