P3683 题解

· · 题解

前言

NOIP 考前写点题解攒 RP

题解

注意事项：一个操作里面包含两个步骤。

首先观察操作的性质：

（不会的话康康样例 1 的图，因为比较显然，就不细说了。）

由于题目询问的“t 个区间的并”不大好求，我们考虑用容斥转化成：只用一个区间恰好包含多边形的最小长度 - 在这个区间内前 t-1 大的间隔数量（不与多边形相交）。

看起来还是没有头绪，注意到区间在编码上连续，而多边形在地图上连续，我们不妨把二维抽象成一维（降维打击.jpg）来考虑问题，其中一维中的第 i 个格子表示地图上编号为 i 的单元。

那么如果把多边形覆盖到的单元在一维上染色，那么我们就得到了这样一张图：

（这是样例 1 的一维表示）

那么注意到“只用一个区间恰好包含多边形的最小长度”的区间的左右端点恰好是多边形内编号最小和最大的单元。 这个易于求解，先按下不表。

我们再考虑另一个问题：“在这个区间内前 t-1 大的间隔数量”,注意到 t 的数量级很大，因此我们猜测 t 的种类数（或者说我们易于区分的间隔的种类，长度不一定不同）与多边形的边数有一定关系。

阿巴阿巴。。。还是不大会，我们考虑一下二维地图和一维序列之间的关系。

为了简便操作，我们希望我们考虑的间隔区间在二维和一维上都连续——我们发现按照题目操作所分割出来的矩形正好满足我们所需要的条件。但是间隔区间可能不完全等于题目操作分割出来的矩形所形成的区间，一个比较 fake 的想法就是分治。

我们假设已经进行了前 i 个操作，分割出来了一个矩形，我们希望通过分治得到这个矩形的贡献（间隔的数量和大小）。

看起来很暴力，不过时间复杂度是对的。

首先注意我们的分治最多会递归 O(2n) 层，因此最大深度是 O(2n)，另外对于每一层，矩阵拥有的顶点不会相同（因为矩阵之间互不相交），因此最多有 O(m) 个矩形存在顶点，会被递归到。那么这种矩形数量最大是 O(2nm) 个。再考虑矩形内全部都是横边或者竖边的个数。首先对于这种矩形一定是由有顶点的矩形转移过来的，由于一个矩形最多能分成两个矩形，并且顶点不会消失，即一个有顶点的矩形最多直接转移出来一个没有顶点的矩形，最多有 O(nm) 个。

对单个矩形分别考虑。最多拥有 O(m) 条边，注意到只有分割矩形的边与当前矩阵的边平行时会产生新的矩阵，并且分割下去的矩形拥有的边不会相同，分割矩形的边与当前的矩阵的边不平行的时候不会产生新的矩阵。那么每一层最多会有 m 个矩阵，即对于一层最多有 O(nm) 个矩形。

这样的矩形共存在 O(n^2m^2) 个，暴力实现复杂度 O(n^2m^3+q\log_{n^2m^3})，注意到我们可以在分治过程中记录当前矩形拥有的边。对于 O(nm) 个顶点矩阵，每个最多拥有 m 条边，对于他们第一次分治出去的矩阵，每个会贡献 O(nm) 条边，总的时间复杂度即 O(n^2m^2+q\log_{n^2m^2})。

代码实现

