【UOJ660】【IOI2021】candies（线段树）

题目链接

• 有 (n) 个盒子，第 (i) 个盒子中至多装 (c_i) 颗糖果。
• 有 (q) 次操作，每次往第 (l_jsim r_j) 个盒子中装入/取出 (v_j) 颗糖果，将操作后的糖果数向 (c_i) 取 (min)，向 (0) 取 (max)。
• 求最终每个盒子中的糖果数。
• (1le n,qle2times10^5)

重要结论

只考虑某一个糖果盒，不管向 (c_i) 取 (min) 和向 (0) 取 (max) 的限制，记录它在每次操作之后的糖果数 (s_j)（即 (pm1) 的前缀和）。

发现如果存在一个区间 ([L,R])，满足 (s_R) 是区间最大值，且 (s_R) 减 ([L,R]) 中的最小值大于 (c_i)，则在第 (R) 个操作后必然有 (c) 颗糖果。

同理，如果存在一个区间 ([L,R])，满足 (s_R) 是区间最小值，且 ([L,R]) 中的最大值减 (s_R) 大于 (c_i)，则在第 (R) 个操作后必然没有糖果。

扫描线+线段树上二分

考虑用扫描线离线操作，这样就可以依次枚举每一个糖果盒，用线段树维护好针对这个糖果盒的修改。

然后线段树上二分，找出最靠后的一段后缀，满足其中最大值减最小值大于 (c_i)。

对于较后面的那个最值，在它和最终值之间不存在相差大于 (c_i) 的值（否则就会选中以它开始的后缀），也就是说在这一过程中不用考虑向 (c_i) 取 (min) 和向 (0) 取 (max) 的问题，直接用 (s_j) 之差计算即可。

特殊地，如果找不到这样一段后缀，即对所有区间最大值减最小值都小于等于 (c_i)，则最小值所在位置必然没有糖果，从它开始计算答案即可。

代码：(O((n+q)log n))

#include "candies.h"
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 200000
#define LL long long
#define INF (LL)1e18
using namespace std;
int n,Qt;struct OP {int x,t,v;I bool operator < (Cn OP& o) Cn {return x<o.x;}}s[2*N+5];
class SegmentTree
{
	private:
		#define PT CI l=0,CI r=Qt,CI rt=1
		#define LT l,mid,rt<<1
		#define RT mid+1,r,rt<<1|1
		#define PU(x) (Mx[x]=max(Mx[x<<1],Mx[x<<1|1]),Mn[x]=min(Mn[x<<1],Mn[x<<1|1]))
		#define PD(x) (F[x]&&(T(x<<1,F[x]),T(x<<1|1,F[x]),F[x]=0))
		#define T(x,v) (Mx[x]+=v,Mn[x]+=v,F[x]+=v)
		bool fg;LL mx,mn,Mx[N<<2],Mn[N<<2],F[N<<2];
		I void G(CI c,PT)//线段树上二分
		{
			if(l==r) return (void)(fg=Mx[rt]>mx);RI mid=l+r>>1;PD(rt);//fg记录较靠前的是哪个最值
			LL mxx=max(mx,Mx[rt<<1|1]),mnn=min(mn,Mn[rt<<1|1]);return mxx-mnn>=c?G(c,RT):(mx=mxx,mn=mnn,G(c,LT));//向右极差大于等于c就向右
		}
		I LL QV(CI x,PT) {if(l==r) return Mx[rt];RI mid=l+r>>1;PD(rt);return x<=mid?QV(x,LT):QV(x,RT);}//询问某个位置的值
	public:
		I void U(CI L,CI v,PT) {if(L<=l) return (void)T(rt,v);RI mid=l+r>>1;PD(rt),L<=mid&&(U(L,v,LT),0),U(L,v,RT),PU(rt);}//后缀修改
		I int Q(CI c) {if(Mx[1]-Mn[1]<=c) return QV(Qt)-Mn[1];mx=-INF,mn=INF,G(c);return fg?QV(Qt)-mn:QV(Qt)-mx+c;}//找到最靠后的极差大于c的区间计算答案
}S;
vector<int> ans;vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v)
{
	RI i,ct=0;for(n=c.size(),Qt=l.size(),i=0;i^Qt;++i) s[++ct]=(OP){l[i],i+1,v[i]},s[++ct]=(OP){r[i]+1,i+1,-v[i]};//离线
	RI j=1;for(sort(s+1,s+ct+1),i=0;i^n;ans.push_back(S.Q(c[i++]))) W(j<=ct&&s[j].x==i) S.U(s[j].t,s[j].v),++j;return ans;//扫描线
}