글 읽기 - c++] 어디가 틀렸는지 모르겠습니다.

hello70825 4년 전 0

C++로 세그먼트 트리를 짜서 만들었는데 게시판에 있는 반례도 맞고, 제가 만든 반례도 정답대로 나오는데 어디가 틀린지 잘 모르겠습니다.

오버플로우 나올까봐 나오는 값들 족족 %MOD를 해놔서 오버플로우가 나올 것 같진 않은데 제가 놓친 것이 있을까요?

Seg_cnt는 어떤 좌표에 나무를 심은 개수, Seg_sum은 0으로부터 어떤 좌표까지의 거리입니다.(같은 좌표에 나무가 2개 있으면 그 좌표만큼 더해줍니다.)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,i,k;
ll ans,a,b;
int MAX=200000;
ll MOD=1000000007;


struct Segment{
    vector<ll> tree;
    Segment(int x){
        int h = (int)ceil(log2(x));
        tree.resize(1<<(h+1),0);
    }
    ll update(int now, int s, int e, int idx, int val){
        if(s>idx || e<idx) return tree[now];
        if(s==e){
            tree[now]=(tree[now]+val)%MOD;
            return tree[now];
        }
        int mid=(s+e)/2;
        return tree[now]=(update(now*2,s,mid,idx,val)%MOD+update(now*2+1,mid+1,e,idx,val)%MOD)%MOD;
    }
    ll Find(int now,int s,int e,int L,int R){
        if(R<s || L>e) return 0;
        if(L<=s && e<=R) return tree[now];
        int mid=(s+e)/2;
        return (Find(now*2,s,mid,L,R)%MOD+Find(now*2+1,mid+1,e,L,R)%MOD)%MOD;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    ans=1;
    Segment Seg_sum(MAX+1);
    Segment Seg_cnt(MAX+1);
    for(i=0; i<n;i++){
        cin >> k;
        Seg_sum.update(1,0,MAX,k,k);
        Seg_cnt.update(1,0,MAX,k,1);
        if(i==0) continue;
        a = (Seg_cnt.Find(1,0,MAX,0,k-1)*k-Seg_sum.Find(1,0,MAX,0,k-1))%MOD;
        b = (Seg_sum.Find(1,0,MAX,k+1,MAX)-Seg_cnt.Find(1,0,MAX,k+1,MAX)*k)%MOD;
        ans=(ans*(a+b))%MOD;
    }
    cout << ans << "\n";
}

crypt9 4년 전 3

update 와 Find 함수에서 %MOD 를 삭제하면 잘되네요.

거리들의 합이 정확하게 계산되어야 하는데, 상위 노드로 올라가면서 %MOD 를 취해서 값이 작아 질 수 있습니다.

값이 왜곡되어 거리 합이 정확하지 않게 될 것 같네요.

tjswns1542 4년 전 0

crypt9님 덕분에 며칠동안 풀지 못했던 문제를 해결했습니다..

200000*200000 수준은 ll범위에서 커버가 되니까

부분합 만드는 부분들에서는 굳이 mod를 할 필요가 없었고

했어도 데이터가 이상해지는군요.. 어찌됐든 최후 연산에서 mod를 하기때문에

아무 상관없다고 생각했는데

그부분에 대해서는 좀더 생각해보고 아무튼 댓글 너무 감사드립니다!

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

문제

문제

출처

ICPC

c++] 어디가 틀렸는지 모르겠습니다.

hello70825 4년 전 0

crypt9 4년 전 3

tjswns1542 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말