题解归档 - cf2239C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2239C
• 本地来源：problems/cf2239C/idea.md
• 题目链接：https://codeforces.com/contest/2239/problem/C
• 原始标题：cf2239C - Revival

思路

cf2239C - Revival

Pattern

Use right-to-left blocks between consecutive known prefix inversion counts.

Add virtual s_0=0. If consecutive s positions are l<r, then
l+1..r-1 are fixed p positions, and only p_r is unknown in this block.
When processing this block, all positions >r are already removed, so the main
segment tree contains exactly the values still available for positions 1..r.

Let F be the fixed values in l+1..r-1, cnt=|F|, and need=s_r-s_l.

For candidate x=p_r:

need = inv(F)
     + sum_{y in F} cnt_available_greater(y)
     - cnt*(cnt-1)/2
     + cnt_available_greater(x)
     - cnt_F_less(x)

Rearrange to:

cnt_available_leq(x) + cnt_F_less(x)
  = inv(F) + sum_greater - cnt*(cnt-1)/2 + r - need

The right side is K. Temporarily add +1 at y+1 in the main segment tree
for every fixed value y in F; then the prefix sum at x is exactly
cnt_available_leq(x)+cnt_F_less(x). A segment-tree kth query returns the
smallest prefix position with sum at least K, which is a valid p_r.

After choosing p_r, remove the temporary y+1 updates, remove p_r, then
remove all fixed values in this block and continue left.

Data Structure

segment_tree is copied from the ordinary point-update/range-sum segment tree
style:

• change(root,l,r,x,val) point add
• query(root,l,r,L,R) range sum
• kth(root,l,r,k) first position whose prefix sum reaches k

Two instances are used:

• T: available values plus temporary y+1 shifts
• T2: temporary frequencies inside one fixed block, used only to count
  inv(F), then cleared immediately

No vectors are needed.

Complexity

Each position causes O(1) segment-tree updates/queries, and each s block
does one kth query. Total complexity is O(n log n), memory O(n).

Checks

• sample: python tools/run_exe.py cf2239C -i problems/cf2239C/sample.in

• randomized checker: python problems/cf2239C/stress2.py

  • 12000 generated valid mixed p/s cases with n<=30
• exhaustive generated valid cases for all permutations and all p/s masks
  with n<=6: 50362 cases
• performance edge: one case with n=200000, all positions as s_i=i(i-1)/2

代码

来源：problems/cf2239C/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5;
ll s[maxn+5],p[maxn+5],ss[maxn+5],ps[maxn+5];
char op[maxn+5];
struct segment_tree{
    ll t[maxn*4+5];
    void pushup(ll root){
        t[root]=t[root*2]+t[root*2+1];
    }
    void build(ll root,ll a,ll b,ll val){
        if(a==b){
            t[root]=val;
            return;
        }
        ll mid;
        mid=(a+b)/2;
        build(root*2,a,mid,val);
        build(root*2+1,mid+1,b,val);
        pushup(root);
    }
    void change(ll root,ll a,ll b,ll x,ll val){
        if(a==b){
            t[root]+=val;
            return;
        }
        ll mid;
        mid=(a+b)/2;
        if(x<=mid) change(root*2,a,mid,x,val);
        else change(root*2+1,mid+1,b,x,val);
        pushup(root);
    }
    ll query(ll root,ll a,ll b,ll L,ll R){
        ll mid,ans;
        if(L<=a and b<=R) return t[root];
        mid=(a+b)/2;
        ans=0;
        if(L<=mid) ans+=query(root*2,a,mid,L,R);
        if(R>mid) ans+=query(root*2+1,mid+1,b,L,R);
        return ans;
    }
    ll kth(ll root,ll a,ll b,ll k){
        ll mid;
        if(a==b) return a;
        mid=(a+b)/2;
        if(t[root*2]>=k) return kth(root*2,a,mid,k);
        return kth(root*2+1,mid+1,b,k-t[root*2]);
    }
}T1,T2;
int main(){
    ll t,n,i,k,a,b,slsl,zc,cnt,cur,dq,dq2,A,K;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        getchar();
        slsl=0;
        ps[0]=0;
        T1.build(1,1,n,1),T2.build(1,1,n,0);
        for(i=1;i<=n;i++){
            scanf("%c%lld",&op[i],&s[i]);
            getchar();
            if(op[i]=='s'){
                p[i]=s[i];
                ps[++slsl]=i;
            }
        }
        b=ps[slsl];
        for(i=n;i>=b+1;i--){
            ss[i]=s[i];
            T1.change(1,1,n,s[i],-1);
        }
        for(k=slsl;k>=1;k--){
            a=ps[k-1],b=ps[k];
            cnt=cur=dq=0;
            for(i=a+1;i<b;i++){
                zc=s[i];
                cur+=cnt-T2.query(1,1,n,1,zc);
                if(zc<n) dq+=T1.query(1,1,n,zc+1,n);
                cnt++;
                T2.change(1,1,n,zc,1);
            }
            for(i=a+1;i<=b-1;i++) T2.change(1,1,n,s[i],-1);
            A=cur+dq-cnt*(cnt-1)/2;
            dq2=p[b]-p[a];
            K=A+b-dq2;
            for(i=a+1;i<b;i++){
                if(s[i]<n) T1.change(1,1,n,s[i]+1,1);
            }
            ss[b]=T1.kth(1,1,n,K);
            for(i=a+1;i<=b-1;i++){
                if(s[i]<n) T1.change(1,1,n,s[i]+1,-1);
            }
            T1.change(1,1,n,ss[b],-1);
            for(i=b-1;i>=a+1;i--){
                ss[i]=s[i];
                T1.change(1,1,n,s[i],-1);
            }
        }
        for(i=1;i<=n;i++){
            if(i>1) printf(" ");
            printf("%lld",ss[i]);
        }
        printf("\n");
    }
    return 0;
}