글 읽기 - 왜 틀렸는지 모르겠습니다 ㅠ 반례 좀 부탁 드립니다.

nkon 6년 전 0

펜윅 트리 구간 합을 통해 풀었는데 8%에서 틀렸다고 나오네요.

Long으로도 바꿔보고 , 질문 검색해서 함정(x y)도 처리 했는데

반례를 못찾겠네요..

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
        public static int N,M;
        public static int arr[];
        public static void main(String[] args) throws Exception {

                    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            
                    StringTokenizer stk = new StringTokenizer(br.readLine());
                    
                    N = Integer.parseInt(stk.nextToken());
                    M = Integer.parseInt(stk.nextToken());
                    
                    stk = new StringTokenizer(br.readLine());
                    
                    arr = new int[N+1];
                    
                    Ftree ftree = new Ftree(N);
                    
                    for(int i=1;i<=N;i++){
                                    arr[i] = Integer.parseInt(stk.nextToken());
                                    ftree.add(i, arr[i]);
                    }
                    
                    
                    for(int i=1;i<=M;i++){
                                    stk = new StringTokenizer(br.readLine());
                                    int from = Integer.parseInt(stk.nextToken());
                                    int to   = Integer.parseInt(stk.nextToken());
                                    
                                    long cum  = ftree.cum(from,to);
                                    
                                    System.out.println(cum);
                                    
                                    int idx  = Integer.parseInt(stk.nextToken());
                                    int val  = Integer.parseInt(stk.nextToken());
                                    
                                    int diff = val - arr[idx];
                                    arr[idx] = val;
                                    ftree.add(idx, diff);
                    }
        }
}
class Ftree{
        long tree[];
        int N;
        public Ftree(int N) {
                    this.N = N;
                    tree   = new long[N+1];
        }
        
        public void add(int pos,long val){
                    while(pos < tree.length){
                                    tree[pos] += val;
                                    pos += (pos&-pos);
                    }
        }
        
        public long cum(int pos){
                    long ret =0;
                    while(pos > 0){
                                    ret +=tree[pos];
                                    pos &= (pos-1);
                    }
                    return ret;
        }
        
        public long cum(int from,int to){
            if(from > to){
                            int temp = to;
                            to = from;
                            from = temp;
            }
                    return cum(to) - cum(from-1);
        }
    
        @Override
        public String toString() {
                    return "Ftree [tree=" + Arrays.toString(tree) + ", N=" + N + "]";
        }
}

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다 ㅠ 반례 좀 부탁 드립니다.

nkon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말