提出 #77980768

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <inttypes.h>
struct data_s {
  uint64_t a, b, c, d, e;
};
struct data_s create_first_data(int v) {
  return (struct data_s){ v, v, v, v, 1 };
}
struct data_s merge_data(struct data_s l, struct data_s r) {
  return (struct data_s){
    l.a + r.a + l.c * r.e + r.b * l.e,
    l.b + l.d * r.e + r.b,
    l.c + r.d * l.e + r.c,
    l.d + r.d,
    l.e + r.e
  };
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

struct data_s {
	uint64_t a, b, c, d, e;
};

struct data_s create_first_data(int v) {
	return (struct data_s){ v, v, v, v, 1 };
}

struct data_s merge_data(struct data_s l, struct data_s r) {
	return (struct data_s){
		l.a + r.a + l.c * r.e + r.b * l.e,
		l.b + l.d * r.e + r.b,
		l.c + r.d * l.e + r.c,
		l.d + r.d,
		l.e + r.e
	};
}

#define KI_MAX (1 << 19) /* 524288 */

struct data_s ki[KI_MAX * 2 - 1];

void ki_init(void) {
	int i;
	for (i = KI_MAX - 2; i >= 0; i--) {
		ki[i] = merge_data(ki[i * 2 + 1], ki[i * 2 + 2]);
	}
}

struct data_s ki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return (struct data_s){ 0, 0, 0, 0, 0 };
	} else {
		int sm = ss + (se - ss) / 2;
		return merge_data(
			ki_get_i(idx * 2 + 1, ss, sm, qs, qe),
			ki_get_i(idx * 2 + 2, sm, se, qs, qe)
		);
	}
}

uint64_t ki_get(int qs, int qe) {
	struct data_s ans = ki_get_i(0, 0, KI_MAX, qs, qe);
	return ans.a;
}

int N, Q;
int A[312345];
int L[312345], R[312345];

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &L[i], &R[i]) != 2) return 1;
	}
	for (i = 0; i < N; i++) {
		ki[KI_MAX - 1 + i] = create_first_data(A[i]);
	}
	ki_init();
	for (i = 0; i < Q; i++) {
		printf("%" PRIu64 "\n", ki_get(L[i] - 1, R[i]));
	}
	return 0;
}

/*

* a: 答え
* b: 左端から各要素までの和の和
* c: 各要素から右端までの和の和
* d: 各要素の和
* e: 要素数

を持つ
左 (a1, b1, c1, d1, e1) と、右 (a2, b2, c2, d2, e2) をマージすると

e = e1 + e2
d = d1 + d2
ここまでは自明

左の要素から始まる部分は、右は全要素を足す
右の要素から始まる部分は、そのまま
なので
c = c1 + d2 * e1 + c2

同様に
b = b1 + d1 * e2 + b2

答えは、左と右それぞれの範囲内のやつの和に加えて、左と右をまたぐやつの和
またぐやつは、左の各要素から始めて、右の各要素で終わる
(左の要素それぞれについて、右の全要素までの和が加わる)
また、右の各要素で終わって、左の各要素で始まる
(右の要素それぞれについて、左の全要素からの和が加わる)
なので
a = a1 + a2 + c1 * e2 + b2 * e1

*/

提出情報

ジャッジ結果