Codeforces 1043D
题意：求$m$个$n$长排列串的公共子串个数。
考虑排列，我们可以根据 LCS 转 LIS 排列做法的那种做法来记录一个串在另一个串中的位置。这里采用第一个串来作为标准之后，发现每个串有形如$i,i+1,i+2,i+3,…,i+k$的子串则说明这个子串和标准串是公共串。我们如果能找到所有串都存在这个子串，则说明这个串是一个答案。怎么找呢？我们可以枚举每一个$i \in [1,n]$的数来判断是否存在一个从$i$开始的串是所有串的公共子串。
这里可以用二分法来求，即固定$i$(在前面枚举，类似 CF 1073C)，然后二分右边边界。中间每个串用双 Hash 进行判断是否相等。
或者可以尺取法。计算一个从每一个数开始最多形成的合法$i,i+1,i+2,i+3,…,i+k$子串的长度$len_i$。每个串进行枚举，我们每次尺取一个合法子串$i,i+1,i+2,i+3,…,i+k$，更新$i$的答案，由于是所有串公共的，所以取交集，即用 min。然后最后答案为$\sum^{n}_{i=1} len_i$
知识点：
1、N，M看清楚
2、字符串 Hash 同样适用于序列 Hash
3、交集：(l max, r min) 并集：(l min, r max)
4、排列记录一个数在另一个数的位置：CF 1043D，CF 1073B，LCS 转 LIS
5、固定左端点二分区间结束位置：CF 1043D，CF 1073C
//尺取法
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
inline LL readl() {
LL x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int power(int a, int b) {
int ans = 1;
while (b) {
if(b & 1) ans = ans * a;
b >>= 1; a = a * a;
}
return ans;
}
int power_mod(int a, int b, int mod) {
a %= mod;
int ans = 1;
while (b) {
if(b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans;
}
LL powerl(LL a, LL b) {
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = ans * a;
b >>= 1ll;a = a * a;
}
return ans;
}
LL power_modl(LL a, LL b, LL mod) {
a %= mod;
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = (ans * a) % mod;
b >>= 1ll, a = (a * a) % mod;
}
return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
int n, m, ai[15][100005], gg[100005], pos[15][100005], whw[100005];
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) scanf("%d", &ai[i][j]);
for (int i = 1; i <= n; ++i) gg[ai[1][i]] = i, whw[i] = n;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) pos[i][j] = gg[ai[i][j]];
/*for (int i = 1; i <= m; ++i, cerr << endl)
for (int j = 1; j <= n; ++j) cerr << pos[i][j] << " ";*/
//for (int i = 1; i <= n; ++i) cerr << gg[i] << " ";
for (int i = 1; i <= m; ++i) {
int r = 1;
for (int l = 1; l <= n; ++l) {
if (r < l) ++r;
while (r <= n && pos[i][r + 1] == pos[i][r] + 1) ++r;
whw[pos[i][l]] = min(whw[pos[i][l]], pos[i][r]);
}
}
// cerr << "??" << endl;
// for (int i = 1; i <= n; ++i) cerr << whw[i] - i + 1 << " ";
LL ans = 0;
for (int i = 1; i <= n; ++i) ans += (LL)whw[i] - i + 1;
cout << ans;
return 0;
}
