题解：P9261 [PA 2022] Płótno

· · 题解

\text{Link}

分析

要求联通块的数量，等价于求联通块的边界数量再除以 2，于是，我们考虑求边界对每个区间的贡献。由于行数只有 2，所以我们可以简单分讨下边界的形态(令红色为一定在区间中的格子，蓝色为一定不在区间中的格子，白色为我们不关心的格子）：

第一种是边界只有一个格子，有上下左右四种对称情况。

第二种是边界有两个格子，有左右两种对称情况。

显然能使一个边界的区间一定满足 l 在一段区间内，r 在一段区间内，在二维平面上的影响就是矩形加，直接扫描线即可。要求权值为 1\sim k 的，直接在线段树上维护前 k 小值即可，时间复杂度 O(nk\log n)。

代码

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first 
#define se second
using namespace std;
long long read(){
    long long x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void write(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=2e5+10;
int n,k;
int b[2][N];
ll res[15];
struct oper{
    int l,r,v;
};
vector<oper>ad[N];
void add(int h,int i,int x,int i_){
    int l=1,r=2*n;
    if(b[h][i_]<x)l=max(l,b[h][i_]+1);
    else r=min(r,b[h][i_]-1);
    if(b[h^1][i]<x)l=max(l,b[h^1][i]+1);
    else r=min(r,b[h^1][i]-1);
    if(l>x||x>r)return;
    ad[l].push_back({x,r,1});
    ad[x+1].push_back({x,r,-1});
    // printf("insert h=%d i=%d x=%d i_=%d [%d,%d]\n",h,i,x,i_,l,r);
}
void add2(int i,int x,int y,int i_){
    int l=1,r=2*n;
    if(x>y)swap(x,y);
    if(b[0][i_]>=x&&b[0][i_]<=y)return;
    if(b[1][i_]>=x&&b[1][i_]<=y)return;
    if(b[0][i_]<x)l=max(l,b[0][i_]+1);
    else r=min(r,b[0][i_]-1);
    if(b[1][i_]<x)l=max(l,b[1][i_]+1);
    else r=min(r,b[1][i_]-1);
    if(l>x||y>r)return;
    ad[l].push_back({y,r,1});
    ad[x+1].push_back({y,r,-1});
}
#define pl p<<1
#define pr p<<1|1
struct Segment{
    struct Tree{
        pair<int,int>g[12];
        int tag;
        Tree(){for(int i=0;i<12;i++)g[i]={1e9,0};}
    }a[N<<2];
    void push(Tree &x,Tree y,Tree z){
        for(int i=0,p=0,q=0;i<=k;i++){
            if(y.g[p].fi==z.g[q].fi){
                x.g[i]=pii(y.g[p].fi,y.g[p].se+z.g[q].se);
                p++;q++;
            }
            else if(y.g[p].fi<z.g[q].fi){
                x.g[i]=y.g[p++];
            }
            else x.g[i]=z.g[q++];
        }
    }
    void pushup(int p){
        push(a[p],a[pl],a[pr]);
    }
    void pushdown(int p){
        if(a[p].tag){
            a[pl].tag+=a[p].tag;a[pr].tag+=a[p].tag;
            for(int i=0;i<12;i++){
                a[pl].g[i].fi+=a[p].tag;
                a[pr].g[i].fi+=a[p].tag;
            }
            a[p].tag=0;
        }
    }
    void build(int p,int L=1,int R=n*2){
        if(L==R){
            a[p].g[0]={0,1};return;
        }
        int mid=(L+R)>>1;
        build(pl,L,mid);build(pr,mid+1,R);
        pushup(p);
    }
    void change(int p,int l,int r,int v,int L=1,int R=2*n){
        if(l<=L&&R<=r){
            a[p].tag+=v;
            for(int i=0;i<12;i++){
                a[p].g[i].fi+=v;
            }
            return;
        }
        pushdown(p);
        int mid=(L+R)>>1;
        if(l<=mid)change(pl,l,r,v,L,mid);
        if(r>mid)change(pr,l,r,v,mid+1,R);
        pushup(p);
    }
}tr;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read();k=read();
    for(int i=0;i<n;i++){
        b[0][i]=read();
    }
    for(int i=0;i<n;i++){
        b[1][i]=read();
    }
    for(int i=0;i<n;i++){
        add(0,i,b[0][i],(i-1+n)%n);
        add(0,i,b[0][i],(i+1+n)%n);
        add(1,i,b[1][i],(i-1+n)%n);
        add(1,i,b[1][i],(i+1+n)%n);
        add2(i,b[0][i],b[1][i],(i-1+n)%n);
        add2(i,b[0][i],b[1][i],(i+1+n)%n);
    }
    tr.build(1);
    for(int i=1;i<=2*n;i++){
        for(auto u:ad[i])
            tr.change(1,u.l,u.r,u.v);
        for(int j=0;j<12;j++)
            if(tr.a[1].g[j].fi/2<=k)
                res[tr.a[1].g[j].fi/2]+=tr.a[1].g[j].se;
    }
    res[1]+=res[0]-1ll*(2*n)*(n*2-1)/2;
    for(int i=1;i<=k;i++)
        printf("%lld ",res[i]);
    puts("");
    return 0;
}