제출 #1182047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182047		Mighilon	Diversity (CEOI21_diversity)	C++20	100 / 100	2692 ms	9976 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){
    // dbg(n,a,b)
    return n*a*a+2LL*sum1(n-1)*a*b+sum2(n-1)*b*b;
}

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


//#define _c(i) assert(i>=0&&i<mxN);
#define _c(i)
ll sol(int L, int R){
    assert(min(L,R)>=0&&max(L,R)<N);
    int n=R-L+1;
    int len=0;
    F0Rd(i,oplen){
        _c(op[i].s);
        if(used[op[i].s])continue;
        used[op[i].s]=1;
        _c(len);
        if(op[i].f==1)act[len++]=op[i].s;
    }
    F0R(i,p_len){
        _c(p_act[i]);
        if(used[p_act[i]])continue;
        used[p_act[i]]=1;
        _c(len);
        act[len++]=p_act[i];
    }
    F0R(i,oplen){
        _c(op[i].s);
        used[op[i].s]=0;
    }
    F0R(i,p_len){
        _c(p_act[i]);
        used[p_act[i]]=0;
    }
    p_len=len;
    F0R(i,len){
        _c(i);
        p_act[i]=act[i];
    }
    sort(act,act+len);// sort on f
    // F0R(i,len){
    //     dbg(act[i],ff[act[i]]);
    // }
    int l=0,r=0,tot=0;
    ll ans=0;
    F0R(i,len){
        _c(act[i]);
        _c(i);
        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);
        // dbg(ans)
        ans+=sum(tol,n-l-sz*tol,sz);
        // dbg(ans)
        ans+=sum(tor,r,sz);
        // dbg(ans)
        ans+=sum(tor,n-r-sz*tor,sz);
        // dbg(ans)
        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;
    }
    F0R(i,N){
        dbg(a[i])
    }
    vi id(Q);
    iota(all(id),0);
    dbg(id)
    dbg(Q)
    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; 
    });
    dbg(id)
    vl ans(mxN);
    int l=0,r=-1;
    dbg(Q)
    F0R(_i,Q){
        dbg(_i)
        int i=id[_i];
        dbg(i)
        dbg(q[i])
        oplen=0;
        int L=q[i].f-1;
        int R=q[i].s-1;
        while(l>L) {
            add(--l);
            dbg("add l ", l);
        }
        while(r<R) {
            add(++r);
            dbg("add r ", r);
        }
        while(l<L) {
            dec(l++);
            dbg("dec l ", l);
        }
        while(r>R) {
            dec(r--);
            dbg("dec r ", r);
        }
        assert(l==L&&r==R);
        dbg(l,r,L,R)
        ans[i]=sol(l,r);
        dbg(_i)
    }
    F0R(i,Q)cout<<ans[i]<<nl;
    cout.flush();
}
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