代码：

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=1e6+1e3;
struct Seg{int dir,p,l,r;Seg(int dir=-1,int p=-1,int l=-1,int r=-1):dir(dir),p(p),l(l),r(r){}};
const bool operator<(const Seg&x,const Seg&y){return x.p<y.p;}
/*
Seg 表示是边

假设是横边，p 表示这条边的 y 左边，l,r 表示这条边的横坐标

dir=0 表示若这条边是竖边，那么在这条边左边（在这条边左边的边的右边，下类似）的点在矩形内部
      表示若这条边是横边，那么在这条边下面的点在矩形内部
dir=1 表示若这条边是竖边，那么在这条边右边的点在矩形内部
      表示若这条边是横边，那么在这条边上面的点在矩形内部
*/
map<int,int,greater<int> >mp;
int check(int l,int r,vector<Seg>&b){for(auto y:b)if(y.l>l||y.r<r)return 0;return 1;}
//判断是否有顶点，因为有可能顶点在矩形边上，另一条边被吞了。 
void write(vector<Seg>&x){for(auto y:x)printf("%d %d %d %d\n",y.dir,y.p,y.l,y.r);puts("");}
pair<int,int>solve(int l,int r,int &sx,int &ex,int &sy,int &ey,int in,int f,vector<Seg>&a,vector<Seg>&b)
/*
l,r：这个矩形对应的区间编号
sx,ex,sy,ey：假定矩形的一维为 sx,ex,另一维为 sy,ey，
            并且满足分割的横线的按 x 这一维分成两半 
in：若这个矩形内部没有边，那么这个矩形是在多边形内部还是外部
f：系数，表示求出的间隔数变成 f 倍
a：维护的边集合，满足与当前分割的横线平行
b：维护的边集合，满足于当前分割的横线相交 

pair<int,int>solve() 表示当前的矩形的区间的左端点到 solve().fi-1 是间隔 
                     表示当前的矩形的区间 solve().se+1 到左断点是间隔
                     -1 表示这个区间都是间隔。 
记得每次转坐标，另外，这个不是 90 度的转，是反复转。 
*/
{
    if(a.empty()&&b.empty())
    {if(in==-1)exit(1);return in?mk(l,r):mk(-1ll,-1ll);} 
    if(l==r)
        if(a.empty())return solve(l,r,sy,ey,sx,ex,in,f,b,a);
        else return (a[0].dir==(a[0].p==sx))?mk(l,r):mk(-1ll,-1ll);
    int mid=l+r>>1,m=sx+ex>>1;
    if(a.empty()&&check(sx,ex,b))//边与分割线相交 
    {
        pii t=solve(l,mid,sy,ey,sx,m,in,2*f,b,a);
        if(t.fi==-1)return t;
        mp[t.fi-l+mid-t.se]+=f;return mk(t.fi,t.se-l+mid+1);
    }
    else //有顶点或者边与分割线平行 
    {
        vector<Seg>al,ar,bl,br;
        for(auto y:a)
        {
            if(y.p<=m)al.pb(y);
            if(y.p>=m)ar.pb(y);
        }
        for(auto y:b)
        {
            if(y.l<m)bl.pb(y);
            if(y.r>m)br.pb(y);
        }
        pii tl=solve(l,mid,sy,ey,sx,m,(!ar.empty()?ar[0].dir==0:in),f,bl,al);
        pii tr=solve(mid+1,r,sy,ey,m,ex,(!al.empty()?al.back().dir==1:in),f,br,ar);
        if(tl.fi==-1)return tr;
        if(tr.fi==-1)return tl;
        mp[tr.fi-tl.se-1]+=f;return mk(tl.fi,tr.se);
    }
}

int n,m;
int val[N],s1[N],s2[N];
vector<Seg>A,B;
int get(int x,int y,int tot=0)
/*
    get()=1 ：在矩形内部 
    get()=0 ：在矩形外部 
*/
{
    for(auto i:A)if(i.p<=x&&i.l<=y&&i.r>y)tot++;
    return tot&1;
}
signed main()
{
//  freopen("geohash.in","r",stdin);
//  freopen("geohash.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    int px,py,x,y,sx,sy;
    scanf("%lld%lld",&sx,&sy);px=sx,py=sy;
    //A：维护横边，B：维护竖边 
    for(int i=2;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        if(x==px)A.pb(Seg(0,x,min(py,y),max(py,y)));
        else B.pb(Seg(0,y,min(px,x),max(px,x)));
        px=x,py=y;
    }
    if(x==sx)A.pb(Seg(0,x,min(sy,y),max(sy,y)));
    else B.pb(Seg(0,y,min(sx,x),max(sx,x)));

    sort(A.begin(),A.end());sort(B.begin(),B.end());
    for(int i=0;i<A.size();i++)A[i].dir=get(A[i].p,A[i].l);
    for(int i=0;i<B.size();i++)B[i].dir=get(B[i].l,B[i].p);
    sx=0,sy=0;int ex=1<<n,ey=1<<n;
    pii t=solve(0,(1ll<<n*2)-1,sx,ex,sy,ey,-1,1,A,B);
    //维护出来的 t.fi 和 t.se 就是用一个区间包含多边形的最小长度 
    int res=t.se-t.fi+1,cnt=0;
    for(auto y:mp)
    {
        val[++cnt]=y.fi;
        s1[cnt]+=s1[cnt-1]+y.se;
        s2[cnt]+=s2[cnt-1]+y.fi*y.se;
    }
    int _;scanf("%lld",&_);
    while(_--)
    {
        int k;scanf("%lld",&k);k--;
        int it=lower_bound(s1+1,s1+cnt+1,k)-s1;
        printf("%lld\n",res-(s2[it-1]+(k-s1[it-1])*val[it]));
    }
    return 0;
}

后记

难点主要在于模拟。