LuoguP6687 论如何玩转 Excel 表格 树状数组

找规律+猜结论.     

不难发现这个旋转 180 度其实是对于一个 $2 imes 2$ 的正方形内部对角线分别交换.    

所以对于这个 $2 imes n$ 的数组来说可以将所有格子分成两类，这两类互不干扰.   

那么判断是否合法的条件之一就是初态和末态对应种类的格子应该相同.     

即 $(1,1)$，$(2,2)$，$(3,1)$，$(4,2)$ 与 $(1,2)$，$(2,1)$ ，$(3,2)$ ，$(4,1)$......

如果只考虑将一类变相同只需求这一类的初态相对于末态的逆序对即可.    

然后我们猜测出的一个结论就是对于每一列的两行在对应类别中的排名应该相同才可以.     

这样的话随便对一个状态用树状数组求一下逆序对个数即可.  

code: 

#include <cstdio> 
#include <cstring>
#include <algorithm>
#define N 2000009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n;
int bu[N],sum[N];  
int a[2][N],b[2][N],A[2][N],B[2][N],c[2][N],d[2][N];   
int lowbit(int x) {
    return x&(-x); 
}      
void update(int x) {
    for(;x<=n;x+=lowbit(x)) 
        ++sum[x];  
}
int query(int x) {
    int tmp=0; 
    for(;x;x-=lowbit(x)) 
        tmp+=sum[x];  
    return tmp;  
}
char *p1,*p2,buf[100000];  
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) 
int rd() {
    int x=0; char c;  
    do {
        c=nc(); 
    }while(c<48);  
    while(c>47) {
        x=(((x<<2)+x)<<1)+(c^48),c=nc();  
    }  
    return x;  
}
int main() {
    // setIO("input");
    n=rd(); 
    for(int i=0;i<2;++i) {
        for(int j=1;j<=n;++j) a[i][j]=rd(); 
    }
    for(int i=0;i<2;++i) {
        for(int j=1;j<=n;++j) b[i][j]=rd(); 
    }
    int x,y,z;
    for(int i=0;i<2;++i) {
        y=i;  
        for(int j=1;j<=n;++j) {
            c[i][j]=A[i][j]=a[y][j];  
            y^=1;        
        }
    }
    for(int i=0;i<2;++i) {
        y=i;   
        for(int j=1;j<=n;++j) {
            d[i][j]=B[i][j]=b[y][j];   
            bu[B[i][j]]=j;    
            y^=1;    
        }
    }
    sort(c[0]+1,c[0]+1+n);    
    sort(c[1]+1,c[1]+1+n);    
    sort(d[0]+1,d[0]+1+n); 
    sort(d[1]+1,d[1]+1+n);     
    for(int i=0;i<2;++i) {
        for(int j=1;j<=n;++j) {
            if(c[i][j]!=d[i][j]) {
                printf("dldsgay!!1
");   
                return 0;  
            }
        }
    }
    for(int i=1;i<=n;++i) {
        if(bu[a[0][i]]!=bu[a[1][i]]) {
            printf("dldsgay!!1
");  
            return 0;  
        }
    }
    ll ans=0;  
    for(int i=n;i>=1;--i) {
        int nu=A[0][i];    
        ans+=query(bu[nu]);   
        update(bu[nu]);  
    }
    printf("%lld
",ans);  
    return 0;
}