Submission #1155626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155626		ace5	Diversity (CEOI21_diversity)	C++20	100 / 100	1265 ms	9912 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


const int maxn = 300005;
const int sqr = 1000;
const int pos1 = 150002;
const int maxq = 50005;

map<int,int> el;
ll a[maxn];
ll neq[maxn];
int val[maxn];
int vale[maxn];
int nxt[maxn+1],prv[maxn+1];
int L = 0,R = -1;

struct block
{
    block(int _l,int _r,ll _sum,ll _wsum,ll _ans){l = _l,r = _r;sum = _sum;wsum = _wsum;ans = _ans;};
    block(){};
    int l,r;
    ll sum;
    ll wsum;
    ll ans;
};

block mrg(block a,block b)
{
    block ans;
    ans.sum = a.sum + b.sum;
    ans.wsum = a.wsum + b.wsum + b.sum * (a.r-a.l+1);
    ans.ans = a.ans + b.ans + a.sum * (b.wsum + b.sum) + (a.sum * (a.r-a.l+1) - a.wsum) * b.sum;
    ans.l = a.l;
    ans.r = b.r;
    return ans;
}
int get_pos(int tpos,int sz)
{
    int d = (sz-tpos)/2;
    return pos1 + (sz%2 == tpos%2 ? -d : d);
}

ll get(int l,int r)
{
    int tl = pos1 + 1,tr = pos1;
    int tnum = maxn;
    deque<block> blocks;
    int tst = prv[maxn];
    while(tst != 0)
    {
        ll e = tst;
        ll f = vale[tst];
       // cout << e << ' ' << f << endl;
        tnum -= f;
        int lg = get_pos(tnum,maxn),rg = get_pos(tnum+1,maxn);
        if(lg > rg)
        {
            swap(lg,rg);
        }
        if(lg != tl)
        {
            ll len = tl-lg;
            blocks.push_front(block(lg,tl-1,e*len,e * len * (len + 1) / 2,len * e * (e + 1) / 2 + e*e*neq[len]));
        }
        if(rg != tr)
        {
            ll len = rg-tr;
            blocks.push_back(block(tr+1,rg,e*len,e * len * (len + 1) / 2,len * e * (e + 1) / 2 + e*e*neq[len]));
        }
        tl = lg;
        tr = rg;
        tst = prv[tst];
    }
    block ans = blocks[0];
    for(int j =1;j < blocks.size();++j)
    {
        ans = mrg(ans,blocks[j]);
    }
    return ans.ans;
}

void add(int x)
{
    int t = val[x];
    if(vale[t] == 1 && vale[t+1] == 0)
    {
        nxt[t+1] = nxt[t];
        if(nxt[t] != -1)
        {
            prv[nxt[t]] = t+1;
        }
        prv[t+1] = prv[t];
        if(prv[t] != -1)
        {
            nxt[prv[t]] = t+1;
        }
        nxt[t] = -1;
        prv[t] = -1;
    }
    if(vale[t] > 1 && vale[t+1] == 0)
    {
        nxt[t+1] = nxt[t];
        if(nxt[t] != -1)
        {
            prv[nxt[t]] = t+1;
        }
        prv[t+1] = t;
        nxt[t] = t+1;
    }
    if(vale[t] == 1 && vale[t+1] > 0)
    {
        prv[t+1] = prv[t];
        if(prv[t] != -1)
        {
            nxt[prv[t]] = t+1;
        }
        nxt[t] = -1;
        prv[t] = -1;
    }
    vale[val[x]] --;
    val[x]++;
    vale[val[x]]++;
}
void sub(int x)
{
    int t = val[x];
    if(vale[t] == 1 && vale[t-1] == 0)
    {
        prv[t-1] = prv[t];
        if(prv[t] != -1)
        {
            nxt[prv[t]] = t-1;
        }
        nxt[t-1] = nxt[t];
        if(nxt[t] != -1)
        {
            prv[nxt[t]] = t-1;
        }
        nxt[t] = -1;
        prv[t] = -1;
    }
    if(vale[t] > 1 && vale[t-1] == 0)
    {
        prv[t-1] = prv[t];
        if(prv[t] != -1)
        {
            nxt[prv[t]] = t-1;
        }
        nxt[t-1] = t;
        prv[t] = t-1;
    }
    if(vale[t] == 1 && vale[t-1] > 0)
    {
        nxt[t-1] = nxt[t];
        if(nxt[t] != -1)
        {
            prv[nxt[t]] = t-1;
        }
        nxt[t] = -1;
        prv[t] = -1;
    }
    vale[val[x]] --;
    val[x]--;
    vale[val[x]]++;
}

ll res[maxq];

struct query
{
    query(int _l,int _r,int _i){l = _l;r = _r;i = _i;};
    query(){};
    int l,r,i;
    bool operator < (const query & oth){return (l/sqr != oth.l/sqr ? l/sqr < oth.l/sqr : r < oth.r);};
};

vector<query> ev;

void go_ll()
{
    L--;
    add(a[L]);
}
void go_lr()
{
    sub(a[L]);
    L++;
}
void go_rr()
{
    R++;
    add(a[R]);
}
void go_rl()
{
    sub(a[R]);
    R--;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    block sb = block(0,0,1,1,0);
    neq[1] = sb.ans;
    vale[0] = maxn;
    for(int j = 1;j < maxn;++j)
    {
        prv[j] = 0;
        nxt[j] = maxn;
    }
    prv[0] = -1;
    nxt[0] = maxn;
    prv[maxn] = 0;
    nxt[maxn] = -1;
    for(int j = 2;j < maxn;++j)
    {

        sb = mrg(sb,block(j-1,j-1,1,1,0));
        neq[j] = sb.ans;
    }
    for(int i = 0;i < n;++i)
    {
        cin >> a[i];
    }
    for(int i = 0;i < q;++i)
    {
        int l,r;
        cin >> l >> r;
        l--;
        r--;
        ev.push_back(query(l,r,i));
    }
    sort(ev.begin(),ev.end());
    for(int i = 0;i < ev.size();++i)
    {
        int tl = ev[i].l;
        int tr = ev[i].r;
        while(L > tl)
        {
            go_ll();
        }
        while(R < tr)
        {
            go_rr();
        }
        while(L < tl)
        {
            go_lr();
        }
        while(R > tr)
        {
            go_rl();
        }
        res[ev[i].i] = get(0,maxn-1);
    }
    for(int i= 0 ;i < q;++i)
    {
        cout << res[i] << "\n";
    }
    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