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

\text{Link}

分析

要求联通块的数量，等价于求联通块的边界数量再除以

2

，于是，我们考虑求边界对每个区间的贡献。由于行数只有

2

，所以我们可以简单分讨下边界的形态(令红色为一定在区间中的格子，蓝色为一定不在区间中的格子，白色为我们不关心的格子）：

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

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

显然能使一个边界的区间一定满足

l

在一段区间内，

r

在一段区间内，在二维平面上的影响就是矩形加，直接扫描线即可。要求权值为

1\sim k

的，直接在线段树上维护前

k

小值即可，时间复杂度

O(nk\log n)

。

代码

CPP

#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;
}

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

文章操作

分析

代码

相关推荐

评论

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