글 읽기 - 펜윅트리를 어떤식으로 적용해야할지 감이 안옵니다...

zmfldlwl 6년 전 1

예를 들어

3 2 0 4 1

과 같이 정렬되지 않은 input이 들어오게된다면...

결과값을 계산해보면

1 + 3

1 + 2 + 4

2 + 1 + 1 + 3

1 * 4 * 7 * 7 = 196이라는 output이 나와야 합니다.

그런데, 각 구간의 거리들이 모두 독립적인 값들이라서 그 다음 값들에 영향을 미치지 않을거 같아서...

펜윅을 어떤식으로 적용시켜서 문제를 풀어가는 로직을 구상해야할지 감이 안오네요...

하루종일 보고 있어서 제자리걸음인거 같아서 질문 올립니다...

chogahui05 6년 전 3

x번째 나무를 loc의 위치에 심어야 한다고 해 봅시다.

(1) loc보다 크거나 같은 좌표에 있는 나무들의 갯수 : x개

(2) loc보다 크거나 같은 좌표에 있는 나무들의 좌표의 합 : sum_one

(3) loc보다 작은 좌표에 있는 나무들의 갯수 : y개

(4) loc보다 작거나 같은 좌표에 있는 나무들의 좌표의 합 : sum_two

현재 기준점은 loc입니다.

loc보다 크거나 같은 경우에는 나무 좌표 - loc이 거리가 되겠네요.

각 나무마다 loc을 빼기 때문에

sum_one - loc * x이 되고요.

loc보다 작은 나무들은

(loc - 나무 좌표)가 거리가 되는데요.

이건 loc * y - sum_two로 계산할 수 있죠.

예를 들어서

[3 2 0 4] 1

이 있다고 가정하고, 1에 나무를 심는다고 가정해 봅시다.

그러면 1보다 크거나 같은 나무의 갯수는 3 = x

그것들의 좌표의 합은 9 = sum_one

1보다 작은 나무의 갯수 1 = y

그것들의 좌표의 합은 0입니다. = sum_two

현재 loc = 1이고요.

sum_one - loc * x + loc * y - sum_two에 대입하면

9 - 1 * 3 + 1 * 1 - 0 = 9 - 3 + 1 = 7이 됩니다.

zmfldlwl 6년 전 0

짠다고 짜봤는데... 계속 틀렷다고만 나오네요 ㅠㅠ

질문글들에 올려주신 인풋들도 제대로 결과가 뜨는데 ...

후 도대체 어떤 경우에 터지는 걸까요...

#include <iostream>

#define MOD 1000000007
#define MMAX 200005

using namespace std;

class fenwick
{
public:
    int fw[MMAX];

    fenwick()
    {
        for (int i = 0; i < MMAX; i++)
            fw[i] = 0;
    }

    void update(int pos, int value)
    {
        while (pos < MMAX)
        {
            fw[pos] = (fw[pos] + value) % MOD;
            
            pos += (pos & -pos);
        }
    }

    int sum(int pos)
    {
        int res = 0;

        while (pos > 0)
        {
            res = (res + fw[pos]) % MOD;

            pos -= (pos & -pos);
        }

        return res;
    }
};

int arr[MMAX];

fenwick compare_fw = fenwick();
fenwick sum_fw = fenwick();

int main()
{
    int n = 0;
    cin >> n;

    cin >> arr[1];
    arr[1]++;

    //갯수 세기위한 펜윅
    compare_fw.update(arr[1], 1);
    //누적합 구하기 위한 펜윅
    sum_fw.update(arr[1], arr[1] - 1);

    long long total = 1;

    if (n == 1)
        total = 0;

    for (int i = 2; i <= n; i++)
    {
        cin >> arr[i];
        arr[i]++;

        compare_fw.update(arr[i], 1);
        sum_fw.update(arr[i], arr[i] - 1);

        //입력된 값들 중에 arr[i]보다 큰 값들 갯수 샌다.
        int count1 = compare_fw.sum(MMAX) - compare_fw.sum(arr[i]);
        //입력된 값들 중에 arr[i]보다 작은값들 갯수 샌다.
        int count2 = compare_fw.sum(arr[i] - 1);

        //입력된 값들 중에 arr[i]보다 큰 값들 누적합 구한다.
        int sum1 = sum_fw.sum(MMAX) - sum_fw.sum(arr[i]);
        //입력된 값들 중에 arr[i]보다 작은 값들 누적합 구한다.
        int sum2 = sum_fw.sum(arr[i] - 1);

        int temp1 = (sum1 - (((arr[i] - 1) * count1) % MOD)) % MOD;
        int temp2 = (((arr[i] - 1) * count2) % MOD - sum2) % MOD;

        total = total * (temp1 + temp2) % MOD;
    }

    cout << total << endl;

    return 0;
}

chogahui05 6년 전 0

오버플로우 체크해 보셨나요?

zmfldlwl 6년 전 0

오버플로우가 터졌었네요...

한 100개넣엏을때 안터지길래 ㅠㅠ 못찾앗는데

패스했습니다! 감사합니다.

wondy1128 6년 전 1

3 2 0 4 1

과 같이 정렬되지 않은 input이 들어오게된다면...

결과값을 계산해보면

1 + 3

1 + 2 + 4

2 + 1 + 1 + 3

1 * 4 * 7 * 7 = 196이라는 output이 나와야 합니다.

1*5*7*7

245 가 나와야합니다.

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ저 입력으로 계속 해보고, 계산 안해보고 196 안나오길래 코드 한시간동안봤습니다ㅋㅋㅋㅋㅋㅋ

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

문제

문제

출처

ICPC

펜윅트리를 어떤식으로 적용해야할지 감이 안옵니다...

zmfldlwl 6년 전 1

chogahui05 6년 전 3

zmfldlwl 6년 전 0

chogahui05 6년 전 0

zmfldlwl 6년 전 0

wondy1128 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말