글 읽기 - 레이지 프로퍼게이션으로 풀었는데 무엇이 잘못된걸까요..

pyeong 2년 전 0

몇번을 체크해봤는데 어떤부분이 잘못되었는지 모르겠습니다..

도와주세요

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
int p[601000], lz[2000100];
vector<int> s;

int seg(int c, int a, int b){
	if(a==b) return s[c]=p[a];
	int m=(a+b)>>1;
	return s[c]=seg(c<<1, a, m)^seg(c<<1|1, m+1, b);
}

void prop(int c, int a, int b){
	if((b-a+1)&1) s[c]^=lz[c];
	if(a!=b){ lz[c<<1]^=lz[c]; lz[c<<1|1]^=lz[c]; }
	lz[c]=0;
}

void upd(int c, int a, int b, int l, int r, int t){
	if(lz[c]) prop(c, a, b);
	if(l<=a&&b<=r){ lz[c]^=t; prop(c, a, b); return; }
	int m=(a+b)>>1;
	if(!(a>r||m<l)) upd(c<<1, a, m, l, r, t);
	if(!(m+1>r||b<l)) upd(c<<1|1, m+1, b, l, r, t);
	s[c]=s[c<<1]^s[c<<1|1];
}

int sum(int c, int a, int b, int l, int r){
	if(lz[c]) prop(c, a, b);
	if(a>r||b<l) return 0;
	if(l<=a&&b<=r) return s[c];
	int m=(a+b)>>1;
	return sum(c<<1, a, m, l, r)^sum(c<<1|1, m+1, b, l, r);
}

int main(){
	int n, m, a, b, c, d, t, i;
	scanf("%d", &n); s.resize(n*4);
	for(i=0; i<n; i++) scanf("%d", &p[i]);
	t=1<<int(ceil(log2(n)));
	seg(1, 0, t-1); scanf("%d", &m);
	for(i=0; i<m; i++){
		scanf("%d %d %d", &a, &b, &c);
		if(b>c) swap(b, c);
		if(a&1){
			scanf("%d", &d);
			upd(1, 0, t-1, b, c, d);
		}
		else printf("%d\n", sum(1, 0, t-1, b, c));
	}
}

rkaxhdals 2년 전 0

25, 26번 라인에서, 범위에 포함되지 않아 자식 노드를 prop 해주지 않으면 문제가 발생할 수 있습니다.

아래와 같은 반례를 잘 생각해보시길 바랍니다.

pyeong 2년 전 0

헉 그렇네요 함수 호출횟수 줄여보겠다고 기본을 잊다니.. 감사합니다

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

문제

문제

출처

ICPC

레이지 프로퍼게이션으로 풀었는데 무엇이 잘못된걸까요..

pyeong 2년 전 0

rkaxhdals 2년 전 0

pyeong 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말