Submission #71280460

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 <string.h>
#include <inttypes.h>
#define KI_MAX (1 << 18) /* 262144 */
struct data_s {
  int zero_cnt, one_cnt;
  int64_t tentosu, gyaku_tentosu;
};
struct data_s inv(struct data_s d) {
  return (struct data_s){
    d.one_cnt,
    d.zero_cnt,
    d.gyaku_tentosu,
    d.tentosu
  };
}
struct data_s merge(struct data_s l, struct data_s r) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

struct data_s {
	int zero_cnt, one_cnt;
	int64_t tentosu, gyaku_tentosu;
};

struct data_s inv(struct data_s d) {
	return (struct data_s){
		d.one_cnt,
		d.zero_cnt,
		d.gyaku_tentosu,
		d.tentosu
	};
}

struct data_s merge(struct data_s l, struct data_s r) {
	return (struct data_s){
		l.zero_cnt + r.zero_cnt,
		l.one_cnt + r.one_cnt,
		l.tentosu + r.tentosu + (int64_t)l.one_cnt * r.zero_cnt,
		l.gyaku_tentosu + r.gyaku_tentosu + (int64_t)l.zero_cnt * r.one_cnt
	};
}

struct data_s ki[KI_MAX * 2 - 1];
char ki_all_inv[KI_MAX * 2 - 1];

void ki_init(void) {
	int i;
	for (i = 0; i < KI_MAX; i++) {
		ki[KI_MAX - 1 + i] = (struct data_s){ 1, 0, 0, 0 };
	}
	for (i = KI_MAX - 2; i >= 0; i--) {
		ki[i] = merge(ki[i * 2 + 1], ki[i * 2 + 2]);
	}
	memset(ki_all_inv, 0, sizeof(ki_all_inv));
}

struct data_s ki_inv_i(int idx, int ss, int se, int qs, int qe) {
	if (se <= qs || qe <= ss) { /* 完全に外れている */
		/* 何もしない */
	} else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		ki_all_inv[idx] = !ki_all_inv[idx];
	} else {
		int sm = ss + (se - ss) / 2;
		if (ki_all_inv[idx]) {
			ki_all_inv[idx * 2 + 1] = !ki_all_inv[idx * 2 + 1];
			ki_all_inv[idx * 2 + 2] = !ki_all_inv[idx * 2 + 2];
			ki_all_inv[idx] = 0;
		}
		ki[idx] = merge(
			ki_inv_i(idx * 2 + 1, ss, sm, qs, qe),
			ki_inv_i(idx * 2 + 2, sm, se, qs, qe)
		);
	}
	return ki_all_inv[idx] ? inv(ki[idx]) : ki[idx];
}

void ki_inv(int qs, int qe) {
	ki_inv_i(0, 0, KI_MAX, qs, qe);
}

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

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

int N, Q;
int A[212345];
int T[212345], L[212345], R[212345];

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%d" ,&T[i], &L[i], &R[i]) != 3) return 1;
	}

	ki_init();
	for (i = 0; i < N; i++) {
		if (A[i] != 0) ki_inv(i, i + 1);
	}
	for (i = 0; i < Q; i++) {
		switch (T[i]) {
			case 1:
				ki_inv(L[i] - 1, R[i]);
				break;
			case 2:
				{
					struct data_s ans = ki_get(L[i] - 1, R[i]);
					printf("%" PRId64 "\n", ans.tentosu);
				}
				break;
		}
	}
	return 0;
}

/*

各区間について、以下の情報を持つ
・「0」の数
・「1」の数
・転倒数 (「1」の後にある「0」の数)
・逆転倒数 (「0」の後にある「1」の数)

inv操作
・「0」の数と「1」の数を入れ替える
・転倒数と逆転倒数を入れ替える

merge操作
・「0」の数を足す
・「1」の数を足す
・転倒数は、転倒数の和に、左の「1」の数×右の「0」の数を足す
・逆転倒数は、逆転倒数の和に、左の「0」の数×右の「1」の数を足す

*/

Submission Info

Judge Result