自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:46:51，当前版本为作者最后更新于2023-10-25 20:37:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其实这个东西直接一般化也是好做的。

把网格图的限制扔了，问题直接变成对于一张没啥性质的无向图，定义 $val(l,r)(l≤r)$ 为将颜色编号在 $[l,r]$ 内的格子染黑形成的四连通块数量，求对于 $i∈[1,k],val(l,r)=i$ 的 $[l,r]$ 数量。

这个东西是有很一般的做法的，考虑沿用森林上点数减边数的结论。从小到大扫 $r$，然后用 LCT 动态维护最大生成森林边集即可，查询变成了对于每个 $i$ 在 $[1,k]$ 查询点数减边数 $=i$ 的 $i$ 的数量，这个可以用线段树维护区间前 $k$ 小以及分别的数量后简单解决。

时间复杂度 $O((n+m) \log (n+m)+nk\log n)$。

#include<bits/stdc++.h>
#define ll long long 
#define pa pair<int,int> 
#define fi first 
#define se second 
#define mp make_pair
#define poly vector<int> 
using namespace std;
const int N=200005,B=15;
int inf;
struct node
{
    int val[B],cnt[B];
    node()
    {
        memset(val,0x3f,sizeof(val));
        memset(cnt,0,sizeof(cnt));
    }
}tr[N<<2];
int tag[N<<2];
node merge(node x,node y)
{
    node res;
    int l=0,r=0;
    for (int i=0;i<B;i++)
    {
        if (l<B&&r<B&&x.val[l]==y.val[r])
        {
            res.val[i]=x.val[l];
            res.cnt[i]=x.cnt[l]+y.cnt[r];
            l++,r++;
            continue;
        }
        if (r==B||l<B&&x.val[l]<y.val[r])
        {
            res.val[i]=x.val[l];
            res.cnt[i]=x.cnt[l];
            l++;
            continue;
        }
        res.val[i]=y.val[r];
        res.cnt[i]=y.cnt[r];
        r++;
    }
    return res;
}
void build(int k,int l,int r)
{
    tag[k]=0;
    if (l==r)
    {
        tr[k].val[0]=0;
        tr[k].cnt[0]=1;
        return;
    }
    int mid=l+(r-l)/2;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tr[k]=merge(tr[k<<1],tr[k<<1|1]);
}
void ptag(int k,int x)
{
    for (int i=0;i<B;i++)
        if (tr[k].val[i]!=inf) tr[k].val[i]+=x;
    tag[k]+=x;
}
void update(int k,int l,int r,int L,int R,int x)
{
    if (L<=l&&r<=R)
    {
        ptag(k,x);
        return;
    }
    if (tag[k])
    {
        ptag(k<<1,tag[k]);
        ptag(k<<1|1,tag[k]);
        tag[k]=0;
    }
    int mid=l+(r-l)/2;
    if (L<=mid) update(k<<1,l,mid,L,R,x);
    if (R>mid) update(k<<1|1,mid+1,r,L,R,x);
    tr[k]=merge(tr[k<<1],tr[k<<1|1]);
}
node query(int k,int l,int r,int L,int R)
{
    if (L<=l&&r<=R) return tr[k];
    if (tag[k])
    {
        ptag(k<<1,tag[k]);
        ptag(k<<1|1,tag[k]);
        tag[k]=0;
    }
    int mid=l+(r-l)/2;
    if (R<=mid) return query(k<<1,l,mid,L,R); 
    if (L>mid) return query(k<<1|1,mid+1,r,L,R);
    return merge(query(k<<1,l,mid,L,R),query(k<<1|1,mid+1,r,L,R));
}
int n,m;
int a[N],b[N],fa[N];
poly G[N],E[N];
ll ans[N];
namespace LCT{
    const int N=500005;
	int tr[N];
	int tot;
	inline void upd(int x,int y){while (x<=m){tr[x]+=y;x+=x&-x;}}
	inline int qry(int x){int res=0;while(x){res+=tr[x];x-=x&-x;}return res;}
	bool rev[N];
	int fa[N],ch[N][2];
	int val[N],mx[N];
	int ecnt;
	#define ls(x) (ch[x][0])
	#define rs(x) (ch[x][1])
	#define dir(x) (x == ch[fa[x]][1])
	#define IsRoot(x) (x != ch[fa[x]][0] && x != ch[fa[x]][1])

	inline void PushUp(int x) {
		mx[x] = x;
		if(ls(x) && val[mx[ls(x)]] > val[mx[x]]) mx[x] = mx[ls(x)];
		if(rs(x) && val[mx[rs(x)]] > val[mx[x]]) mx[x] = mx[rs(x)];
	}

