【TJOI2012】防御

题目链接

小清新数据结构题，题解区为啥清一色两棵线段树。

考虑分块，维护两个数组：$tag$ 和 $minx$ 分别记录整块的累计伤害和当前护盾最小值。当发现有护盾值为负数时，将它赋值为 $INF$，然后暴力重新扫块内并下放 $tag$，对于盾值为 $INF$ 的累加 $tag \times 2$，否则就累加 $tag$ 即可。

对于一个点最多重扫一次，重扫一次复杂度为 $O(\sqrt N)$ ，总复杂度为 $O(N \sqrt N)$，事实上因为一次块内重扫可能将多个盾值标记为 $INF$，所以实际跑起来一般达不到上界。

需要注意的地方是对盾值做减法的时候要先判断当前盾值与 $tag$ 的关系，如果已经爆盾了只不过伤害还寄存在 $tag$ 里，就应该先下放 $tag$。

跑的比某些线段树还要快吗？

$Code$

#include<bits/stdc++.h>
#define int long long
#define MAX 100010
#define INF 999999999
#define mod 1000000009
using namespace std;

inline int read()
{
	int s=0;
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s;
}

int n,m;
char op;
int blo,bn;
int a[MAX],l[MAX],r[MAX],pos[MAX],tag[MAX],minx[MAX];

inline void block()
{
	n=read(),m=read();
	memset(minx,0x3f,sizeof minx);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(a[i]==0) a[i]=INF;
	}
	blo=sqrt(n);bn=(n-1)/blo+1;
	for(int i=1;i<=bn;i++)
		l[i]=(i-1)*blo+1,r[i]=i*blo;
	r[bn]=n;
	for(int i=1;i<=bn;i++)
		for(int j=l[i];j<=r[i];j++)
			pos[j]=i,minx[i]=min(minx[i],a[j]);
	return;
}

int ans[MAX];
inline void spread(int x)
{
	minx[x]=INF;
	for(int i=l[x];i<=r[x];i++)
	{
		if(a[i]==INF) ans[i]+=2*tag[x];
		else ans[i]+=tag[x],a[i]-=tag[x];
		if(a[i]<=0) a[i]=INF;
		minx[x]=min(minx[x],a[i]);
	}
	tag[x]=0;
	return;
}
inline void change(int L,int R,int k)
{
	int p=pos[L],q=pos[R];
	if(p==q)
	{
		if(minx[p]<=tag[p]+k) spread(p);   //先判断是否需要下放!!!
		for(int i=L;i<=R;i++)
		{
			if(a[i]==INF) ans[i]+=2*k;
			else a[i]-=k,ans[i]+=k;	
			minx[p]=min(minx[p],a[i]);			
			if(a[i]<=0) a[i]=INF;
		}
		if(minx[p]<=tag[p]) spread(p);
	}
	else
	{
		for(int i=p+1;i<=q-1;i++)
		{
			if(minx[i]<=tag[i]+k) spread(i);
			tag[i]+=k;
		}
		if(minx[p]<=tag[p]+k) spread(p);
		for(int i=L;i<=r[p];i++)
		{
			if(a[i]==INF) ans[i]+=2*k;
			else a[i]-=k,ans[i]+=k;
			minx[p]=min(minx[p],a[i]);
			if(a[i]<=0) a[i]=INF;
		}
		if(minx[p]<=tag[p]) spread(p);
		if(minx[q]<=tag[q]+k) spread(q);
		for(int i=l[q];i<=R;i++)
		{
			if(a[i]==INF) ans[i]+=2*k;
			else a[i]-=k,ans[i]+=k;
			minx[q]=min(minx[q],a[i]);
			if(a[i]<=0) a[i]=INF;
		}
		if(minx[q]<=tag[q]) spread(q);
	}
	return;
}
inline int getsum(int x)
{
	int p=pos[x];
	if(a[x]==INF) return ans[x]+2*tag[p];
	return ans[x]+tag[p];
}

int x,y,k;
int answer;
inline void work()
{
	for(int i=1;i<=m;i++)
	{
		cin>>op;
		switch(op)
		{
			case 'A':x=read(),y=read(),k=read();change(x,y,k);break;
			case 'Q':x=read();answer+=getsum(x);break;
		}
	}
	cout<<answer%mod;
	return;
}

signed main()
{
	block();
	work();
	return (0-0);
}