自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:11:10，当前版本为作者最后更新于2023-04-30 23:04:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

看数据范围不大，尤其是 $s_i$ 很小，所以先暴力容斥出每种贝壳给贡献的至多 $2^{s_i}$ 个矩形区域，然后差分下来再二维前缀和即可 $O(ms\times2^s+n^2)$ 预处理出以每个点为所挖矩形左下角时的答案。

接下来考虑修改，注意到每加入一个鸟蛋都会使一些格子由合法变成不合法，而每个格子至多会这样变一次，所以考虑用并查集对每行维护当前还合法的格子，每次加蛋暴力在每行的并查集上跳，这样即可 $O(nT+n^2)$ 地找出每次需要删除的格子。

最后考虑询问，发现每次整体询问 $\geq V_i$ 的值的数量，权值线段树维护加数删数和区间和就行了。总时间复杂度 $O(ms\times 2^s+nT+n^2 \log m)$，常数还挺小，可以通过本题。

代码

/*
  author: PEKKA_l  
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define popcount(x) __builtin_popcount(x)

int n,k,m,s,u[7],v[7],t,b,c,flag,a[2505][2505];

struct tree
{
	int sum;
}tree[400005];

#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define n(x) tree[x].sum
#define md(x,y) ((x+y)>>1)
#define push_up(x) n(x)=n(ls(x))+n(rs(x))

void cz(int l,int r,int x,int k,int p)
{
	if(l==r) {n(p)+=k; return;} int mid=md(l,r);
	if(mid>=x) cz(l,mid,x,k,ls(p)); else cz(mid+1,r,x,k,rs(p)); push_up(p);
}
int ask(int l,int r,int x,int y,int p)
{
	if(x>y) return 0;
	if(l>=x&&r<=y) return n(p); int mid=md(l,r),nans=0;
	if(mid>=x) nans+=ask(l,mid,x,y,ls(p)); if(mid<y) nans+=ask(mid+1,r,x,y,rs(p)); return nans;
}

int fa[2505][2505];
int getfa(int u,int x) {return fa[u][x]==x?x:fa[u][x]=getfa(u,fa[u][x]);}

signed main()
{
	cin>>n>>k>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>s; for(int j=1;j<=s;j++) cin>>u[j]>>v[j];
		for(int j=1;j<(1<<s);j++)
		{
			int mnx=1,mny=1,mxx=n-k+1,mxy=n-k+1;
			for(int p=1;p<=s;p++)
			{
				if(j&(1<<(p-1)))
				{
					mnx=max(mnx,u[p]-k+1); mny=max(mny,v[p]-k+1);
					mxx=min(mxx,u[p]); mxy=min(mxy,v[p]);
				}
			}
			if(mnx>mxx||mny>mxy) continue; int zz=(popcount(j)&1)?1:-1;
			a[mnx][mny]+=zz; a[mnx][mxy+1]-=zz; a[mxx+1][mny]-=zz; a[mxx+1][mxy+1]+=zz;
		} 
	}
	for(int i=1;i<=n-k+1;i++) for(int j=1;j<=n-k+1;j++) 
	{a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; cz(0,m,a[i][j],1,1);}
	for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++) fa[i][j]=j;
	cin>>t; while(t--)
	{
		cin>>flag;
		if(flag==1)
		{
			cin>>b>>c; int mnx=1,mny=1,mxx=n-k+1,mxy=n-k+1;
			mnx=max(mnx,b-k+1); mny=max(mny,c-k+1); mxx=min(mxx,b); mxy=min(mxy,c);
			if(mnx>mxx||mny>mxy) continue;
			for(int i=mnx;i<=mxx;i++)
			{
				int kk=getfa(i,mny);
				while(kk<=mxy) {cz(0,m,a[i][kk],-1,1); fa[i][kk]=getfa(i,kk+1); kk=fa[i][kk];}
			}
		}
		else
		{
			cin>>b; cout<<(double)ask(0,m,b,m,1)/(double)((n-k+1)*(n-k+1))<<endl;
		}
	}
}