专栏文章

AT_joisc2019_j

xxujindong_
AT_joisc2019_j题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minm4nrg
此快照首次捕获于
2025/12/02 04:39
3 个月前
此快照最后确认于
2025/12/02 04:39
3 个月前
查看原文
题意：nn 个物品有 Vi,CiV_i,C_i，选恰好 mm 个物品按某个顺序排成一个环，权值是 ViV_i 的和减环上相邻两个物品 CiC_i 之差，最大化权值。
显然 CC 从小到大/从大到小选，按 CC 排序，则 CC 的贡献是 −2-2 倍极差，因此选一个区间 [l,r][l,r]，强制首尾要选，权值是 VV 在 (l,r)(l,r) 的前 k−2k-2 大和加 Vl+Vr−2(Cr−Cl)V_l+V_r-2(C_r-C_l)。
注意到它有决策单调性。四边形不等式，只和端点有关的抵消，剩 (l,r)(l,r) 的前 k−2k-2 大和。这个满足四边形不等式 w(a,c)+w(b,d)≥w(a,d)+w(b,c)(a<b<c<d)w(a,c)+w(b,d)\geq w(a,d)+w(b,c)(a<b<c<d)，假设在 [a,d],[b,c][a,d],[b,c] 中各选 kk 个，显然总是 [a,c],[b,d][a,c],[b,d] 的一种方案（[a,b)[a,b) 的放进 [a,c][a,c]，(c,d](c,d] 的放进 [b,d][b,d]，中间的随便放）。
决策单调性分治，维护区间权值有多种方案：主席树，或者用莫队 trick 之后维护对顶 set 或者 BIT 上二分。O(nlog⁡2n)O(n\log^2n)。
CPP
#include<bits/stdc++.h>
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T&a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename ...Args>void in(T&a,Args&...args){
  in(a),in(args...);
}
using namespace std;
int n,k,l=1,r,va[200005],cnt,tr1[200005];
long long tr2[200005];
struct node{
  int a,b;
}a[200005];
bool cmp(node a,node b){
  return a.b<b.b;
}
void add(int x,int k){
  for(int i=x;i<=cnt;i+=i&-i)tr1[i]+=k,tr2[i]+=k*va[x];
}
long long query(int k){
  int x=0;
  long long sum=0;
  for(int i=__lg(cnt);i>=0;i--){
    x+=1<<i,k-=tr1[x],sum+=tr2[x];
    if(x>cnt||k<0)k+=tr1[x],sum-=tr2[x],x-=1<<i;
  }
  if(x<cnt)sum+=1ll*k*va[x+1];
  return sum;
}
long long calc(int gl,int gr){
  if(gr-gl+1<k)return -0x3f3f3f3f3f3f3f3f;
  while(l>gl)add(a[--l].a,1);
  while(r<gr)add(a[++r].a,1);
  while(l<gl)add(a[l++].a,-1);
  while(r>gr)add(a[r--].a,-1);
  return query(k)+va[a[gl-1].a]+va[a[gr+1].a]-2*(a[gr+1].b-a[gl-1].b);
}
long long solve(int l1,int r1,int l2,int r2){
  if(l2>r2)return -0x3f3f3f3f3f3f3f3f;
  int mid=(l2+r2)>>1,pos=l1;
  long long ans=-0x3f3f3f3f3f3f3f3f;
  for(int i=l1;i<=min(mid-k+1,r1);i++)if(calc(i,mid)>ans)ans=calc(i,mid),pos=i;
  return max(ans,max(solve(l1,pos,l2,mid-1),solve(pos,r1,mid+1,r2)));
}
int main(){
  in(n,k);
  for(int i=1;i<=n;i++)in(a[i].a,a[i].b),va[i]=a[i].a;
  sort(a+1,a+n+1,cmp),sort(va+1,va+n+1),cnt=unique(va+1,va+n+1)-va-1;
  for(int i=1;i<=n;i++)a[i].a=cnt-(lower_bound(va+1,va+cnt+1,a[i].a)-va)+1;
  reverse(va+1,va+cnt+1);
  if(k==1)return cout<<va[1]<<'\n',0;
  return k-=2,cout<<solve(2,n,1,n-1)<<'\n',0;
}
还可以更快。普通莫队可以改成回滚莫队，决策单调性的莫队也可以设计指针的移动做到只增不删/只删不增。此处我们需要只删不增：
当前从 [l1,r1][l_1,r_1] 转移到 [l2,r2][l_2,r_2]，假设当前维护 [l1,r2][l_1,r_2]。
  • 倒序删除 (mid,r2](mid,r_2]；
  • 求解 midmid 的决策点，正着扫一遍 [l1,r1][l_1,r_1]，同时删除，完毕后倒序恢复 [l1,r1][l_1,r_1]；
  • 删除 midmid，递归左半边 [l1,mid][l_1,mid] 转移到 [l2,pos−1][l_2,pos-1]，恢复 midmid；
  • 正序恢复 (mid,r2](mid,r_2]；
  • 正序删除 [l1,pos)[l_1,pos)，递归右半边 [mid,r1][mid,r_1] 转移到 [pos+1,r2][pos+1,r_2]，倒序恢复 [l1,pos)[l_1,pos)。
