Submission #73434995

Source Code Expand

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>
#define KI_MAX (1 << 19) /* 524288 */
/* 点add、範囲sum */
void ki_add(int64_t ki[], int pos, int64_t value) {
  pos += KI_MAX - 1;
  ki[pos] += value;
  do {
    pos = (pos - 1) / 2;
    ki[pos] = ki[pos * 2  + 1] + ki[pos * 2 + 2];
  } while (pos > 0);
}
int64_t ki_sum_i(const int64_t ki[], int idx, int ss, int se, int qs, int qe) {
  if (se <= qs || qe <= ss) { /* 完全に外れている */
    return 0;
  } else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    return ki[idx];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

/* 点add、範囲sum */

void ki_add(int64_t ki[], int pos, int64_t value) {
	pos += KI_MAX - 1;
	ki[pos] += value;
	do {
		pos = (pos - 1) / 2;
		ki[pos] = ki[pos * 2  + 1] + ki[pos * 2 + 2];
	} while (pos > 0);
}

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

int64_t ki_sum(const int64_t ki[], int qs, int qe) {
	return ki_sum_i(ki, 0, 0, KI_MAX, qs, qe);
}

int N, Q;
int A[512345];
int query[212345][3];

int64_t num_ki[KI_MAX * 2 - 1], sum_ki[KI_MAX * 2 - 1];

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d%d", &query[i][0], &query[i][1], &query[i][2]) != 3) return 1;
	}

	for (i = 1; i <= N; i++) {
		ki_add(num_ki, A[i], 1);
		ki_add(sum_ki, A[i], A[i]);
	}
	for (i = 0; i < Q; i++) {
		if (query[i][0] == 1) {
			int x = query[i][1], y = query[i][2];
			ki_add(num_ki, A[x], -1);
			ki_add(sum_ki, A[x], -A[x]);
			A[x] = y;
			ki_add(num_ki, A[x], 1);
			ki_add(sum_ki, A[x], A[x]);
		} else if (query[i][0] == 2) {
			int l = query[i][1], r = query[i][2];
			printf("%" PRId64 "\n",
				l <= r ? (
					ki_sum(num_ki, 0, l) * l +
					ki_sum(sum_ki, l, r + 1) +
					ki_sum(num_ki, r + 1, KI_MAX) * r
				) : (
					(int64_t)l * N
				)
			);
		}
	}

	return 0;
}

Submission Info

Judge Result