27086 - 점수 내기

step 1

수학토끼가 내야 하는 금액은 $O(N)$에 구할 수 있으니 신경쓰지 맙시다.

$y=1$로 계산하고 마지막에 진짜 y를 곱해줍니다.

$(x, \lceil 2*10^5 / x \rceil)$ 크기의 배열을 생각해 봅시다. 점수가 $X_i$인 학생은 $(X_i\%x, \lfloor X_i/x\rfloor)$ 칸에 들어가 있습니다. 아래는 각 점수별로 어떤 칸에 들어가는지 표시해 두었습니다.

 

각 열마다 해당 열에 있는 사람들의 몫의 합과 그 열에 있는 사람의 수를 저장해 둡니다. 아래 그림에서 칸에 있는 숫자는 해당 칸에 해당하는 사람의 수입니다.

step 2

점수가 가장 낮은 사람을 봅시다. 이 사람은 모든 사람(같은 칸에 있는 사람 제외)과 비교를 해야 합니다. 어떤 칸에 사람이 있는지에 따라 내야 하는 금액이 달라집니다. 아래 표는 점수가 11인 사람 기준으로 내야 하는 금액을 적어 두었습니다.

점수가 11인 사람보다 왼쪽에 있는 사람과 아닌 사람으로 나눠봅시다. 저희는 각 열에 대해 몫의 합들을 다 구해 두었으니 이 값을 이용해 구할 수 있습니다.

 

왼쪽 : (왼쪽에 있는 모든 사람들의 몫의 합) - (점수가 11인 사람의 몫) * (왼쪽에 있는 사람 수)

오른쪽 : (오른쪽에 있는 모든 사람들의 몫의 합) - (점수가 11인 사람의 몫 - 1) * (오른쪽에 있는 사람 수)

이때 오른쪽이라고 쓰긴 했지만 같은 열이 있는 사람도 오른쪽에 포함된다 생각합시다.

같은 칸에 있는 값을 예외처리를 해 주면 됩니다.

 

계산이 끝나면 11에 해당하는 사람을 없애고 해당 열의 몫의 합과 사람 수를 바꿔줍니다.

몫의 합과 사람 수는 서그 트리나 인덱스 트리로 관리할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
long long int b[300000];
long long int it[1200000],t=1,cnt[1200000];
void up(long long int p, long long int v1, long long int v2) {
    it[p] += v1;
    cnt[p] += v2;
    while (p != 1) {
        p /= 2;
        it[p] += v1;
        cnt[p] += v2;
    }
}
long long int sum(long long int s, long long int e, long long int i, long long int x, long long int y) {
    if (x > y) return 0;
    if (x <= s && e <= y) return it[i];
    if (e < x || y < s) return 0;
    return sum(s, (s + e) / 2, i * 2, x, y) + sum((s + e) / 2 + 1, e, i * 2 + 1, x, y);
}
long long int sumc(long long int s, long long int e, long long int i, long long int x, long long int y) {
    if (x > y) return 0;
    if (x <= s && e <= y) return cnt[i];
    if (e < x || y < s) return 0;
    return sumc(s, (s + e) / 2, i * 2, x, y) + sumc((s + e) / 2 + 1, e, i * 2 + 1, x, y);
}
int main() {
    long long int n, x, y, i,d=0,tar=0;
    scanf("%lld%lld%lld", &n, &x, &y);
    while (t < x) t <<= 1;
    for (i = 1;i <= n;i++) {
        scanf("%lld", &b[i]);
        up(t - 1 + b[i] % x + 1, b[i] / x, 1);
    }
    tar = b[1];
    d = 0;
    sort(b + 1, b + n + 1);
    for (i = 1;i <= n;i++) {
        long long int countt = 0;
        while (1) {
            up(t - 1 + b[i] % x + 1, -(b[i] / x), -1);
            countt++;
            if (b[i] != b[i + 1]) break;
            i++;
        }
        long long int s1 = sum(1, t, 1, b[i] % x + 1, x);
        long long int c1 = sumc(1, t, 1, b[i] % x + 1, x);
        long long int s2 = it[1] - s1;
        long long int c2 = cnt[1] - c1;
        d += (s1 - b[i] / x * c1 + c1 + s2 - b[i] / x * c2)*countt;
        d %= 998244353;
    }
    printf("%lld ", d * y % 998244353);
    d = 0;
    for (i = 1;i <= n;i++) {
        if (tar < b[i]) {
            d += (b[i] - tar) / x + 1;
            d %= 998244353;
        }
    }
    printf("%lld", d * y % 998244353);
    return 0;
}