	inline void PushDown(int x) {
		if(rev[x]) {
			if(ls(x)) std::swap(ls(ls(x)),rs(ls(x))),rev[ls(x)] ^= 1;
			if(rs(x)) std::swap(ls(rs(x)),rs(rs(x))),rev[rs(x)] ^= 1;
			rev[x] = 0;
		}
	}

	void update(int x) {
		if(!IsRoot(x)) update(fa[x]);
		PushDown(x);
	}

	inline void rotate(int x) {
		int y = fa[x],z = fa[y],d = dir(x),w = ch[x][d ^ 1];
		if(!IsRoot(y)) ch[z][dir(y)] = x;
		ch[y][d] = w,ch[x][d ^ 1] = y;
		fa[y] = x,fa[x] = z;
		if(w) fa[w] = y;
		PushUp(y);
	}

	inline void splay(int x) {
		update(x);
		while(!IsRoot(x)) {
			int y = fa[x],z = fa[y];
			if(!IsRoot(y))
				rotate((ls(y) == x) ^ (ls(z) == y) ? x : y);
			rotate(x);
		}
		PushUp(x);
	}

	inline void access(int x) {
		for(int p = 0;x;p = x,x = fa[x])
			splay(x),rs(x) = p,PushUp(x);
	}

	inline void MakeRoot(int x) {
		access(x),splay(x);
		std::swap(ls(x),rs(x)),rev[x] ^= 1;
	}

	inline int FindRoot(int x) {
		access(x),splay(x);
		while(ls(x)) PushDown(x),x = ls(x);
		splay(x);
		return x;
	}

	inline void split(int x,int y) {
		MakeRoot(x),access(y),splay(y);
	}

	inline void link(int x,int y) {
		MakeRoot(x); fa[x] = y;
	}
	inline int addedge(int u,int v,int w)
	{
		val[++tot] = w;
		MakeRoot(u);
		if(u != FindRoot(v)) {
			link(tot,u),link(tot,v);
			ecnt++;
		}
		else {
			split(u,v);
			int ep = mx[v];
			if(w < val[ep]) {
                int now=val[ep];
				splay(ep);
				fa[ch[ep][0]] = fa[ch[ep][1]] = 0;
				link(tot,u);
				link(tot,v);
                return now;
			}
            return -1;
		}
        return -2;
	}
	inline int qzadd(int u,int v,int w)
	{
		if (qry(w)-qry(w-1)) return -1;
		val[++tot] = w;
		MakeRoot(u);
		split(u,v);
		int ep = mx[v];
		{
			splay(ep);
			fa[ch[ep][0]] = fa[ch[ep][1]] = 0;
			link(tot,u);
			link(tot,v);
			upd(val[ep],-1);
			upd(w,1);
		}
		return val[ep];
	}
	inline void clr()
	{
		for (int i=1;i<=m;i++) tr[i]=0;
		for (int i=1;i<=tot;i++) rev[i]=0,fa[i]=0,
		val[i]=mx[i]=0,ch[i][0]=ch[i][1]=0;
		ecnt=0;
		tot=0;
	}			
}
void Bellakira()
{
    inf=tr[0].val[0];
    cin>>n>>m;
    for (int i=0;i<n;i++)
        cin>>a[i];
    for (int i=0;i<n;i++)
        G[max(a[i],a[(i+n-1)%n])].push_back(min(a[i],a[(i+n-1)%n]));
    for (int i=0;i<n;i++)
        cin>>b[i];
    for (int i=0;i<n;i++)
        G[max(b[i],b[(i+n-1)%n])].push_back(min(b[i],b[(i+n-1)%n]));
    for (int i=0;i<n;i++)
        E[max(b[i],a[i])].push_back(min(b[i],a[i]));
    n*=2;
	LCT::tot=n;
    build(1,1,n);
    for (int i=1;i<=n;i++)
    {
        update(1,1,n,1,i,1);
        for (auto u:G[i])
        {
            int o=LCT::addedge(u,i,n-u+1);
            if (o==-1) continue;
            update(1,1,n,1,u,-1);
            if (o!=-2)
                update(1,1,n,1,n-o+1,1);
        }
        for (auto u:E[i])
        {
            int o=LCT::addedge(u,i,n-u+1);
            if (o==-1) continue;
            update(1,1,n,1,u,-1);
            if (o!=-2)
                update(1,1,n,1,n-o+1,1);
        }
        node now=query(1,1,n,1,i);
        for (int j=0;j<B;j++)
            if (now.cnt[j]&&now.val[j]<=m) 
            {
                ans[now.val[j]]+=now.cnt[j];
            }
    }
    for (int i=1;i<=m;i++) cout<<ans[i]<<' ';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    while (T--)
    {
        Bellakira();
    }
}