글 읽기 - 어디서 틀린걸까요..? 세그먼트 트리, 누적합 공식

wonmo 6년 전 0

누적합 세그먼트 트리로 구간에 대한 합 정보를 저장하고

1이 들어오면 b까지의 누적합 - (a-1까지의 누적합)을계산하고 이 둘이 같다면 yes아니면 no를 출력하게 했는데..

자꾸 틀렸다고 나오네요.. 어디서 틀렸을까요..??

#include<iostream>
#include<vector>
using namespace std;
vector<long long> seg;
long long seglen, n, m, x, y, z;
int idxer[100000];

long long init(int node,int start,int end) {
	if (start == end)return seg[node];
	int mid = (start + end) / 2;
	return seg[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end);
}

void update(int idx,int diff) {
	seg[idx] = diff;
	idx /= 2;
	while (idx){
		seg[idx] = seg[idx * 2] + seg[idx * 2 + 1];
		idx /= 2;
	}
}

long long query(int node,int start,int end,int p,int q) {
	if (start <= p&&q <= end)return seg[node];
	if (q < start || end < p)return 0;
	int mid = (p + q) / 2;
	return query(node * 2, start, end, p, mid) + query(node * 2 + 1, start, end, mid + 1, q);
}

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--){
		seglen = 1;
		scanf("%lld %lld", &n, &m);
		while (seglen<n)
			seglen *= 2;
		seg.clear();
		seg.resize(seglen * 2);
		for (int i = 0;i < n;i++) {
			seg[i + seglen] = i + 1;
			idxer[i] = i;
		}
		init(1, 0, seglen - 1);
		while (m--){
			scanf("%lld %lld %lld", &x, &y, &z);
			if (x == 1) {
				long long temp = query(1, y, z, 0, seglen - 1);
				long long temp2 = (z+2)*(z + 1) / 2 - y*(y + 1) / 2;
				if (temp == temp2)printf("YES\n");
				else printf("NO\n");
			}
			else {
				update(seglen + idxer[y], z + 1);
				update(seglen + idxer[z], y + 1);
				swap(idxer[y], idxer[z]);
			}
		}
	}
	return 0;
}

jason9319 6년 전 7

단순히 누적합으로 해결하려 하신다면

2~4에 1 3 5 가 있는 경우에도 YES로 판단할 것입니다.

힌트를 드리자면 이 문제는 누적합 세그먼트 트리보다는 최대,최소 세그먼트 트리를 이용하시는 걸 추천드립니다.

wonmo 6년 전 0

아 그렇군요~!! 우왕 제가 너무 단순하게 생각했나보네요~! 감사합니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디서 틀린걸까요..? 세그먼트 트리, 누적합 공식

wonmo 6년 전 0

jason9319 6년 전 7

wonmo 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말