[USACO23FEB] Hungry Cow P 题解

T7 [USACO23FEB] Hungry Cow P

这题就比较正常了，蓝紫之间的水平。

我们发现 Bessie 能活 \(10^{14}\) 天（，导致我们不好直接按照值域来维护。发现给某一天送干草，影响到的是后面很多天，这是个区间问题。所以考虑动态开点线段树。线段树的每个节点维护 \(\mathit{ans},\mathit{cnt},\mathit{out}\)，分别表示当前区间答案、当前区间有多少天能吃上饭、当前区间有多少溢出。

不好维护的地方在于解决左儿子向右儿子 “溢出” 的问题。设 \(f(l,r,x)\) 表示前面溢出了 \(x\) 份干草给区间 \([l,r]\) 时这个区间有多少天能吃上饭。对于这个函数的求解，分类讨论：

• \(x=0\)，直接返回区间 \([l,r]\) 的 \(\mathit{ans}\)；
• \(l=r\)，直接返回 \(l\)；
• \(x-\mathit{cnt}_l\le\mathit{mid}-l+1\)，说明 \(x\) 份干草让左区间用完了，递归左区间并加上右区间的答案。注意右区间的答案不是 \(\mathit{ans}_r\)，而是 \(\mathit{ans}_p-\mathit{ans}_l\)，因为右区间的答案我们暂时没有更新，我们只能用我们已经更新过的当前区间答案和左区间答案相减得到。
• 否则说明，左区间全都可以吃到干草，等差数列求和统计左区间答案，然后递归计算右区间。

核心部分就讲完了，感觉还是挺技巧的。注意动态开点线段树的空间复杂度是 \(O(n\log n)\) 的。时间复杂度是线段树的 \(n\log n\) 乘上 \(f\) 函数计算的一个 \(\log\)，总共 \(O(n\log^2n)\)。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define lp st[p].ls
#define rp st[p].rs
#define mid ((s+t)>>1)
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
template<typename T=int>
T read(){
	T x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	putchar(sf);
}
using ll=long long;
constexpr int MAXN=1e5+5;
constexpr ll MOD=1e9+7,inv2=500000004;
int U;
struct SegTree{
	int ls,rs;
	ll ans,cnt,out;
}st[MAXN*47];
int rt=1,tot=1;
ll sum(ll l,ll r){
	return (l+r)%MOD*((r-l+1)%MOD)%MOD*inv2%MOD;
}
ll f(ll s, ll t, ll x, int p){
	if(!x)return st[p].ans;
	if(s==t)return s%MOD;
	if(x+st[lp].cnt<=mid-s+1)return(f(s,mid,x,lp)+st[p].ans-st[lp].ans+MOD)%MOD;
	return(sum(s,mid)+f(mid+1,t,x-(mid-s+1-st[lp].cnt)+st[lp].out,rp))%MOD; 
}
void pushup(ll s,ll t,int p){
	st[p].cnt=st[lp].cnt+min(st[lp].out+st[rp].cnt,t-mid);
	st[p].out=st[rp].out+max(st[lp].out+st[rp].cnt-(t-mid),0ll);
	st[p].ans=(st[lp].ans+f(mid+1,t,st[lp].out,rp))%MOD;
}
void update(ll s,ll t,ll x,ll k,int&p){
	if(!p)p=++tot;
	if(s==t){
		if(!k)st[p].ans=st[p].cnt=st[p].out=0;
		else st[p].cnt=1,st[p].out=k-1,st[p].ans=s%MOD;
		return;
	}
	if(x<=mid)update(s,mid,x,k,lp);
	else update(mid+1,t,x,k,rp);
	pushup(s,t,p);
}

int main(){
	U=read();
	while(U--){
		ll x=read<ll>(),y=read<ll>();
		update(1,2e14,x,y,rt);
		write(st[rt].ans);
	}
	return fw,0;
}