Submission #1182048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182048		Mighilon	Diversity (CEOI21_diversity)	C++20	100 / 100	2519 ms	9904 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const ll MOD = 998244353;
const int mxN = 3e5+5;

int N,Q,B,ff[mxN],oplen,act[mxN],p_act[mxN],used[mxN],p_len;
int a[mxN],f[mxN];
pi op[4*mxN],q[mxN];
ll sum1(ll n){
    return n*(n+1)/2;
}
ll sum2(ll n){
    return n*(n+1)*(2*n+1)/6;
}
// a^2 + (a+b)^2 + (a+2b)^2 + (a+3b)^2 ... n times
ll sum(ll n,ll a,ll b){
    return n*a*a+2LL*sum1(n-1)*a*b+sum2(n-1)*b*b;
}

void add(int i){
    ff[f[a[i]]]--;
    if(ff[f[a[i]]]==0)op[oplen++]={-1,f[a[i]]};//--
    f[a[i]]++;
    ff[f[a[i]]]++;
    if(ff[f[a[i]]]==1)op[oplen++]={1,f[a[i]]};//++
}
void dec(int i){
    ff[f[a[i]]]--;
    if(ff[f[a[i]]]==0)op[oplen++]={-1,f[a[i]]};//--
    f[a[i]]--;
    ff[f[a[i]]]++;
    if(ff[f[a[i]]]==1)op[oplen++]={1,f[a[i]]};//++
}


ll sol(int L, int R){
    int n=R-L+1;
    int len=0;
    F0Rd(i,oplen){
        if(used[op[i].s])continue;
        used[op[i].s]=1;
        if(op[i].f==1)act[len++]=op[i].s;
    }
    F0R(i,p_len){
        if(used[p_act[i]])continue;
        used[p_act[i]]=1;
        act[len++]=p_act[i];
    }
    F0R(i,oplen){
        used[op[i].s]=0;
    }
    F0R(i,p_len){
        used[p_act[i]]=0;
    }
    p_len=len;
    F0R(i,len){
        p_act[i]=act[i];
    }
    sort(act,act+len);// sort on f
    int l=0,r=0,tot=0;
    ll ans=0;
    F0R(i,len){
        int tol=0,tor=0,nr=ff[act[i]],sz=act[i];
        if(tot%2==0){
            tol+=(nr+1)/2;
            tor+=nr/2;
        }
        else{
            tor+=(nr+1)/2;
            tol+=nr/2;
        }
        ans+=sum(tol,l,sz);
        ans+=sum(tol,n-l-sz*tol,sz);
        ans+=sum(tor,r,sz);
        ans+=sum(tor,n-r-sz*tor,sz);
        l+=tol*sz;
        r+=tor*sz;
        tot+=nr;
    }
    return (1LL*n*(n+1)*tot-1LL*n*(tot-1)-ans)/2;
}


void solve(){
    cin>>N>>Q;
    B=ceil(sqrt(N));
    F0R(i,N)cin>>a[i];
    F0R(i,Q){
        cin>>q[i].f>>q[i].s;
    }
    { // compress
        vi tmp(mxN);
        F0R(i,N)tmp[a[i]]++;
        int c=0;
        F0R(i,mxN)if(tmp[i])tmp[i]=c++;
        F0R(i,N)a[i]=tmp[a[i]];
        ff[0]=c;
    }
    vi id(Q);
    iota(all(id),0);
    sort(all(id),[&](int i, int j){
        // dbg(i,j)
        // assert(i>=0&&j>=0&&i<Q&&j<Q);
        if(q[i].f/B==q[j].f/B)
            return q[i].s<q[j].s; 
        return q[i].f/B<q[j].f/B; 
    });
    vl ans(mxN);
    int l=0,r=-1;
    F0R(_i,Q){
        int i=id[_i];
        oplen=0;
        int L=q[i].f-1;
        int R=q[i].s-1;
        while(l>L) {
            add(--l);
        }
        while(r<R) {
            add(++r);
        }
        while(l<L) {
            dec(l++);
        }
        while(r>R) {
            dec(r--);
        }
        ans[i]=sol(l,r);
    }
    F0R(i,Q)cout<<ans[i]<<nl;
}
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

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