#include <stdio.h>#include <iostream>#define MAX 100010using namespace std;long long t[4*MAX];void update(int n,int s,int e,int p, long long v){ if(p<s || p>e)return; if(s==e)t[n] = v; else{ update(2*n,s,(s+e)/2,p,v); update(2*n+1,(s+e)/2+1,e,p,v); t[n] = t[2*n]+t[2*n+1]; }} long long sum(int n,int s,int e,int l,int r){ if(e<l || r<s)return 0; if(l<=s && e<=r)return t[n]; return sum(2*n,s,(s+e)/2,l,r)+sum(2*n+1,(s+e)/2+1,e,l,r);} int main(){ int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;++i){ int x; scanf("%d",&x); update(1,1,n,i,x); } for(int i=0;i<q;++i){ int x,y,a,b; scanf("%d%d%d%d",&x,&y,&a,&b); printf("%lld\n",sum(1,1,n,x,y)); update(1,1,n,a,b); } return 0;}
그냥 보통 구간 트리로 푸는 문제라고 생각 했는데 계속 틀리다는 답이 뜨네요. 구간 합 구하기 문제와
동일하게 풀면 될것 같았는데 안되네요 ㅠㅠ 어떤점이 잘못 되었을까요.
이거 x > y 인 데이터도 들어오네요 ㅡㅡ;; 그 부분을 직접 고쳐서 제출해보니 맞았습니다.
이걸 문제에 명시를 하든지 아니면 데이터를 수정하든지 해야할 것 같습니다 백준님... @baekjoon
그거 출제저의 의도라고 합니다....
헐...
댓글을 작성하려면 로그인해야 합니다.
ainch96 8년 전
#include <stdio.h>
#include <iostream>
#define MAX 100010
using namespace std;
long long t[4*MAX];
void update(int n,int s,int e,int p, long long v){
if(p<s || p>e)return;
if(s==e)t[n] = v;
else{
update(2*n,s,(s+e)/2,p,v);
update(2*n+1,(s+e)/2+1,e,p,v);
t[n] = t[2*n]+t[2*n+1];
}
}
long long sum(int n,int s,int e,int l,int r){
if(e<l || r<s)return 0;
if(l<=s && e<=r)return t[n];
return sum(2*n,s,(s+e)/2,l,r)+sum(2*n+1,(s+e)/2+1,e,l,r);
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
update(1,1,n,i,x);
}
for(int i=0;i<q;++i){
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
printf("%lld\n",sum(1,1,n,x,y));
update(1,1,n,a,b);
}
return 0;
}
그냥 보통 구간 트리로 푸는 문제라고 생각 했는데 계속 틀리다는 답이 뜨네요. 구간 합 구하기 문제와
동일하게 풀면 될것 같았는데 안되네요 ㅠㅠ 어떤점이 잘못 되었을까요.