Submission #75176801

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#define KI_MAX (1 << 18) /* 262144 */
int ki[KI_MAX * 2 - 1];
void ki_set(int pos, int 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);
}
int ki_get_i(int idx, int ss, int se, int qs, int qe) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    return ki[idx];
  } else if (qe <= ss || se <= qs) { /* 完全に外れている */
    return 0;
  } else {
    int sm = ss + (se - ss) / 2;
    return
      ki_get_i(idx * 2 + 1, ss, sm, qs, qe) +
      ki_get_i(idx * 2 + 2, sm, se, qs, qe);
  }
}
int ki_get(int qs, int qe) {
  return ki_get_i(0, 0, KI_MAX, qs, qe);
}
int N, Q;
int A[212345];
int query[512345][3];
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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define KI_MAX (1 << 18) /* 262144 */

int ki[KI_MAX * 2 - 1];

void ki_set(int pos, int 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);
}

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

int ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

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

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", &query[i][0], &query[i][1]) != 2) return 1;
		if (query[i][0] == 2) {
			if (scanf("%d", &query[i][2]) != 1) return 1;
		}
	}

	for (i = 1; i <= N; i++) {
		ki_set(i, A[i]);
	}
	for (i = 0; i < Q; i++) {
		if (query[i][0] == 2) {
			printf("%d\n", ki_get(query[i][1], query[i][2] + 1));
		} else {
			int x = query[i][1];
			int t = A[x];
			A[x] = A[x + 1];
			A[x + 1] = t;
			ki_set(x, A[x]);
			ki_set(x + 1, A[x + 1]);
		}
	}

	return 0;
}

Submission Info

Judge Result