题解：P4497 [WC2011] 拼点游戏
Unaccepted_Zhou
·
·
题解
2K 短代码实现。别人咋都是 DS 乱飞吓哭了。只需要树状树组，set 和线段树区间 \max 板子。
题面补充
不保证最优下标序列唯一。
构造下标的 W 希望最小化修改次数 X。
思路
首先看到一加一减，考虑差分原数组。
序列按 $>0$（红）或 $\le0$（蓝）分成若干段：
第 $i$ 个深蓝色区间（不能是靠边的浅蓝色区间）的**区间和减区间最大值**为 $s_i$。要最小化 $X$，使得最小的 $X$ 个 $s$ 满足 $\displaystyle W+\sum s\le0$。
为啥不能 $\ge0$？因为红色选的越多，蓝色的最大值变小，蓝色区间会分裂，均导致 $X$ 变大。
### 维护
单点修改，维护所有 $s_i$。
区间和树状树组。区间 $\max$ 线段树。
`set<pair<int,int>>` 维护蓝色区间 `pair<int,int>={l,r}`。方便起见，靠边的也维护，询问的时候减去贡献即可。
询问 $X$ 可以线段树二分。这里使用 `unordered_map` 中[树状树组倍增](https://www.luogu.com.cn/article/klof1kp5)的阴间方法。值域大概 $1.3\times10^{15}$。
区间改变可以看作区间插入和删除，单点修改查询 $X$ 的数据结构。
### 细节
差分树组不考虑 $a_1$ 但考虑 $-a_n$。
差分树组修改不合法位置时跳过修改。
二分（倍增）到最后一个点时，要加上 $\displaystyle\left\lceil\frac{W-\sum s}{s'}\right\rceil$ 状物而不是加 $1$。
靠边区间减掉。注意判断 `set.empty()`。建议询问时减掉而不是分讨区间的变化时。（区间 $[1,n]$ 减重复了不影响）
注意你 `set.lower/upper_bound` 查找的区间是否正确。
建议先减去原贡献，再加上新贡献，以免算贡献算错版本。（负数改为负数可以先断开区间再接上）
### 代码
```cpp
#include<bits/stdc++.h>
#define pr pair<ll,ll>
#define F first
#define S second
#define B s.begin()
#define E s.end()
#define Z s.size()
#define ub s.upper_bound({x+1,0})//没+1不行
using namespace std;
typedef long long ll;
const ll N=1e5+10,M=N<<2,C=1.22e15;//C：umap树状树组偏移量
unordered_map<ll,ll> p,f; set<pr> s; bool ik;
ll sg[M],a[N],b[N],h[N],t,n,q,o,l,r,c,w,d,X,Y;
ll cl(ll u,ll l,ll r){//区间max
if(X<=l&&r<=Y)
{if(ik) sg[u]=a[l]; return sg[u];}
ll L=u<<1,R=L|1,m=l+r>>1,A=-1e18;
if(m<Y) A=cl(R,m+1,r);
if(X<=m) A=max(A,cl(L,l,m));
sg[u]=max(sg[L],sg[R]); return A;
}
ll Q(ll x){return x?h[x]+Q(x-(x&-x)):0;}//区间和
void g(pr t,ll K,bool G){//蓝区间插入或删除（K=1插入，-1删除）
X=t.F,Y=t.S; ll A=Q(Y)-Q(X-1)-cl(1,1,n);
for(ll i=A+C;i<=C;i+=i&-i) p[i]+=A*K,f[i]+=K;
if(G) if(K>0) s.insert(t); else s.erase(t);
}
void up(ll x,ll k){//差分树组修改
if(!x) return;
//减去原贡献
if(a[x]>0) w-=a[x];//不能>=0
else{//断开区间
auto U=--ub; pr u=*U; g(u,-1,1);
pr L={u.F,x-1},R={x+1,u.S};
if(L.F<=L.S) g(L,1,1);
if(R.F<=R.S) g(R,1,1);
}
//加上新贡献
for(ll i=x;i<=n;i+=i&-i) h[i]+=k-a[x];
ik=1,a[X=Y=x]=k,cl(1,1,n),ik=0;
if(a[x]>0) w+=a[x];
else{//合并区间
auto U=ub; pr u={x,x};
if(U!=E&&U->F==x+1)
u.S=U->S,g(*U,-1,1),U=ub;
if(U!=B&&(--U)->S==x-1)
u.F=U->F,g(*U,-1,1); g(u,1,1);
}
}
void pd(ll k){//去掉靠边区间
if(Z){if(B->F==1) g(*B,k,0);
if((--E)->S==n) g(*(--E),k,0);}
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&q),w=n;
s.clear(),p.clear(),f.clear();
for(ll i=1;i<=n;i++) h[i]=i&-i;
for(ll i=0;i<n;i++) scanf("%lld",&b[i]);
for(ll i=n;i>=1;i--)//差分
b[i]-=b[i-1],a[i]=1,up(i,b[i]);
while(q--){
scanf("%lld",&o),d=0; ll j=0,W=w;
if(!o){
scanf("%lld%lld%lld",&l,&r,&c);
up(l-1,a[l-1]+c),up(r,a[r]-c);
}else{
pd(-1);
for(ll i=1ll<<50ll;i;i>>=1ll)//树状树组倍增
if(j+i<=C&&W+p[j+i]>0)
W+=p[j+=i],d+=f[j]; if(j==C) d=-1;
else d+=W/(C-j-1)+bool(W%(C-j-1));//倍增到最后一个点
pd(1),printf("%lld %lld\n",w,d);
}
}
}
return 0;
}