题解：P17502 [ICPC 2026 Wuhan I] The Best Card

最近做过质量比较高的题（我也最多这样了），

观察影响情况，是若干的三角状物拼起来。如下（* 为新增的中毒）：

* *      *    
*+*+     *+  *
*++++    *++ *+

考虑每次附魔，在同一个连通块内，增加的贡献最多为长度加一，并使其长度加一。

- -      -
*-*-     *-   
*+*+-    *+- *
*++++-   *++-*+

如上（- 为新增贡献），在第二次中毒附魔一定不如在第一次优，推广为在连通块的头部附魔一定最优。

这里算一下在长为 \(U\) 的连通块头部附魔 \(K\) 次的贡献为 \(UK+\frac{K(K+1)}{2}\)。等差数列求和即可。

注意这样的操作可能使两个连通块合并（如图）！为方便理解，我们可以预处理出不附魔时的贡献，剩下的贡献压成一维的线段（如下）：

+++++    +++ ++

对于两条相邻线段，设其间距为 \(G\)，前面线段长度为 \(U\)，后面为 \(V\)。合并两条线段的代价为 \(G\)，并产生 \(GU+\frac{G(G+1)}{2}\) 的贡献，产生长度为 \(U+G+V\) 的线段。

注意到这里额外贡献与 \(V\) 无关，那么若我们合并连续的一系列线段，一定从前往后合并，从后往前一定不优。

同样的，我们只会合并连续的一系列线段，枚举起点模拟即可做到 \(O(Tn^2)\)。参考我的代码中注释的一段。

考虑优化，我们发现起点向后枚举时，终点单调不降，想到双指针，结合前缀和做到 \(O(Tn \log n)\)，老哥来源于对 \(t\) 的排序（题目没保证升序）。

#include
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,m;
array,N> a;
array ab,s,sum,c,t;
signed Main(){cin>>n>>m;int ans=0,bs=0;for(int i=1;i<=n;i++)cin>>a[i][1];for(int i=1;i<=n;i++)cin>>a[i][0];sort(a.begin()+1,a.begin()+1+n);vector > b;int u=a[1][1],l=a[1][0];for(int i=2;i<=n;i++){int v=a[i][1],r=a[i][0];if(r-l<=u){bs+=((u+l-a[i-1][0])*2-(r-a[i-1][0]-1))*(r-a[i-1][0])/2;u+=v;}else{bs+=(u+l-a[i-1][0])*(u+l-a[i-1][0]+1)/2;b.push_back(array{u,l});u=v,l=r;}}bs+=(u+l-a[n][0])*(u+l-a[n][0]+1)/2;b.push_back(array{u,l});// for(int i=0;i>T;while(T--)Main();cerr<<(double)(clock()-Start)/CLOCKS_PER_SEC<

由于 AI 说我的代码命名过于混乱，故放下表。

代码本身思路对应正确，但变量名对读者不友好。建议在题解代码前加一个变量表：