P3377 【模板】左偏树/可并堆
pb_ds版
cpp
#define heap __gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>,pairing_heap_tag>
int par[N];
bool vis[N];
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
heap q[N];
void solve(){
int n,m;
cin>>n>>m;
iota(par+1,par+n+1,1);
for(int i=1;i<=n;i++){
int x;
cin>>x;
q[i].push({x,i});
}
while(m--){
int op,x,y;
cin>>op;
if(op==1){
cin>>x>>y;
if(vis[x]||vis[y])continue;
x=find(x),y=find(y);
if(x==y)continue;
par[x]=y;
q[y].join(q[x]);
}
else{
cin>>x;
if(vis[x]){
cout<<"-1\n";
continue;
}
x=find(x);
y=q[x].top().first;
int z=q[x].top().second;
q[x].pop();
cout<<y<<"\n";
vis[z]=1;
}
}
}手写版
cpp
int dis[N],l[N],r[N],v[N];
bool cmp(int x,int y){
if(v[x]!=v[y])return v[x]<v[y];
return x<y;
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(cmp(y,x))swap(x,y);//y>x
r[x]=merge(r[x],y);
if(dis[r[x]]>dis[l[x]])swap(l[x],r[x]);
dis[x]=dis[r[x]]+1;
return x;
}P4331 [BalticOI 2004] Sequence 数字序列
题意：
给定整数序列 $ a_1,a_2,a_3,...,a_n $,求一个递增序列满足 $ b_1<b_2<b_3<..<b_n $,使得 $ \sum_{i=1}^N |a_i-b_i| $ 最小
思路：
- 令 $ a_i=a_i-i,b_i=b_i-i $ ,则变成求 $ b_1 \leq b_2 \leq ... \leq b_n $
- 结论：
- 假设b的所有值相等，则根据中位数定理，取中位数
- 假设将一个区间分成两个区间，第一个区间中位数为u，第二个区间中位数为v
- $ u<v $ ,不用管
- 否则，合并两个区间，取新的中位数
- 这样构造出来的答案为最小
- 用可并堆维护中位数，注意本题属于特殊情况才可以用可并堆维护
cpp
#define heap __gnu_pbds::priority_queue<int,less<int>,pairing_heap_tag>
struct Segment{
int end,root,size;
};
void solve(){
int n;
cin>>n;
vector<Segment> st;
vector<int> a(n+1);
heap q[n+1];
for(int i=1;i<=n;i++)cin>>a[i],a[i]-=i;
for(int i=1;i<=n;i++){
auto cur=Segment{i,a[i],1};
q[i].push(a[i]);
while(st.size()&&cur.root<st.back().root){
auto [end,root,size]=st.back();
st.pop_back();
q[cur.end].join(q[end]);
if(cur.size%2&&size%2)q[cur.end].pop();
cur.root=q[cur.end].top();
cur.size+=size;
}
st.push_back(cur);
}
vector<int> ans(n+1);
int res=0,i=1;
for(auto &[end,root,size]:st){
while(i<=end){
ans[i]=root;
res+=abs(ans[i]-a[i]);
i++;
}
}
cout<<res<<"\n";
for(int i=1;i<=n;i++)cout<<ans[i]+i<<" \n"[i==n];
}不需要记录方案的堆做法
cpp
void solve(){
int n;
cin>>n;
priority_queue<int> q;
vector<int> a(n+1);
int ans=0,res=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
q.push(a[i]);
if(q.top()>a[i]){
ans+=q.top()-a[i];
q.pop();
q.push(a[i]);
}
}
{//不上升
priority_queue<int,vector<int>,greater<int>> q;
for(int i=1;i<=n;i++){
q.push(a[i]);
if(q.top()<a[i]){
res+=a[i]-q.top();
q.pop();
q.push(a[i]);
}
}
ans=min(ans,res);
}
cout<<ans<<"\n";
}POJ3016 K-单调
题意：
将序列加1或减1，使得序列有k个部分单调
思路：
- $ O(n^2) $ 预处理每个部分的最小贡献，单调减的话让每个数取反即可
- $ O(n^2k) $ dp转移
cpp
#define heap __gnu_pbds::priority_queue<int,less<int>,pairing_heap_tag>
struct Segment{
int end,root;
int tree_size,tree_sum,size,sum;
int get(){
return root*tree_size-tree_sum+sum-tree_sum-root*(size-tree_size);
}
};
void solve(){
int n,k;
while(cin>>n>>k,n||k){
vector<int> a(n+1),w(n+1);
vector<vector<int>> cost(n+1,vector<int>(n+1,1e9)),f(n+1,vector<int>(k+1,1e9));
auto getcost=[&](int u){
heap q[n+1];
vector<Segment> st;
int res=0;
for(int i=u;i<=n;i++){
auto cur=Segment{i,w[i],1,w[i],1,w[i]};
q[i].push(w[i]);
while(!st.empty()&&cur.root<st.back().root){
auto [end,root,tree_size,tree_sum,size,sum]=st.back();
res-=st.back().get();
st.pop_back();
q[cur.end].join(q[end]);
bool ispop=cur.size%2&&size%2;
cur.tree_size+=tree_size;
cur.tree_sum+=tree_sum;
cur.size+=size;
cur.sum+=sum;
if(ispop){
auto big=q[cur.end].top();
q[cur.end].pop();
cur.tree_size--;
cur.tree_sum-=big;
}
cur.root=q[cur.end].top();
}
st.push_back(cur);
res+=cur.get();
cost[u][i]=min(cost[u][i],res);
}
};
for(int i=1;i<=n;i++)cin>>a[i],w[i]=a[i]-i;
for(int i=1;i<=n;i++)getcost(i);
for(int i=1;i<=n;i++)w[i]=-a[i]-i;
for(int i=1;i<=n;i++)getcost(i);
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
for(int u=1;u<=i;u++){
f[i][j]=min(f[i][j],f[u-1][j-1]+cost[u][i]);
}
}
}
cout<<f[n][k]<<"\n";
}
}