Submission #1051069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051069		PoonYaPat	Diversity (CEOI21_diversity)	C++14	64 / 100	7072 ms	227012 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MX=300000,sq=1350;
int MID,mx=1;

struct NN {
    ll sum,sl,sr,cnt;
} s[1<<21];

NN merge(NN a, NN b) {
    NN res;
    res.sum=a.sum+b.sum;
    res.cnt=a.cnt+b.cnt;
    res.sl=a.sl+a.cnt*b.sum+b.sl;
    res.sr=b.sr+b.cnt*a.sum+a.sr;
    return res;
}

ll fast2_query(int l, int r, int idx, int x, int val) {
    if (x>r) return s[idx].sr+s[idx].sum*(ll)(x-r);
    if (x<l) return s[idx].sl+s[idx].sum*(ll)(l-x);
    if (l==r) {
        if (val==0) s[idx]={0,0,0,0};
        else s[idx]={val,val,val,1};
        return val;
    }
    int mid=(l+r)/2;
    ll res1=fast2_query(l,mid,2*idx,x,val);
    ll res2=fast2_query(mid+1,r,2*idx+1,x,val);
    s[idx]=merge(s[2*idx],s[2*idx+1]);
    return res1+res2;
}

int have[MX+5],idx_seq=-1;
vector<int> seq;
deque<int> dq[MX+5];
ll ans=0;
ll lcnt,rcnt;
ll L=MID,R=MID;

ll cal_left(int pos) {
    return lcnt*(lcnt+1)/2 + (s[1].sl+s[1].sum*(L-pos)) + (rcnt*(rcnt+1)/2+rcnt*(R+1-pos));
}

ll cal_right(int pos) {
    return rcnt*(rcnt+1)/2 + (s[1].sr+s[1].sum*(pos-R)) + (lcnt*(lcnt+1)/2+lcnt*(pos-L+1));
}

ll cal_mid(int pos, int val) {
    return fast2_query(1,mx,1,pos,val) + (rcnt*(rcnt+1)/2+rcnt*(R+1-pos)) + (lcnt*(lcnt+1)/2+lcnt*(pos-L+1));
}

void add(int val) {

    if (have[val]>1) {
        int pos=dq[have[val]].front();
        dq[have[val]].pop_front();
        dq[have[val]+1].push_back(pos);
        ans+=cal_mid(pos,have[val]+1);

    } else if (have[val]==1) {
        int pos=dq[1].front();
        dq[1].pop_front();
        dq[2].push_back(pos);
        
        if (pos<MID) --lcnt, L=pos;
        if (pos>MID) --rcnt, R=pos;
        
        ans+=cal_mid(pos,2);

    } else {
        int pos=seq[++idx_seq];
        dq[1].push_back(pos);

        if (pos==MID) ans+=cal_mid(pos,1);
        else if (pos<MID) {
            ++lcnt;
            ans+=cal_left(pos);
        } else {
            ++rcnt;
            ans+=cal_right(pos);
        }
    }

    ++have[val];
}

void del(int val) {

    if (have[val]>2) {
        int pos=dq[have[val]].back();
        dq[have[val]].pop_back();
        dq[have[val]-1].push_front(pos);
        ans-=(cal_mid(pos,have[val]-1)+1);

    } else if (have[val]==2) {
        int pos=dq[2].back();
        dq[2].pop_back();
        dq[1].push_front(pos);

        if (pos==MID) ans-=(cal_mid(pos,1)+1);
        else {
            ans-=(cal_mid(pos,0)+2);
            if (pos<MID) ++lcnt, L=pos+1;
            if (pos>MID) ++rcnt, R=pos-1;
        } 

    } else {
        int pos=dq[1].back();
        dq[1].pop_back();
        --idx_seq;

        if (pos==MID) {
            fast2_query(1,mx,1,pos,0);
            ans=0;
        } else if (pos<MID) {
            ans-=cal_left(pos);
            --lcnt;
        } else {
            ans-=cal_right(pos);
            --rcnt;
        }
    }
    
    --have[val];
}

int n,q,a[MX+5];

struct Query {
    int l,r,idx;
    bool operator<(Query other) const {
        return pii(l/sq,((l/sq)&1) ? -r : +r)<pii(other.l/sq,((other.l/sq)&1) ? -other.r : +other.r);
    }
};

vector<Query> ques;
ll Ans[50005];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    set<int> ss;
    cin>>n>>q;
    for (int i=0; i<n; ++i) cin>>a[i], ss.insert(a[i]), ++have[a[i]];
    for (auto s : ss) if (have[s]>1) ++mx;
    memset(have,0,sizeof(have));
    mx+=(mx%2);

    MID=mx/2;
    L=MID;R=MID;
    int ll=MID,rr=MID;
    seq.push_back(MID);
    for (int i=1; i<MX; ++i) {
        if (i%2==0) seq.push_back(--ll);
        else seq.push_back(++rr);
    }

    for (int i=0; i<q; ++i) {
        int l,r; cin>>l>>r;
        ques.push_back({--l,--r,i});
    }

    sort(ques.begin(),ques.end());

    int cur_l=0;
    int cur_r=-1;

    for (auto q : ques) {
        while (cur_l>q.l) add(a[--cur_l]);
        while (cur_r<q.r) add(a[++cur_r]);
        while (cur_l<q.l) del(a[cur_l++]);
        while (cur_r>q.r) del(a[cur_r--]);
        Ans[q.idx]=ans;
    }

    for (int i=0; i<q; ++i) cout<<Ans[i]<<"\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