Description

給出一個 $n?m$ 的網格圖，保證所有位置上的數形成一個 $1?n?m$ 的排列。

問有多少個值域區間 $[l,r]$ 滿足，在 $[l,r]$ 中的數在網格圖上的位置形成一棵樹。

$n?m\le 200000,n,m\le 1000$

題目鏈接：Codeforces 1109F. Sasha and Algorithm of Silence’s Sounds

Solution

• 考慮到形成一棵樹要同時滿足兩個條件：無環、連通 。

• 維護兩個指針 $l,r$ ，表示當前做到的值域范圍。

• 每次將 $r$ 右移一位，用 LCT 維護最小的 $l$ 使得將 $[l,r]$ 的點加入后沒有成環，即森林（條件①）。

• 那么我們要計算的就是這個區間內有多少個 $l^{\prime }$ 使得 $[l^{\prime },r]$ 滿足條件。

• 由于 連通塊個數 = 點數 - 邊數 ，那么我們維護一棵線段樹記錄每個位置的 “點數 - 邊數” 。

• 注意到這個值是非負的，于是線段樹統計區間最小值及其個數，支持區間加減和區間查詢即可。

• 我們看看區間 $[l,r]$ 內的最小值是不是 $1$ ，是就加上其個數就可以了（條件②）。

• 時間復雜度 $O(nmlog(nm))$ 。

Code

#include<cstdio> #include<algorithm> #include<cctype> using namespace std; typedef pair<int,int> PI; const int N=2e5+5,M=1005; const int way[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; struct node {int x,y; }a[N]; int n,m,up,top,qx,qy,qz; long long ans; int fa[N],s[N][2],st[N]; bool rev[N]; PI f[N<<2]; int b[M][M],c[N<<2]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline bool isroot(int x) {return x^s[fa[x]][0] && x^s[fa[x]][1]; } inline void rotate(int x) {int y=fa[x],w=pd(x);if((fa[x]=fa[y]) && !isroot(y)) s[fa[y]][pd(y)]=x;if(s[y][w]=s[x][w^1]) fa[s[y][w]]=y;s[fa[y]=x][w^1]=y; } inline void reverse(int x) {if(x) swap(s[x][0],s[x][1]),rev[x]^=1; } inline void down(int x) {if(rev[x]){reverse(s[x][0]),reverse(s[x][1]);rev[x]=false;} } inline void splay(int x) {for(int y=st[top=1]=x;!isroot(y);y=fa[y]) st[++top]=fa[y];while(top) down(st[top--]);for(int y;!isroot(x);rotate(x))if(!isroot(y=fa[x])) rotate(pd(x)==pd(y)?y:x); } inline void access(int x) {for(int y=0;x;x=fa[y=x]) splay(x),s[x][1]=y; } inline void mkroot(int x) {access(x),splay(x),reverse(x); } inline void link(int x,int y) {mkroot(x),fa[x]=y; } inline void cut(int x,int y) {mkroot(x),access(y),splay(y);s[y][0]=fa[x]=0; } inline bool connect(int x,int y) {mkroot(x),access(y),splay(y);while(s[y][0]) y=s[y][0];return x==y; } inline void down1(int v) {if(c[v]){f[v<<1].first+=c[v];f[v<<1|1].first+=c[v];c[v<<1]+=c[v];c[v<<1|1]+=c[v];c[v]=0;} } void make(int v,int l,int r) {if(l==r){f[v].second=1;return;}int mid=l+r>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);f[v].second=f[v<<1].second+f[v<<1|1].second; } PI cmin(PI x,PI y) {if(x.first<y.first) return x;if(x.first>y.first) return y;return make_pair(x.first,x.second+y.second); } void change(int v,int l,int r) {if(qx<=l && r<=qy){f[v].first+=qz;c[v]+=qz;return;}down1(v);int mid=l+r>>1;if(qx<=mid) change(v<<1,l,mid);if(qy>mid) change(v<<1|1,mid+1,r);f[v]=cmin(f[v<<1],f[v<<1|1]); } PI find(int v,int l,int r) {if(qx<=l && r<=qy) return f[v];down1(v);int mid=l+r>>1;PI val(N,0);if(qx<=mid) val=find(v<<1,l,mid);if(qy>mid) val=cmin(val,find(v<<1|1,mid+1,r));return val; } inline bool judge(int l,int r) {for(int i=0;i<3;i++){int x=a[r].x+way[i][0],y=a[r].y+way[i][1];if(!x || x>n || !y || y>m) continue;if(b[x][y]<l || b[x][y]>r) continue;for(int j=i+1;j<4;j++){int xx=a[r].x+way[j][0],yy=a[r].y+way[j][1];if(!xx || xx>n || !yy || yy>m) continue;if(b[xx][yy]<l || b[xx][yy]>r) continue;if(connect(b[x][y],b[xx][yy])) return true;}}return false; } inline void del(int l) {for(int i=0;i<4;i++){int x=a[l].x+way[i][0],y=a[l].y+way[i][1];if(!x || x>n || !y || y>m) continue;if(connect(b[x][y],l))cut(b[x][y],l);} } inline void add(int l,int r) {for(int i=0;i<4;i++){int x=a[r].x+way[i][0],y=a[r].y+way[i][1];if(!x || x>n || !y || y>m) continue;if(l<=b[x][y] && b[x][y]<r){link(b[x][y],r);qx=1,qy=b[x][y],qz=-1;change(1,1,up);}}qx=l,qy=r,qz=1;change(1,1,up); } int main() {n=read(),m=read(),up=n*m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){b[i][j]=read();a[b[i][j]]=(node){i,j};}make(1,1,up);for(int i=1,j=1;i<=up;i++){while(judge(j,i)) del(j++);add(j,i);qx=j,qy=i;PI sum=find(1,1,up);ans+=sum.first==1?sum.second:0;}printf("%I64d",ans);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Codeforces 1109F. Sasha and Algorithm of Silence's Sounds的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。