JOISC2022K 魚 2 做题记录

有一些鱼和一个一条鱼宽的长条鱼缸（鱼在鱼缸中只能排成一条直线）。若鱼缸中相邻两条鱼 $a,b$ 大小分别为 $x,y$ 则：

• $x>y$：$a$ 能吃掉 $b$；
• $x<y$：$b$ 能吃掉 $a$；
• $x=y$：$a$ 和 $b$ 都能吃掉对方；

一条大小为 $x$ 的鱼吃掉一条大小为 $y$ 的鱼后它的大小会增加 $y$。

给定 $n$ 条鱼，大小依次为 $a_1,a_2,\dots ,a_n$。$q$ 次操作，每次操作为以下两种操作中的一种：

• $1\, x\, y$：把 $a_x$ 改为 $y$；
• $2\, l\, r$：求若把 $a_l,a_{l+1},\dots,a_r$ 依次放入鱼缸中，最后有多少条鱼可能吃光其它鱼，询问互相独立，即鱼不会真的互相吃；

$1\le n,q\le 10^5$，$1\le a_i, y\le 10^9$，$1\le l\le r\le n$。

直接上线段树，不难发现区间 $[L,R]$ 中有可能对答案有贡献的鱼肯定满足以下条件中至少一个：

• 能吃完 $[L,R]$ 中的其它鱼；
• 能吃完 $[L,l_i]$ 即某个前缀中的其它鱼；
• 能吃完 $[r_i,R]$ 即某个后缀中的其它鱼；

不难发现 $l_i$ 和 $r_i$ 分别只有 $O(\log V)$ 个，因为只有满足 $a_i>\sum\limits_{j=L}^{i-1}a_j$ 或 $a_i>\sum\limits_{j=i+1}^{R}a_j$ 的 $i$ 才有可能成为 $l_i+1$ 和 $r_{i}-1$。

那么线段树上每个节点开两个 vector 维护一下这些端点就行了，具体实现看代码注释。

时间复杂度 $O((n+q)\log n\log V)$，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int S=100005,MS=35;

struct ndd
{
	int p;         // 吃掉这个端点后最远可以吃到哪里（左端点往右吃，右端点往左吃）
	long long s,v; // 吃掉这个端点可以长大多少，这个端点的值
	int c;         // 有多少鱼可以吃掉这个端点
	inline ndd(){p=s=v=c=0;}
	inline ndd(int x,long long y,long long z,int w){p=x,s=y,v=z,c=w;}
};

int smcl[S],smcr[S];

struct node
{
	vector<ndd> lb,rb; // 前缀端点（从前到后）、后缀端点（从后到前）
	inline node(int x=0,long long y=0)
	{
		if(x==0) lb.clear(),rb.clear();
		else lb=rb={ndd(x,y,y,1)}; // 只有一条鱼的区间
	}
	inline node(vector<ndd> &rl,vector<ndd> &rr){lb=rl,rb=rr;}
}tr[S<<2];

inline node operator+(node a,node b)
{
	if(a.lb.size()==0) return b;
	if(b.lb.size()==0) return a;
	vector<ndd> rl=a.lb,rr=b.rb;
	int al=a.lb.size(),ar=a.rb.size(),bl=b.lb.size(),br=b.rb.size();
	// left
	long long sum=0;
	for(int i=0;i<al;i++) sum+=a.lb[i].s; // 吃完左边有多大
	for(ndd pre:b.lb)
	{
		if(sum>=pre.v) rl[rl.size()-1].s+=pre.s,rl[rl.size()-1].p=pre.p; // 这个端点可以被吃掉
		else rl.push_back(pre); // 不能被吃掉
		sum+=pre.s;
	}
	// right 同理
	sum=0;
	for(int i=0;i<br;i++) sum+=b.rb[i].s;
	for(ndd pre:a.rb)
	{
		if(sum>=pre.v) rr[rr.size()-1].s+=pre.s,rr[rr.size()-1].p=pre.p;
		else rr.push_back(pre);
		sum+=pre.s;
	}
	// c
	// 清空
	for(ndd &u:rl) smcl[u.p]=0;
	for(ndd &u:rr) smcr[u.p]=0;
	// 左区间的左端点和右区间的右端点
	for(int i=0;i<al;i++) smcl[rl[i].p]+=rl[i].c;
	for(int i=0;i<br;i++) smcr[rr[i].p]+=rr[i].c;
	// 可以吃光整个大区间的鱼特殊处理
	if(rl.size()==al) smcr[rr[rr.size()-1].p]+=a.lb[al-1].c;
	if(rr.size()==br) smcl[rl[rl.size()-1].p]+=b.rb[br-1].c;
	// 被左边的右端点困住，通过吃右边完成逃离
	sum=0;
	int l=0,r=0;
	for(int i=0;i<ar-1;i++)
	{
		while(l<=i) sum+=a.rb[l].s,l++; // 获取这些鱼被困时多大
		bool f=true;
		while(f) // 往左往右吃
		{
			f=false;
			while(r<bl&&sum>=b.lb[r].v) sum+=b.lb[r++].s,f=true;
			while(l<ar&&sum>=a.rb[l].v) sum+=a.rb[l++].s,f=true;
		}
		if(l==ar) smcl[b.lb[r-1].p]+=a.rb[i].c; // 如果可以吃完左区间，即吃掉大区间的一个前缀
		if(r==bl) smcr[a.rb[l-1].p]+=a.rb[i].c; // 如果可以吃完右区间，即吃掉大区间的一个后缀
	}
	// 同理
	sum=0;
	l=0,r=0;
	for(int i=0;i<bl-1;i++)
	{
		while(l<=i) sum+=b.lb[l].s,l++;
		bool f=true;
		while(f)
		{
			f=false;
			while(r<ar&&sum>=a.rb[r].v) sum+=a.rb[r++].s,f=true;
			while(l<bl&&sum>=b.lb[l].v) sum+=b.lb[l++].s,f=true;
		}
		if(l==bl) smcr[a.rb[r-1].p]+=b.lb[i].c;
		if(r==ar) smcl[b.lb[l-1].p]+=b.lb[i].c;
	}
	for(ndd &u:rl) u.c=smcl[u.p];
	for(ndd &u:rr) u.c=smcr[u.p];
	return node(rl,rr);
}

int n,q;
long long a[S];

void build(int u,int l,int r)
{
	if(l==r) return tr[u]=node(l,a[l]),void();
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	tr[u]=tr[u<<1]+tr[u<<1|1];
}

void upd(int u,int l,int r,int pos,long long y)
{
	if(l==r) return tr[u]=node(l,a[l]=y),void();
	int mid=l+r>>1;
	if(pos<=mid) upd(u<<1,l,mid,pos,y);
	else upd(u<<1|1,mid+1,r,pos,y);
	tr[u]=tr[u<<1]+tr[u<<1|1];
}

void que(int u,int l,int r,int L,int R,node &res)
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R) return res=res+tr[u],void();
	int mid=l+r>>1;
	if(L<=mid) que(u<<1,l,mid,L,R,res);
	if(R>=mid+1) que(u<<1|1,mid+1,r,L,R,res);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%d",&q);
	while(q--)
	{
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1) upd(1,1,n,x,y);
		else
		{
			node res;
			que(1,1,n,x,y,res);
			printf("%d\n",res.lb[res.lb.size()-1].c);
		}
	}
	return 0;
}