题目

\(N\) 个物品中选\(M\)个，排列成一个环:\(k_1,\cdots,k_M\)价值为：

\[ \sum_{j=1}^{N}{V_i} - \sum_{j=1}^{M}|C_{k_j}- C_{k_{j\%M+1} }| \]

$3 \le N,M \le 2\times 10^5 $

题解

• 对于一个\(k\)，\(C\)最小的排列的贡献是\(2\ ( max - min)\)

• 因为将 $ k $ 按 $ C $ 排序，由于最终是一个环， $ C_{k_j} - C_{k_{j+1}} $ 一定会被至少经过两次

• 将物品按\(C\)排序，枚举最大点，枚举最小点，中间选\(V\)最大的

• 可以发现从左向右枚举右端点，最小值的选择是单调的

• 但是单调可能是不连续的，接下来有一个套路：

• 计算\([l,r]\)的值时，可以先找\(mid = (l + r) /2\) 的最优决策点\(pos_{mid}\)

• 那么\(pos_{[l,mid-1]} \le pos_{mid} \ , \ pos_{[mid+1,r]} \ge pos_{mid}\) ，分治求下去

• 需要查找区间前\(m-2\)大的和，如果用主席树实现

• 时间复杂度：\(O(N \log^2 N )\)

  #include
        
         #define ll long long #define inf 1e18using namespace std;const int N=200010,M=20;int n,m,st[N],tp,sub[N],tot,sz,cnt[N*M],ls[N*M],rs[N*M],rt[N];ll sum[N*M],a[N],b[N],ans=-inf;struct data{int x,y;}A[N];bool operator <(data X,data Y){return X.y
         
          >1;  if(x<=mid)ins(ls[k],ls[lst],l,mid,x,y);  else ins(rs[k],rs[lst],mid+1,r,x,y);}ll query(int k,int lst,int l,int r,int x){  if(l==r||!x)return 1ll*sub[l]*x;  int mid=(l+r)>>1,tmp=cnt[rs[k]]-cnt[rs[lst]];  if(x
          
           R)return;  if(l==r){for(int i=L;i<=R;++i)ans=max(ans,cal(st[l],i));}  int Mid=(L+R)>>1,mid=l;ll tmp=-inf;  for(int i=l;i<=r;++i){      ll now=cal(st[i],Mid);      if(tmp
           
            a[st[tp]])st[++tp]=i;  }  solve(m,n,1,tp);  /*ll ans=cal(1,m);  for(int i=m,j=1;i<=n;++i){      while(j
            
             <=i&&cal(st[j],i)