CF1109F 题解

冷月葬T魂 · 2024-03-13 16:36:08 · 题解

简要题意：给定一个 n\times m 网格，格子中填有 1\sim n\times m 的互不相同的权值。称一个区间 [l,r] 合法当且仅当权值在 [l,r] 内的格子形成一棵树。求有几个合法区间。n\times m\le 2\times 10^5。

Do NOT use LCT!

首先数合法区间个数要想到考虑有用点对/禁止点对。

在这里“禁止点对”就是那些极小的会形成环的区间，把它们预处理出来（后面再看怎么处理），设 i 向右的极大无环区间是 [i,R_i]。

那么扫左端点，问题就变成了类似于“对于每个 i，求有几个 j\le R_i 满足 [i,j] 形成一棵树”，隐含条件是当 j\le R_i 时保证 [i,j] 无环。

保证无环有什么好处呢？这样经典“点 - 边”容斥就可以正确地给出这个森林的连通块数量。（如果有环，那么一棵基环树的贡献是 0，更复杂的图的贡献是负的，就没法计算连通块数量）

想到把贡献拆成点 - 边之后，我们对每两个相邻的格子 x 和 y 把贡献拍到二维平面 (x,y) 处 -1，再在二维平面上每个 (i,i) 处 +1，那一个区间 [l,r] 的连通块数就是点 (l,r) 右下角的权值和，那问题就变成了求有几个位置权值为 1。进一步观察发现所有位置的权值都 \ge 1，于是扫描线，线段树维护区间最小值以及最小值个数即可。

剩下的问题是怎么找出 i 往右的极长无环区间。题解区都是 LCT，很不理解。

首先发现格子越多越可能形成环，所以 R_i 是关于 i 单调的。这样我们就会考虑双指针和决策单调性。

双指针的话就有两种想法：一种是直接双指针，这样需要支持删除，并查集做不了，于是就出来了 LCT 的做法；另一种是过左端点重构（又称尺取/带删双指针），这样需要支持左右两部分的合并，并查集还是做不了。

那并查集能做啥？能做撤销。

把眼光转向决策单调性，从“撤销”就会自然地想到整体二分。定义函数 solve(l,r,L,R) 求出 [l,r] 内的答案，已知它们的答案取值范围都在 [L,R] 内。这个是很经典的只需要支持撤销的，递归时保证 [r+1,L]（可能为空，分讨）都在并查集内即可。每次求出 mid 的答案，并暴力加入两个子问题 solve(l,mid-1,L,res) 和 solve(mid+1,r,res,R) 所新需要的点，递归求解。

