题解：CF706E Working routine

· · 题解

在 Print 之前

这道题是在比赛中遇到的，看着有点久远了，但码量有点大，赛时只打了暴力，没写出正解。

原题

暴力

事实上暴力十分简单，在每次交换时只是交换位置的话会更快一些。

时间复杂度：O(q\times n \times m)。

Code

#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
    using namespace std;
    inline ll read() {
        char x=getchar();
        ll ans=0,f=1;
        while(x<'0'||x>'9') {
            if(x=='-') {
                f*=(-1);
            }
            x=getchar();
        }
        while(x>='0'&&x<='9') {
            ans*=10;
            ans+=(x-'0');
            x=getchar();
        }
        return ans*f;
    }
    inline void print(ll x) {
        if(x<0) {
            putchar('-');
            x=-x;
        }
        if(x>=10) {
            print(x/10);
            putchar(x%10+'0');
        }
        else {
            putchar(x+'0');
        }
    }
}
using namespace io;
const ll N=1e3+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll num[N][N],n,m,q;
pll kl[N][N];
string a[N][N];
inline void solve() {
    cin>>n>>m>>q;
    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=m;j++) {
            cin>>a[i][j];
            num[i][j]=(i-1)*m+j;
        }
    }
    while(q--) {
        ll x,y,xl,yl,len,cl;
        cin>>x>>y>>xl>>yl>>len>>cl;
        for(ll i=0;i<len;i++) {
            for(ll j=0;j<cl;j++) {
                swap(num[x+i][y+j],num[xl+i][yl+j]);
            }
        }
    }
    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=m;j++) {
            ll num1=num[i][j]%m,num2=(num[i][j]-num1)/m+1;
            if(num1==0) {
                num2--;
                num1+=m;
            }
            cout<<a[num2][num1]<<' ';
        }
        cout<<'\n';
    }
}
praise_long_long main() {
//  freopen("file.in","r",stdin);
//  freopen("file.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll T=1;
//  T=read();
    while(T--) {
        solve();
    }
    return 0;
}
/**/

正解

我们可以想象一下，每次只交换两个不相交的两个相同长宽的矩形就像不像在一块布上剪下两块交换后缝好？

不难发现，如果能够只在四边进行操作，而不在内部每一个点上进行转换，时间复杂度会大大降低，但什么数据结构能够在 O(1) 的复杂度内大面积交换呢？

如果是一维的转换我们可以想到链表，那么二维转换我们可以想到四向链表，在每次访问时只需要修改四周指向的位置，时间复杂度就减下来了。

时间复杂度：O(q \times (n+m))。

Code

#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
    using namespace std;
    inline ll read() {
        char x=getchar();
        ll ans=0,f=1;
        while(x<'0'||x>'9') {
            if(x=='-') {
                f*=(-1);
            }
            x=getchar();
        }
        while(x>='0'&&x<='9') {
            ans*=10;
            ans+=(x-'0');
            x=getchar();
        }
        return ans*f;
    }
    inline void print(ll x) {
        if(x<0) {
            putchar('-');
            x=-x;
        }
        if(x>=10) {
            print(x/10);
            putchar(x%10+'0');
        }
        else {
            putchar(x+'0');
        }
    }
}
using namespace io;
const ll N=1e3+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
struct List {
    ll left,right,up,down,val;
} lst[N*N];
ll n,m,q;
string a[N][N];
inline void insert(ll val) {
    ll num=val%(m+2),numl=val/(m+2);
    ll up=(numl-1)*(m+2)+num,down=(numl+1)*(m+2)+num,left=val-1,right=val+1;
    lst[val]={left,right,up,down,val};
}
inline ll find(ll rt,ll sp) {
    for(ll i=lst[rt].right;;i=lst[i].right) {
        sp--;
        if(!sp) {
            return lst[i].val;
        }
    }
    return 0;
}
inline void query(ll x,ll y,ll xl,ll yl,ll len,ll cl) {
    ll num=find(x*(m+2),y),numl=find(xl*(m+2),yl);
    ll kl=num,kll=numl;
    for(ll i=1;i<=len;i++) {
        ll p1=lst[kl].left,p2=lst[kll].left;
        swap(lst[p1].right,lst[p2].right);
        swap(lst[kl].left,lst[kll].left);
        if(i==len) {
            break;
        }
        kl=lst[kl].down,kll=lst[kll].down;
    }
    for(ll i=1;i<=cl;i++) {
        ll p1=lst[kl].down,p2=lst[kll].down;
        swap(lst[p1].up,lst[p2].up);
        swap(lst[kl].down,lst[kll].down);
        if(i==cl) {
            break;
        }
        kl=lst[kl].right,kll=lst[kll].right;
    }
    for(ll i=1;i<=len;i++) {
        ll p1=lst[kl].right,p2=lst[kll].right;
        swap(lst[p1].left,lst[p2].left);
        swap(lst[kl].right,lst[kll].right);
        if(i==len) {
            break;
        }
        kl=lst[kl].up,kll=lst[kll].up;
    }
    for(ll i=1;i<=cl;i++) {
        ll p1=lst[kl].up,p2=lst[kll].up;
        swap(lst[p1].down,lst[p2].down);
        swap(lst[kl].up,lst[kll].up);
        if(i==cl) {
            break;
        }
        kl=lst[kl].left,kll=lst[kll].left;
    }
}
inline void output(ll x) {
    for(ll i=lst[x].right;i!=x+m+1;i=lst[i].right) {
        ll xl=(lst[i].val)/(m+2),yl=(lst[i].val)%(m+2);
        cout<<a[xl][yl]<<' ';
    }
    cout<<'\n';
}
inline void solve() {
    cin>>n>>m>>q;
    for(ll i=1;i<=m;i++) {
        lst[(n+1)*(m+2)+i]={0,0,n*(m+2)+i,0,(n+1)*(m+2)+i};
        lst[i]={0,0,0,m+2+i,i};
    }
    for(ll i=1;i<=n;i++) {
        lst[i*(m+2)]={0,i*(m+2)+1,0,0,i*(m+2)};
        lst[i*(m+2)+m+1]={i*(m+2)+m,0,0,i*(m+2)+m+1};
    }
    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=m;j++) {
            cin>>a[i][j];
            insert(i*(m+2)+j);
        }
    }
    while(q--) {
        ll x,y,xl,yl,len,cl;
        cin>>x>>y>>xl>>yl>>len>>cl;
        query(x,y,xl,yl,len,cl);
    }
    for(ll i=1;i<=n;i++) {
        output(i*(m+2));
    }
}
praise_long_long main() {
//  freopen("file.in","r",stdin);
//  freopen("file.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T=1;
//  T=read();
    while(T--) {
        solve();
    }
    return 0;
}
/**/