map维护段的分裂

E. Fill the Matrix

Problem - E - Codeforces

题意：给定一个n*n的阵列，每一列从上到下连续ai个为黑，其余为白，白格子中才能放数，现在有k个数，beauty值定义为满足i后接i+1的数的数量。

n<=2e5

题解：转换下题意就是说找到最少的段数使得总和>=k。由于n很大，无法遍历阵列，我们考虑从最下面的行向上转移，观察如何log维护转移。

我们发现，在转移过程中，当在第i行j列出现黑色而i+1行j列未出现黑色，则会使得此段断裂产生两个段。而这种新出现的黑色至多有n个，如此我们可以维护段，维护一个段的出现开始行并在其消失时将其长度出现次数加入答案中即可。用map维护做到O(nlogn)。

#include<bits./stdc++.h>
#define int long long 
using namespace std;
const int N=2e5;
struct seg
{
    int l,r;
};
bool operator <(const seg &a, const seg &b){
	return a.l < b.l;
}
void solve(){
    int n;cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int m;cin>>m;
    map<seg,int> used;
    used[{0,n}]=n;
    vector<int> ord(n);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&a](int x,int y){
        return a[x]>a[y];
    });
    int ans=0;
    int j=0;
    vector<int> cnt(n+1);
    for(int i=n;i>=0;i--){
        while(j<n&&a[ord[j]]>=i){
            auto it=used.upper_bound({ord[j],-1});
            --it;
            auto tmp=it->first;
            cnt[tmp.r-tmp.l]+=it->second-i;
            used.erase(it);
            if(tmp.l!=ord[j])
                used[{tmp.l,ord[j]}]=i;
            if(tmp.r!=ord[j])
                used[{ord[j]+1,tmp.r}]=i;
            ++j;    
        }        
    }
    for(int i=n;i>0;i--){
        int t=min(cnt[i],m/i);
        ans+=t*(i-1);
        m-=t*i;
        if(t!=cnt[i]&&m>0){
            ans+=m-1;
            m=0;
        }
    }
    cout<<ans<<endl;
}
signed main(){
    int T;cin>>T;
    while(T--){
        solve();
    }
}