제출 #492961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492961		blue	Diversity (CEOI21_diversity)	C++17	4 / 100	3 ms	6988 KiB

diversity

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <deque>
using namespace std;

const int mx = 300'000;
const int mxQ = 50'000;
const int rt = 500;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define sz(x) (int(x.size()))

int N, Q;
vi a(1+mx);

vi l(1+mxQ), r(1+mxQ);
vll ans(1+mxQ);

int L = 1;
int R = 0;

vll ct(1+mx, 0);
vll freq(1+mx, 0);

vector<ll> sizes;
vector<bool> occ(1+mx, 0);


const ll bs = 1'000'000'000;
const int bc = 4;

struct largeint
{
    vll x = vll(bc, 0);

    largeint()
    {
        ;
    }

    largeint(ll k)
    {
        for(int u = 0; u < bc; u++)
        {
            x[u] += k%bs;
            k /= bs;
        }
    }

    ll get_long()
    {
        return x[0] + bs*x[1] + bs*bs*x[2];
    }
};

largeint operator + (largeint X, largeint Y)
{
    largeint res;
    for(int u = 0; u < bc; u++)
    {
        res.x[u] = X.x[u] + Y.x[u];
        if(u+1 < bc)
        {
            res.x[u+1] += res.x[u] / bs;
            res.x[u] %= bs;
        }
    }
    return res;
}

largeint operator - (largeint X, largeint Y)
{
    largeint res;
    for(int u = 0; u < bc; u++)
    {
        res.x[u] = X.x[u] - Y.x[u];
        if(res.x[u] < 0)
        {
            res.x[u] += bs;
            res.x[u+1] -= 1;
        }
    }
    return res;
}

largeint operator * (largeint X, largeint Y)
{
    largeint res;
    for(int u = 0; u < bc; u++)
    {
            for(int v = 0; v < bc; v++)
            {
                if(u+v >= bc) continue;

                res.x[u+v] += X.x[u] * Y.x[v];
                if(res.x[u+v] >= bs)
                {
                    res.x[u+v+1] += res.x[u+v]/bs;
                    res.x[u+v] %= bs;
                }
            }
    }

    for(int u = 0; u+1 < bc; u++)
    {
        if(u+1 < bc)
        {
            res.x[u+1] += res.x[u] / bs;
            res.x[u] %= bs;
        }
    }

    return res;

    // for(int u = 0; u < bc; u++)
    // {
    //     res.x[u] = X.x[u] + Y.x[u];
    //     if(u+1 < bc)
    //     {
    //         res.x[u+1] += res.x[u] / bs;
    //         res.x[u] %= bs;
    //     }
    // }
}





largeint ap_sum(ll a, ll d, ll n)
{
    return largeint((n * (2*a + (n-1)*d))/2);
}

largeint ap_sq_sum(ll a, ll d, ll n)
{
    /*
    a^2 + (a+d)^2 + ... + (a+(n-1)*d)^2
    = n * a^2   +   2*a*(0d + 1d + ... + (n-1)d)   +   0d^2 + d^2 + ... (n-1)d ^ 2
    = n*a^2  +  2*a*d * (n-1)*n/2   +   d^2 * (n-1)*(n)*(2n-1)/6
    */
    // assert(d*n <= 300'000);
    // assert(d*d*n*n*2*n <= 1'000'000'000'000'0000);

    return largeint(n*a*a  +  a*d*(n-1)*n)   +   largeint(d*d)*largeint(((n-1)*n*(2*n-1))/6LL);
}




ll get_ans()
{
    vector<ll> sizes2;
    for(ll s: sizes)
    {
        if(occ[s]) continue;
        if(freq[s] == 0) continue;
        sizes2.push_back(s);
        occ[s] = 1;
    }
    sizes = sizes2;
    sizes2.clear();
    for(ll s: sizes) occ[s] = 0;

    sort(sizes.begin(), sizes.end(), [] (int u, int v)
    {
        return u > v;
    });

    deque< pair<ll, ll> > ord;
    int z = 0;
    for(ll s: sizes)
    {
        if(freq[s] % 2 == 1)
        {
            if(z) ord.push_back({s, 1});
            else ord.push_front({s, 1});
            z = !z;
        }

        if(freq[s]/2)
        {
            ord.push_back({s, freq[s]/2});
            ord.push_front({s, freq[s]/2});
        }
    }
    ord.push_front({0, 0});

    largeint ans(0);
    ll tot = 0;

    int P = sz(ord);
    vll prefsum(1+P, 0);
    for(int i = 1; i <= P; i++)
    {
        prefsum[i] = prefsum[i-1] + (ord[i].first * ord[i].second);
    }
    tot = prefsum[P];

    for(int i = 1; i <= P; i++)
    {
        ans = ans + largeint(ord[i].second) * largeint((ord[i].first * (ord[i].first + 1))/2);
        ans = ans + largeint(ord[i].second * largeint(largeint(ord[i].first) * (largeint(tot) - largeint(ord[i].first))));
        ans = ans + largeint((tot - ord[i].first) * ap_sum(prefsum[i-1], ord[i].first, ord[i].second));
        ans = ans - ap_sq_sum(prefsum[i-1], ord[i].first, ord[i].second);
    }

    return ans.get_long();
}

void add_species(int a)
{
    freq[ct[a]]--;
    ct[a]++;
    freq[ct[a]]++;
    sizes.push_back(ct[a]);
}

void remove_species(int a)
{
    freq[ct[a]]--;
    ct[a]--;
    freq[ct[a]]++;
    sizes.push_back(ct[a]);
}

void expand_right()
{
    R++;
    add_species(a[R]);
}

void expand_left()
{
    L--;
    add_species(a[L]);
}

void contract_right()
{
    remove_species(a[R]);
    R--;
}

void contract_left()
{
    remove_species(a[L]);
    L++;
}

int main()
{
    cin >> N >> Q;
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int j = 1; j <= Q; j++) cin >> l[j] >> r[j];

    vi I(Q);
    for(int j = 0; j < Q; j++) I[j] = j+1;
    sort(I.begin(), I.end(), [] (int u, int v)
    {
        if(l[u]/rt != l[v]/rt) return l[u]/rt < l[v]/rt;
        else return r[u] < r[v];
    });

    freq[0] = mx;

    for(int q: I)
    {
        while(R < r[q]) expand_right();
        while(L > l[q]) expand_left();
        while(R > r[q]) contract_right();
        while(L < l[q]) contract_left();
        ans[q] = get_ans();
    }

    for(int q = 1; q <= Q; q++) cout << ans[q] << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36