题解 P9261 [PA 2022] Płótno
其实这个东西直接一般化也是好做的。
把网格图的限制扔了，问题直接变成对于一张没啥性质的无向图，定义
这个东西是有很一般的做法的，考虑沿用森林上点数减边数的结论。从小到大扫
时间复杂度
#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();
}
}