两部分时间复杂度都为 O(nm\log nm)。

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
constexpr int N=2e5+5;
class STree{
    int n,mn[N<<2],cnt[N<<2],tag[N<<2];
    #define k1 (k<<1)
    #define k2 (k<<1|1)
    void setg(int k,int x) { mn[k]+=x; tag[k]+=x; }
    void pushdown(int k) { if(tag[k]) setg(k1,tag[k]),setg(k2,tag[k]),tag[k]=0; }
    void update(int k) { mn[k]=min(mn[k1],mn[k2]); cnt[k]=(mn[k]==mn[k1]?cnt[k1]:0)+(mn[k]==mn[k2]?cnt[k2]:0); }
    void build(int k,int l,int r){
        if(l==r) return mn[k]=0,cnt[k]=1,void();
        int mid=(l+r)>>1; build(k1,l,mid); build(k2,mid+1,r); update(k);
    }
    void modify(int k,int l,int r,int ql,int qr,int x){
        if(ql<=l&&r<=qr) return setg(k,x),void();
        int mid=(l+r)>>1; pushdown(k);
        if(ql<=mid) modify(k1,l,mid,ql,qr,x);
        if(mid+1<=qr) modify(k2,mid+1,r,ql,qr,x);
        update(k);
    }
    int query(int k,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return mn[k]==1?cnt[k]:0;
        int mid=(l+r)>>1,res=0; pushdown(k);
        if(ql<=mid) res+=query(k1,l,mid,ql,qr);
        if(mid+1<=qr) res+=query(k2,mid+1,r,ql,qr);
        return res;
    }
public:
    void init(int _n) { n=_n; build(1,1,n); }
    void modify(int l,int r,int x) { modify(1,1,n,l,r,x); }
    int query(int l,int r) { return query(1,1,n,l,r); }
}T;
class DSU{
    int fa[N],siz[N]; stack<int> S;
    int getfa(int x) { return x==fa[x]?x:getfa(fa[x]); }
public:
    void init(int n) { For(i,1,n) fa[i]=i,siz[i]=1; }
    bool merge(int x,int y){
        x=getfa(x); y=getfa(y); if(x==y) { S.push(0); return false; }
        S.push(y); fa[y]=x; siz[x]+=siz[y]; return true;
    }
    void undo(){
        int y=S.top(); S.pop(); if(y==0) return;
        int x=fa[y]; siz[x]-=siz[y]; fa[y]=y;
    }
}O;
int n,m,a[N],f[N],pi[N],pj[N],vis[N]; vector<int> lis[N];
inline int ID(int i,int j) { return (i-1)*m+j; }
bool Add(int o){
    bool ok=true; vis[o]=1;
    auto work=[&](int u) { if(vis[u]) ok&=O.merge(o,u); };
    if(pi[o]>1) work(a[ID(pi[o]-1,pj[o])]);
    if(pi[o]<n) work(a[ID(pi[o]+1,pj[o])]);
    if(pj[o]>1) work(a[ID(pi[o],pj[o]-1)]);
    if(pj[o]<m) work(a[ID(pi[o],pj[o]+1)]);
    return ok;
}
void Del(int o){
    vis[o]=0;
    auto work=[&](int u) { if(vis[u]) O.undo(); };
    if(pi[o]>1) work(a[ID(pi[o]-1,pj[o])]);
    if(pi[o]<n) work(a[ID(pi[o]+1,pj[o])]);
    if(pj[o]>1) work(a[ID(pi[o],pj[o]-1)]);
    if(pj[o]<m) work(a[ID(pi[o],pj[o]+1)]);
}
void solve(int l,int r,int L,int R){ // guaranteed [r+1,L] filled
    if(l>r) return;
    debug(l,r,L,R);
    if(L==R) { For(i,l,r) f[i]=L;; return; }
    int mid=(l+r)>>1;
    // For(i,1,n*m) assert(vis[i]==(i>r&&i<=L));
    if(r<L){
        Rev(i,r,mid) Add(i);
        int res=L; while(res<R&&Add(res+1)) res++;
        if(res!=R) Del(res+1);
        f[mid]=res; debug(mid,res);
        Rev(i,res,L+1) Del(i);
        solve(l,mid-1,L,res);
        For(i,mid,r) Del(i);
        For(i,L+1,res) Add(i);
        solve(mid+1,r,res,R);
        Rev(i,res,L+1) Del(i);
    }
    else{
        int res=mid-1; while(res<R&&Add(res+1)) res++;
        if(res!=R) Del(res+1);
        f[mid]=res; debug(mid,res);
        Rev(i,res,mid) Del(i);
        For(i,mid,L) Add(i);
        solve(l,mid-1,L,res);
        Rev(i,L,mid) Del(i);
        For(i,r+1,res) Add(i);
        solve(mid+1,r,res,R);
        Rev(i,res,r+1) Del(i);
    }
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m; For(i,1,n) For(j,1,m) cin>>a[ID(i,j)],pi[a[ID(i,j)]]=i,pj[a[ID(i,j)]]=j;
    For(i,1,n) For(j,1,m-1) { int x=a[ID(i,j)],y=a[ID(i,j+1)]; lis[min(x,y)].push_back(max(x,y)); }
    For(i,1,n-1) For(j,1,m) { int x=a[ID(i,j)],y=a[ID(i+1,j)]; lis[min(x,y)].push_back(max(x,y)); }
    O.init(n*m); solve(1,n*m,1,n*m); debuga(f,1,n*m);
    T.init(n*m); ll ans=0;
    Rev(i,n*m,1){
        T.modify(i,n*m,1); for(int x:lis[i]) T.modify(x,n*m,-1);
        ans+=T.query(i,f[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: March 13 Wed, 15 : 07 : 36