Submission #60216704

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>
#define KI_MAX (1 << 19) /* 524288 */
struct info {
  int color, left, right;
};
struct info ki[KI_MAX * 2 - 1];
char ki_valid[KI_MAX * 2 - 1];
void ki_set_i(int idx, int ss, int se, int qs, int qe, struct info data) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    ki[idx] = data;
    ki_valid[idx] = 1;
  } else if (se <= qs || qe <= ss) { /* 完全に外れている */
    /* 何もしない */
  } else {
    int sm = ss + (se - ss) / 2;
    ki_set_i(idx * 2 + 1, ss, sm, qs, qe, data);
    ki_set_i(idx * 2 + 2, sm, se, qs, qe, data);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

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

struct info {
	int color, left, right;
};

struct info ki[KI_MAX * 2 - 1];
char ki_valid[KI_MAX * 2 - 1];

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

void ki_set(int qs, int qe, struct info data) {
	ki_set_i(0, 0, KI_MAX, qs, qe, data);
}

struct info ki_get_i(int idx, int ss, int se, int q) {
	if (ki_valid[idx]) {
		return ki[idx];
	} else {
		int sm = ss + (se - ss) / 2;
		if (q < sm) {
			return ki_get_i(idx * 2 + 1, ss, sm, q);
		} else {
			return ki_get_i(idx * 2 + 2, sm, se, q);
		}
	}
}

struct info ki_get(int q) {
	return ki_get_i(0, 0, KI_MAX, q);
}

int N, Q;
int type[212345], x[212345], c[212345];

int color_cnt[212345];

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d", &type[i]) != 1) return 1;
		switch (type[i]) {
			case 1:
				if (scanf("%d%d", &x[i], &c[i]) != 2) return 1;
				break;
			case 2:
				if (scanf("%d", &c[i]) != 1) return 1;
				break;
			default:
				return 3;
		}
	}

	/* 両端に番兵を置く */
	ki_set(0, 1, (struct info){0, 0, 0});
	ki_set(N + 1, N + 2, (struct info){0, 0, 0});
	/* マス i を色 i で塗る */
	for (i = 1; i <= N; i++) {
		ki_set(i, i + 1, (struct info){i, i, i});
		color_cnt[i] = 1;
	}

	for (i = 0; i < Q; i++) {
		if (type[i] == 1) {
			struct info current = ki_get(x[i]);
			struct info left = ki_get(current.left - 1);
			struct info right = ki_get(current.right + 1);
			int delta = current.right - current.left + 1;
			color_cnt[current.color] -= delta;
			color_cnt[c[i]] += delta;
			current.color = c[i];
			if (left.color == current.color) current.left = left.left;
			if (right.color == current.color) current.right = right.right;
			ki_set(current.left, current.right + 1, current);
		} else {
			printf("%d\n", color_cnt[c[i]]);
		}
	}

	return 0;
}

/*

範囲設定・1点取得ができるセグメント木で
・そのマスの色
・左側にどこまで同じ色か
・右側にどこまで同じ色か
を管理する。

塗り替える際、左側・右側のマスが同じ色なら連結する。

*/

Submission Info

Judge Result