「题解」300iq Contest 2 H. Honorable Mention
本文将同步发布于：
- 洛谷博客；
- csdn；
- ；
- gym102331H。
题意概述
给定一个长度为 \(n\) 的序列 \(a\)，有 \(q\) 次询问，每次询问给定三个参数 \(l,r,k\)，求出对于区间 \([l,r]\)，你将其划分为若干个子区间，然后取其中的 \(k\) 个，最大化取出来的所有元素的和。即：最大 \(k\) 子段和。
\(1\leq n,q\leq 3.5\times 10^4\)，\(|a_i|\leq 3.5\times 10^4\)。
题解
寻找函数的性质
如果我们设 \(f_{[l,r]}(k)\) 表示区间 \(l,r\) 的最大 \(k\) 子段和，那么我们不难猜测到 \(l,r\) 相同时，\(f(k)\) 是一个上凸函数。
我们考虑证明这一点，即 \(f(k)-f(k-1)\geq f(k+1)-f(k)\)。
考虑反证法，设 \(\exists x\in\mathbb{N}\)，满足 \(f(x)-f(x-1)
那么我们考虑在 \(x-1,x,x+1\) 的时候的选取方案。
- 若取 \(x+1\) 的时候正子段仍未取完，那么 \(f(x)\) 比 \(f(x-1)\) 多取了一个区间 \(p(p>0)\)；\(f(x+1)\) 比 \(f(x)\) 多取了一个区间 \(q(q>0)\)。
如果我们认为 \(f(x)-f(x-1) - 若取 \(x-1\) 的时候正子段取完了，那么 \(f(x)\) 比 \(f(x-1)\) 多取了一个区间 \(p(p<0)\)；\(f(x+1)\) 比 \(f(x)\) 多取了一个区间 \(q(q<0)\)。
如果我们认为 \(f(x)-f(x-1)
综上所述，如果选取的方案不满足上凸包的性质，我们总是可以通过调整法将其变成上凸包。
合并凸包——闵可夫斯基和
如果我们求出了区间 \([l,r]\) 内的 \(f(k)\)，我们就想要知道这个东西是否支持快速合并，例如 \(f_{[l,\texttt{mid}]}+f_{[\texttt{mid}+1,r]}\to f_{[l,r]}\)。
答案是可以的。
考虑到 \(f(k)\) 的凸性，我们不妨使用 闵可夫斯基和 对两个凸包进行合并，时间复杂度为 \(\Theta(r-l)\)。
简单做法
通过上面的叙述，我们已经得到了一个简单的做法。
每次询问时，我们在线段树上求出此次询问覆盖的区间，并将所有的凸包合并，然后直接得到 \(f(k)\) 即为答案。
考虑分析时间复杂度，不难发现，这种做法的单次询问时间复杂度与区间长度有关，我们需要更优秀的做法。
wqs 二分
我们考虑不将区间合并，而是直接在线段树上的 \(\Theta(\log_2n)\) 个区间内求解答案。
具体地，我们决定使用 wqs 二分，解除掉选择区间个数的限制，然后各个区间就可以互不干扰的选择，很容易就能求出最优解。通过调整最终的斜率，我们可以得出答案，时间复杂度为 \(\Theta(q\log^3_2n)\)。
整体 wqs 二分
我们考虑到，当 \(k\) 增大时，其对应的 wqs 二分时的斜率也会越大，因此这个二分具有单调性，我们可以将询问对 \(k\) 排序，然后进行整体二分，常数更小的方法是在线段树上维护一个指针，表示上一次 \(k\leq x\) 的最优位置，然后暴力自增即可。
时间复杂度为 \(\Theta(q\log_2^2n)\)。
参考程序
#includeusing namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; #define flush() (fwrite(wbuf,1,wp1,stdout),wp1=0) #define putchar(c) (wp1==wp2&&(flush(),0),wbuf[wp1++]=c) static char wbuf[1<<21];int wp1;const int wp2=1<<21; inline int read(void){ reg bool f=false; reg char ch=getchar(); reg int res=0; while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar(); return f?-res:res; } inline void writeln(reg int x){ static char buf[32]; reg int p=-1; if(x<0) x=-x,putchar('-'); if(!x) putchar('0'); else while(x) buf[++p]=(x%10)^'0',x/=10; while(~p) putchar(buf[p--]); putchar('\n'); return; } inline int max(reg int a,reg int b){ return a>b?a:b; } const int MAXN=5e4+5; const int MAXQ=5e4+5; const ll inf=1e12; struct querys{ int id,l,r,k,lef,rig; }; inline bool cmp(const querys& a,const querys& b){ return (a.lef+a.rig)>(b.lef+b.rig); } typedef vector Data; inline Data max(Data a,Data b){ if(a.size()>b.size()){ for(reg int i=0,siz=b.size();i (a.begin()+1,a.end()); } inline void print(Data p){ for(auto x:p) printf("%lld ",x); return; } int tim; pair {0,-inf},dat(k)[1][1]=vector {-inf,a[l]}; return; } build(lson,l,mid,a),build(rson,mid+1,r,a); pushup(k); return; } inline void query(reg int k,reg int l,reg int r,reg int L,reg int R,reg ll K){ if(t(k)!=tim){ t(k)=tim; ptr(k)[0][0]=ptr(k)[0][1]=ptr(k)[1][0]=ptr(k)[1][1]=0; } if(L<=l&&r<=R){ g[0]=f[0],g[1]=f[1],f[0]=f[1]=make_pair(-inf,0); for(reg int i=0;i<2;++i) for(reg int j=0;j<2;++j) if(dat(k)[i][j].size()){ while(ptr(k)[i][j] - 若取 \(x+1\) 的时候正子段仍未取完，那么 \(f(x)\) 比 \(f(x-1)\) 多取了一个区间 \(p(p>0)\)；\(f(x+1)\) 比 \(f(x)\) 多取了一个区间 \(q(q>0)\)。