Codeforces Round #590 (Div. 3)_D_선분 수

제목 링크:https://codeforces.com/contest/1234/problem/D
문제 풀이 과정: 이 문 제 를 보 았 습 니 다. 자모의 총 수 는 26 개 에 불과 하기 때문에 저 는 선분 트 리 로 길이 가 26 인 배열 을 유지 하고 이 구간 에 있 는 모든 자모의 총 개 수 를 기록 합 니 다. 그러면 우 리 는 l, r 구간 의 모든 자모 자모의 수량 을 직접 유지 한 다음 에 조회 할 때 (1, r) - (1, l - 1) 을 직접 사용 할 수 있 습 니 다.l - r 구간 의 서로 다른 자모의 개 수 를 얻 을 수 있 습 니 다.
코드:

#include 
#include 
#include 
using namespace std;

const int maxn = 1e5 + 5;

char str[maxn], op[3];
int n, l, r, x, fi[30], permt[30], tmp_permt[30];
struct SegmentTree {int l, r, a[30]; }t[maxn * 4];

inline void build(int s, int l, int r) {
	t[s].l = l, t[s].r = r;
	for(int i = 0; i <= 26; i ++)
		t[s].a[i] = 0;
	if(l == r) return;

	int mid = (l + r) / 2;
	build(s * 2, l, mid);
	build(s * 2 + 1, mid + 1, r);
}

inline void insert(int s, int l, int r, int x) {
	if(l <= t[s].l && r >= t[s].r) {
		t[s].a[x] ++;
		return;
	}

	int mid = t[s].l + t[s].r >> 1;
	if(l <= mid) insert(s * 2, l, r, x);
	else insert(s * 2 + 1, l, r, x);
	t[s].a[x] = t[s * 2].a[x] + t[s * 2 + 1].a[x];
}

inline void change(int s, int l, int r, int y, int x) {
	if(l <= t[s].l && r >= t[s].r) {
		t[s].a[x] ++;
		t[s].a[y] --;
		return;
	}

	int mid = (t[s].l + t[s].r) >> 1;
	if(l <= mid) {
		change(s * 2, l, r, y, x);
		t[s].a[x] = t[s * 2].a[x] + t[s * 2 + 1].a[x];
		t[s].a[y] = t[s * 2].a[y] + t[s * 2 + 1].a[y];
	} else {
		change(s * 2 + 1, l, r, y, x);
		t[s].a[x] = t[s * 2].a[x] + t[s * 2 + 1].a[x];
		t[s].a[y] = t[s * 2].a[y] + t[s * 2 + 1].a[y];
	}
}

inline void query(int s, int l, int r) {
	if(l <= t[s].l && r >= t[s].r) {
		for(int i = 0; i <= 26; i ++)
			permt[i] += t[s].a[i];
		return;
	}

	int mid = (t[s].l + t[s].r) / 2;
	if(l <= mid) query(s * 2, l, r);
	if(mid < r) query(s * 2 + 1, l, r);
}

inline void out(void) {
	for(int i = 0; i <= 26; i ++) permt[i] = 0;
	query(1, 1, 15);
	for(int i = 0; i <= 26; i ++)
		printf("%d%c  ", permt[i], i + 'a');
	puts("");
	for(int i = 0; i <= 26; i ++) permt[i] = 0;
}

int main(void) {
//	freopen("in.txt", "r", stdin);
	scanf("%s", str + 1);
	scanf("%d", &n);
 
	build(1, 1, strlen(str + 1));
	for(int i = 1; i <= strlen(str + 1); i ++) 
		insert(1, i, i, str[i] - 'a');

	for(int i = 1; i <= n; i ++) {
		scanf("%s", op);
		if(op[0] == '1') {
			scanf("%d%s", &x, op);
			change(1, x, x, str[x] - 'a', op[0] - 'a');
			str[x] = op[0];
		} else {
			memset(permt, 0, sizeof permt);
			scanf("%d%d", &l, &r);
			int sum = 0;
			query(1, 1, r);
			memcpy(tmp_permt, permt, sizeof permt);
			memset(permt, 0, sizeof permt);
			query(1, 1, l - 1);
			for(int i = 0; i <= 26; i ++) {
				tmp_permt[i] -= permt[i];
				if(tmp_permt[i] > 0) sum ++;
			}
			
			printf("%d
", sum);	
		}
	}
	
	return 0;
}

결론: 사실 이 문 제 는 제 가 추가 로 쓰 고 싶 은 시간 이 10 분 도 안 될 것 같 습 니 다. 그런데 제 가 코드 를 디 버 깅 할 때 1 시간 정도 바 꾸 었 는데 결국은 바 꾸 지 않 았 습 니 다. 마지막 으로 다시 한 번 검 사 를 했 는데 문제 가 제 가 경기 할 때 생각 하지 못 했 던 점 에 나 타 났 습 니 다. 즉, change 할 때 원래 의 문자열 을 같이 고 치 는 것 을 잊 었 습 니 다.그래서 우 리 는 검 사 를 할 때 반드시 처음부터 자세히 검 사 를 해 야 한다. 문제 가 없 는 지 확인 한 후에 cout 방식 으로 디 버 깅 을 할 수 있다. 마지막 으로 잘못 이 있 는 것 은 사고방식 의 문제 일 수도 있다.