特殊矩阵の压缩存储

矩阵图像如下所示。

$\begin{vmatrix}a_{11}&a_{12}&...&a_{1n}\\a_{21}&a_{22}&...&a_{2n}\\...\\a_{n1}&a_{n2}&...&a_{nn}\end{vmatrix}$

共$N\times N$个元素。

1. 对称矩阵：

• 一个$n$行$n$列对称矩阵图像特点如下所示：

1. $a_{ij}=a_{ji}(i,j\le n)$。
2. 图像可分为上三角和下三角，两个三角图案全等。

下三角（$i\ge j$）：
$\begin{vmatrix}a_{11}\\a_{21}&a_{22}\\a_{31}&a_{32}&a_{33}\\...\\a_{n1}&a_{n2}&a_{n3}&...&a_{nn}\end{vmatrix}$

上三角（$i<j$）的图差不多就不画了。

我们假设存储下三角的一维数组 （需要$\frac{N\times(N+1)}{2}$的空间，压缩了一半） 是数组$b$，且数组下标从$1$开始。

那么我们的$a_{ij}$存到$b$数组里的$k$（也是从$1$开始）和$i,j$有以下关系：

$k=\frac{(i-1)*n}{2}+j$

第一部分$\frac{(i-1)*n}{2}$指$\begin{vmatrix}a_{11}\\a_{21}&a_{22}\\a_{31}&a_{32}&a_{33}\\...\\a_{i1}&a_{i-1,2}&a_{i-1,3}&...&a_{i-1,j-1}\end{vmatrix}$的元素个数。

第二部分$j$指第$i$行还有第$j$个。

以存储下三角为例，代码：

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*(N+1)/2];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	fs(i,1,n,1){
		fs(j,1,n,1){
			cin>>a;
			if(i>=j){
				downsj[i*(i-1)/2+j]=a;
			}
		}
	}
	fs(i,1,q,1){
		int x,y;
		cin>>x>>y;
		if(x<y) swap(x,y);
		cout<<downsj[x*(x-1)/2+y]<<endl;
	}
	return 0;
}

2. 三角矩阵

三角矩阵分为上三角矩阵和下三角矩阵，这里以下三角为例。

• 一个$n$行$n$列下三角矩阵图像特点如下所示：
• 若$i<j,a_{ij}=c(i,j\le n)$（$c$是常数）。
  $\begin{vmatrix}a_{11}&c&...&c\\a_{21}&a_{22}&...&c\\...\\a_{n1}&a_{n2}&...&a_{nn}\end{vmatrix}$

存储方法：

和对称矩阵相同，存储下三角，在询问时若询问上三角就直接回答上三角即可。

以存储下三角为例，代码：

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*(N+1)/2],c;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	fs(i,1,n,1){
		fs(j,1,n,1){
			cin>>a;
			if(i>=j){
				downsj[i*(i-1)/2+j]=a;
			}else{
				c=a; 
			}
		}
	}
	fs(i,1,q,1){
		int x,y;
		cin>>x>>y;
		if(x<y) cout<<c<<endl;
		else cout<<downsj[x*(x-1)/2+y]<<endl;
	}
	return 0;
}

那么上三角呢？

我们观察这个矩阵。
$\begin{vmatrix}a_{11}&a_{12}&a_{13}&...&a_{1n}\\c&a_{22}&a_{23}&...&a_{2n}\\c&c&a_{33}&...&a_{3n}\\...\\c&c&c&...&a_{nn}\end{vmatrix}$

会发现，若$i>j,$则$a_{ij}=c$。

否则，$i\le j,$则$k$和$i,j$的关系如下所示：

$k=\frac{(n-i+2+n)\times(i-1)}{2}+j-i+1=\frac{(i-1)\times(2n-i+2)}{2}+j-i+1$

• 第一部分$\frac{(n-i+2+n)\times(i-1)}{2}$指代$\begin{vmatrix}a_{11}&a_{12}&a_{13}&...&a_{1n}\\c&a_{22}&a_{23}&...&a_{2n}\\c&c&a_{i-1,3}&...&a_{i-1,n}\end{vmatrix}$中，$a_{...}$的个数。
• 第二部分$j-i+1$为$\begin{vmatrix}c&c&...&a_{i,i}&a_{i,i+1}&...&a_{i,j-1}&a_{i,j}\end{vmatrix}$中$i,j$中的个数。

代码：

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*(N+1)/2],c;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    fs(i,1,n,1){
        fs(j,1,n,1){
            cin>>a;
            if(i>j){
                c=a;
            }else{
                downsj[(2*n-i+2)*(i-1)/2+j-i+1]=a;
            }
        }
    }
    fs(i,1,q,1){
        int x,y;
        cin>>x>>y;
        if(x>y) cout<<c<<endl;
        else cout<<downsj[(2*n-x+2)*(x-1)/2+y-x+1]<<endl;
    }
    return 0;
}

3. 对角矩阵

对角矩阵的特点如下：

• 基本所有非$c$元素集结在对角线旁，共$l$条对角线（$l\bmod2=1$），称为$l$对角矩阵。

则半带宽$d=\frac{l+1}{2}$。

矩阵如下所示：$\begin{vmatrix}a_{11}&a_{12}&...&c&c&...&c\\a_{21}&a_{22}&...&c&c&...&c\\c&a_{32}&a_{33}&a_{34}&c&...&c\\...\\c&c&c&c&...&a_{n-1,n}&a_{nn}\end{vmatrix}$

存储方法：

• 总共需要$l\times n-2\times d$空间。
• 对于每一条对角线，先补上$0$直到有意义的每一行长度都是$l$。
• Pass掉$1$行前面的$d$个$0$和$n$行最后的$d$个$0$。
• 公式如下所示（其实我也没理解，老师还打错了，还讲的好好的）：

$k=\begin{cases}(i-1)\times l+j-i&|i-j|<d\\c&|i-j|\ge d\end{cases}$

代码：

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*N-2*N],c,d,l;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>l;d=(l+1)/2;
    fs(i,1,n,1){
        fs(j,1,n,1){
            cin>>a;
            if(abs(i-j)>=d){
                c=a;
            }else{
                downsj[(i-1)*l+j-i]=a;
            }
        }
    }
    fs(i,1,q,1){
        int x,y;
        cin>>x>>y;
        if(abs(x-y)>=d) cout<<c<<endl;
        else cout<<downsj[(x-1)*l+y-x]<<endl;
    }
    return 0;
}