P5476 题解

· · 题解

题目分析

看数据范围不大，尤其是 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;
        }
    }
}