如此将所有加入变成了对删除的撤销。
此时我们可以用链表维护前 kk 大和，这个只能删除，通过上面的方法将加入变成了撤销，就可以维护了。O(nlog⁡n)O(n\log n)。
CPP
#include<bits/stdc++.h>
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T&a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename ...Args>void in(T&a,Args&...args){
  in(a),in(args...);
}
using namespace std;
int n,k,va[200005],cnt,pre[200005],nxt[200005],top;
long long now;
struct node{
  int a,b;
}a[200005];
bool cmpa(node a,node b){
  return a.a>b.a;
}
bool cmpb(node a,node b){
  return a.b<b.b;
}
void add(int x){
  nxt[pre[x]]=pre[nxt[x]]=x;
  if(x<=top)now+=va[x]-va[top],top=pre[top];
}
void del(int x){
  if(x<=top)top=nxt[top],now+=va[top]-va[x];
  nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];
}
long long solve(int l1,int r1,int l2,int r2){
  if(l2>r2||r2-l1+1<k)return -0x3f3f3f3f3f3f3f3f;
  int mid=(l2+r2)>>1;
  for(int i=r2;i>mid;i--)del(a[i].a);
  int pos=l1;
  long long ans=-0x3f3f3f3f3f3f3f3f;
  for(int i=l1;i<=min(mid-k+1,r1);i++){
    if(now+va[a[i-1].a]+va[a[mid+1].a]-2*(a[mid+1].b-a[i-1].b)>ans)ans=now+va[a[i-1].a]+va[a[mid+1].a]-2*(a[mid+1].b-a[i-1].b),pos=i;
    del(a[i].a);
  }
  for(int i=min(mid-k+1,r1);i>=l1;i--)add(a[i].a);
  del(a[mid].a),ans=max(ans,solve(l1,pos,l2,mid-1)),add(a[mid].a);
  for(int i=mid+1;i<=r2;i++)add(a[i].a);
  for(int i=l1;i<pos;i++)del(a[i].a);
  ans=max(ans,solve(pos,r1,mid+1,r2));
  for(int i=pos-1;i>=l1;i--)add(a[i].a);
  return ans;
}
int main(){
  in(n,k);
  for(int i=1;i<=n;i++)in(a[i].a,a[i].b);
  sort(a+1,a+n+1,cmpa);
  for(int i=1;i<=n;i++)va[i]=a[i].a,a[i].a=i;
  va[n+1]=0,sort(a+1,a+n+1,cmpb);
  if(k==1)return cout<<va[1]<<'\n',0;
  k-=2;
  for(int i=1;i<=n+1;i++)pre[i]=i-1,nxt[i]=i+1;
  for(int i=1;i<=k;i++)now+=va[i];
  return top=k,del(a[1].a),del(a[n].a),cout<<solve(2,n,k+1,n-1)<<'\n',0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...