Submission #491593

#	Time	Username	Problem	Language	Result	Execution time	Memory
491593		blue	Diversity (CEOI21_diversity)	C++17	64 / 100	7050 ms	72004 KiB

diversity

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

const int maxN = 300'000;
const int maxQ = 50'000;

const int Sp = 300'000; //******

struct fenwick_tree
{
    vector<long long> BIT = vector<long long>(1+Sp, 0);

    void add(int L, int i, long long v)
    {
        for(int j = i; j <= Sp; j += j&-j)
            BIT[j] += v;
    }

    int rangesum(int L, int i)
    {
        long long res = 0;
        for(int j = i; j >= 1; j -= j&-j)
            res += BIT[j];

        return res;
    }
};

struct segtree
{
    int l;
    int r;
    long long lp = 0;
    long long sm = 0;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void add(int L, int R, long long V)
    {
        if(R < L) return;
        if(R < l || r < L) return;
        else if(L <= l && r <= R)
        {
            lp += V;
            sm += (r-l+1)*V;
        }
        else
        {
            sm += V*(min(R,r) - max(L,l) + 1);
            left->add(L, R, V);
            right->add(L, R, V);
        }
    }

    long long rangesum(int L, int R)
    {
        if(R < L) return 0;
        if(R < l || r < L) return 0;
        else if(L <= l && r <= R)
        {
            return sm;
        }
        else
        {
            return lp*(min(R,r) - max(L,l) + 1) + left->rangesum(L, R) + right->rangesum(L, R);
        }
    }
};





vector<int> a(1+maxN);
vector<int> l(1+maxQ), r(1+maxQ);

int L = 1;
int R = 0;

fenwick_tree ST;
segtree ST2(1, Sp);
segtree ST3(1, Sp);

vector<int> species_size(1+Sp);
vector<int> species_rank(1+Sp); //1 = center, S = edge
vector<int> rank_species(1+Sp);

vector<int> rank_pos(1+Sp);
vector<int> pos_rank(1+Sp);

vector<int> size_lowrank(1+maxN, -1), size_highrank(1+maxN, -1);

long long curr_ans = 0;

void add(int A)
{
    // cerr << "add " << A << '\n';
    int curr_size = species_size[A];
    // cerr << "curr_size = " << curr_size << '\n';
    int B = rank_species[ size_lowrank[ curr_size ] ];



    swap(rank_species[ species_rank[A] ], rank_species[ species_rank[B] ]);
    swap(species_rank[A], species_rank[B]);
    long long T = species_size[A];
    long long P = ST.rangesum(1, rank_pos[species_rank[A]] - 1);
    long long S = R-L+1 - P - T;

    curr_ans += ((T+1)*(T+2)/2) - (T*(T+1)/2);
    curr_ans += 2*P + 2*S;
    curr_ans += ST2.rangesum(1, rank_pos[species_rank[A]] - 2);
    curr_ans += ST3.rangesum(rank_pos[species_rank[A]] + 2, Sp);

    // cerr << "A = " << A << '\n';
    species_size[A]++;

    long long RP = rank_pos[ species_rank[A] ];
    ST.add(RP, RP, +1);
    ST2.add(RP, Sp, +1);
    ST3.add(1, RP, +1);

    if(size_lowrank[curr_size+1] > size_highrank[curr_size+1])
    {
        // cerr << "creating new\n";
        size_lowrank[curr_size+1] = size_highrank[curr_size+1] = size_lowrank[curr_size];
        size_lowrank[curr_size]++;
    }
    else
    {
        // cerr << "expanding old\n";
        size_highrank[curr_size+1]++;
        size_lowrank[curr_size]++;
    }
}

void remove(int A)
{
    // cerr << "remove " << A << '\n';
    int curr_size = species_size[A];
    int B = rank_species[ size_highrank[ curr_size ] ];

    swap(rank_species[ species_rank[A] ], rank_species[ species_rank[B] ]);
    swap(species_rank[A], species_rank[B]);

    species_size[A]--;
    int RP = rank_pos[ species_rank[A] ];
    ST.add(RP, RP, -1);
    ST2.add(RP, Sp, -1);
    ST3.add(1, RP, -1);

    long long T = species_size[A];
    long long P = ST.rangesum(1, rank_pos[species_rank[A]] - 1);
    long long S = R-L+1 - P - T;

    curr_ans -= ((T+1)*(T+2)/2) - (T*(T+1)/2);
    curr_ans -= 2*P + 2*S;
    curr_ans -= ST2.rangesum(1, rank_pos[species_rank[A]] - 2);
    curr_ans -= ST3.rangesum(rank_pos[species_rank[A]] + 2, Sp);

    if(size_lowrank[curr_size-1] > size_highrank[curr_size-1])
    {
        size_lowrank[curr_size-1] = size_highrank[curr_size-1] = size_highrank[curr_size];
        size_highrank[curr_size]--;
    }
    else
    {
        size_lowrank[curr_size-1]--;
        size_highrank[curr_size]--;
    }
}



int C;

const int rt = 500;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    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];

    vector<long long> answer(1+Q);

    vector<int> queries(Q);
    for(int j = 0; j < Q; j++) queries[j] = j+1;
    sort(queries.begin(), queries.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];
    });

    L = 1;
    R = 0;

    for(int s = 1; s <= Sp; s++)
    {
        species_size[s] = 0;
        species_rank[s] = s;
        rank_species[s] = s;
    }

    C = (1+Sp)/2;
    if(Sp % 2 == 0)
        C++;

    vector<int> P(Sp);
    for(int i = 0; i < Sp; i++) P[i] = i+1;
    sort(P.begin(), P.end(), [] (int u, int v)
    {
        if(abs(u - C) != abs(v - C)) return abs(u - C) < abs(v - C);
        else return u < v;
    });

    for(int i = 1; i <= Sp; i++)
    {
        rank_pos[i] = P[i-1];
        pos_rank[ P[i-1] ] = i;
    }

    size_lowrank[0] = 1;
    size_highrank[0] = Sp;
    for(int i = 1; i <= N; i++)
    {
        size_lowrank[i] = -1;
        size_highrank[i] = -2;
    }

    L = l[queries[0]];
    R = L-1;

    for(int j: queries)
    {
        while(R < r[j])
        {
            add(a[R+1]);
            R++;
        }

        while(r[j] < R)
        {
            R--;
            remove(a[R+1]);
        }

        while(l[j] < L)
        {
            add(a[L-1]);
            L--;
        }

        while(L < l[j])
        {
            L++;
            remove(a[L-1]);
        }

        answer[j] = curr_ans;
    }

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

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