题解 | #小苯吃糖果# 构式分块做法||提供一组小数据

小苯吃糖果

https://ac.nowcoder.com/acm/contest/93847/A

~~唉唉是谁赛时唐到用分块写硬条1h40min没调出来最后发现忘处理小块破防了~~

~~蒟蒻码字不易,路过的留个赞呗~~

本文并没有同步发布于我的博客,因为懒

提供一种分块做法:

分析题目易知,我们只需要维护每个水池所在连通块的左右端点即可,平均值可用前缀和求.

先考虑如何维护

假设我们已经知道本次修改的左右端点,设 $a[i]$ 为点 $i$ 的值, $P[i]$ 表示点 $i$ 左侧有挡板,同时以 $\sqrt n$ 为块长分块,对于散块暴力处理,对于整块直接打上标记.这样操作的时间复杂度是 $O(\sqrt n)$ 的

性质:如果一个整块被打上了标记,那么它内部的散块一定不会再被更新.

很容易证明:被打上标记的整块内部点的左端点一定在块的左侧,右端点一定在块的右侧

这个性质我们查询时也会用到.

再考虑如何寻找左右端点

对于左端点,如果该点所在的块被打过标记,那么跳到前一个块并重复此过程.

如果该点所在的块没被打过标记,那在这个块内一定有一个挡板.因为块长最多为 $O(\sqrt n)$ ,所以我们最多会查询 $O(\sqrt n)$ 次,暴力找即可.

对于右端点同理.

考虑查询

如果该点所在块被打过标记,输出块记录的值

否则输出该点的 $a[i]$ 值

时间复杂度为 $O(n\sqrt n)$ ,可以通过本题

于是我们愉快的切掉了本题......

才怪!

接下来是地狱般的的调试,因为 " $P[i]$ 表示点 $i$ 左侧有挡板",所以在分块时有巨多的细节需要注意,十分甚至九分难写.

代码(数据在最后)

#include<bits/stdc++.h>
using namespace std;
int n,m;
int len,gen;
double a[214514],s[214514],res;
int p[214514];
struct Node
{
	int l,r;
	double cnt;
	int f;
	int res;
} b[2145];
int op,aa,bb,c;
int l,r;
int ls,rs;

inline int findl(int l,int r)
{
	int op=(r-1)/len+1;
	
	while(b[op].res<=0&&op>=1)
	{
		r=b[op].l;
		if(p[r])
		  return r;
		op--;
		//***
	}
	
	for(int i=r;i>=l;i--)
	{//cout<<i<<' ';
		op=(i-1)/len+1;
		if(b[op].res<=0&&i%len!=1&&op>=0)
		{
			i=b[op].l;
			if(p[i])
			  return i;
			i++;  
		}
		else
		{
			if(p[i])
		    return i;
		}
	}
	return l;
}

inline int findr(int l,int r)
{
	int op=(l-1)/len+1;
	
	while(b[op].res<=0&&op<=gen)
	{
		op++;
		l=b[op].l;//***
		if(p[l])
		  return l-1;
	}
	
	for(int i=l;i<=r;i++)
	{
		op=(i-1)/len+1;
		if(b[op].res<=0&&i%len!=1&&op<=gen)
		{
			i=b[++op].l;
			if(p[i])
			  return i-1;
			i--;  
		}
		else
		{
			if(p[i])
		    return i-1;
		}
		
	}
	return r-1;
}

int main()
{
	scanf("%d%d",&n,&m);
	//len=100;
	len=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		p[i]=1;//cin>>a[i];
		scanf("%lf",&a[i]);
		b[(i-1)/len+1].res++;
		if((i-1)%len==0)
		{
			b[(i-1)/len+1].l=i;
			b[(i-1)/len].r=i-1;
		}
		s[i]+=s[i-1]+a[i];
	}
	p[n+1]=1;
	gen=(n-1)/len+1;
	b[gen].r=n;
  b[gen+1].l=n+1;
	while(m--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d",&aa,&bb);
			l=findl(1,aa);
			r=findr(bb+1,n+1);
			res=(s[r]-s[l-1])/(r-l+1);
			ls=(l-1)/len+1;
			rs=(r-1)/len+1;
			if(ls==rs)
			{
				for(int i=l;i<=r;i++)
				{
					a[i]=res;
					if(p[i]&&i>l)
					{
						p[i]=0;
						b[ls].res--;
					}
				}
			}
			else
			{
				for(int i=l;i<=b[ls].r;i++)
				{
					a[i]=res;
					if(p[i]&&i>l)
					{
						p[i]=0;
						b[ls].res--;
						//add(i,1);
					}
				}
				for(int i=ls+1;i<=rs-1;i++)
				{
					p[b[i].l]=0;
					a[b[i].l]=res;
					b[i].cnt=res;
					b[i].res=0;
					//b[i].f=1;
				}
				for(int i=b[rs].l;i<=r;i++)
				{
					a[i]=res;
					if(p[i])
					{
						p[i]=0;
						b[rs].res--;
						//add(i,1);
					}
				}
			}
			//cout<<a[10]<<' ';	
		}
		else
		{
			scanf("%d",&c);//cout<<c<<' ';
			if(c%len==1||abs(b[(c-1)/len+1].cnt)<1e-8)
			{
				//cout<<a[10]<<' ';
				printf("%.6lf\n",a[c]);
			}
			  
			else
			  printf("%.6lf\n",b[(c-1)/len+1].cnt);  
		}
		
	}
	
	
	return 0;
}
/*提供一组数据进行调试 
12 12
3 6 10 1 10 3 10 9 4 3 6 1 
1 3 6
1 8 8
1 5 11
1 2 9
1 2 6
1 5 7
1 10 11
2 8
2 6
2 9
2 10
2 4
*/
/*
6.200000
6.200000
6.200000
6.200000
6.200000
*/