BOJ)8462 배열의 힘

문제: icpc.me/8462

시퀀스와 쿼리가 주어질 때 매 쿼리에 대한 답을 출력하는 문제이다.

쿼리는 구간이 주어지면 구간에 존재하는 모든 자연수 s에 대하여 (s 의 개수의 제곱) x s를 합한 값이다.

쿼리와 시퀀스가 10만이기 때문에 적어도 쿼리를 log나 root 시간에 처리해주고 싶지만 안타깝게도 저 쿼리를 해당 시간에 처리하기는 힘든거 같다.

하지만 쿼리 도중에 업데이트가 일어나지 않기 때문에 쿼리를 정렬한 뒤 mo's 알고리즘으로 접근한다면 해답을 얻을 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, m, a[100010], sz, cnt[1000010], curr, ans[100010];
struct qry {
    ll lo, hi, idx;
    qry(ll lo, ll hi, ll idx) :lo(lo), hi(hi), idx(idx) {};
    qry() {}
    bool operator<(const qry& x){
        ll lidx = hi / sz;
        ll ridx = x.hi / sz;
        return lidx == ridx ? lo < x.lo : lidx < ridx;
    }
}q[100010];
void add(ll num) {
    curr -= cnt[num] * cnt[num] * num;
    cnt[num]++;
    curr += cnt[num] * cnt[num] * num;
}
void erase(ll num) {
    curr -= cnt[num] * cnt[num] * num;
    cnt[num]--;
    curr += cnt[num] * cnt[num] * num;
}
int main() {
    scanf("%d%d", &n, &m);
    sz = sqrt(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        q[i] = qry(x - 1, y - 1, i);
    }
    sort(q, q + m);
    ll lo = 0, hi = 0;
    add(a[0]);
    for (int i = 0; i < m;i++) {
        auto &next = q[i];
        ll nlo = next.lo, nhi = next.hi;
        for (int i = lo; i < nlo; i++)
            erase(a[i]);
        for (int i = lo - 1; i >= nlo; i--)
            add(a[i]);
        for (int i = hi + 1; i <= nhi; i++)
            add(a[i]);
        for (int i = hi; i > nhi; i--)
            erase(a[i]);
        lo = nlo;
        hi = nhi;
        ans[next.idx] = curr;
    }
    for (int i = 0; i < m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}