原题传送门
题意：给定n个序列，每个序列有m个数。且这n * m个数互不相同。
定义f(A,B)：将A、B两个数组合在一起升序排列后，记为数组C。
则f(A,B)为A数组中所有数在C数组中的下标之和。
求对于所有1<=i<j<=n,f(i,j)的和。
性质：可以大胆地排序，因为它只关心相对位置
硬算显然T飞，考虑批量计算贡献。
再看i和j的限制，十分灵性啊，一眼：倒着搞，就可以对于每一个i，把大于它的j都算进去，且只需要搞一遍。
每次只不过是查询一下排名罢了，随便选个ds就行了，比如优美的树状数组。当然我懒，直接复制了自己以前写的Treap板子（别学我。
但是要注意，对于每个数在计算贡献的时候还要加上它之后（也就是此时ds里面已经维护了的（不包含当前数组））数组的数量，这个简单地打个草稿就能理解。
然后就结束了（你看这场的F是不是很水（
还是贴个码，
#include<bits/stdc++.h>
using namespace std;
#define re
#define int long long
const int N=10010,M=110;
const int INF=1e10;
int idx,root;
int n,m,a[N][M],ans;
struct node{
int l,r;
int key,val;
int cnt,size;
}tr[N*M];
int get_node(int key){
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=1;
tr[idx].size=1;
return idx;
}
void push_up(int id){
tr[id].size=tr[tr[id].l].size+tr[tr[id].r].size+tr[id].cnt;
}
void build(){
root=get_node(-INF),tr[1].r=get_node(INF);
push_up(root);
}
void zig(int &p){
int q=tr[p].r;
tr[p].r=tr[q].l;
tr[q].l=p;
p=q;
push_up(tr[p].l);
push_up(p);
}
void zag(int &p){
int q=tr[p].l;
tr[p].l=tr[q].r;
tr[q].r=p;
p=q;
push_up(tr[p].r);
push_up(p);
}
void insert(int x,int &p){
if(!p){
p=get_node(x);
return;
}
if(tr[p].key==x)tr[p].cnt++;
else{
if(x<tr[p].key){
insert(x,tr[p].l);
if(tr[tr[p].l].val>tr[p].val)zag(p);
}
else{
insert(x,tr[p].r);
if(tr[tr[p].r].val>tr[p].val)zig(p);
}
}
push_up(p);
}
int get_rank(int x,int p){
if(!p)return 0;
if(tr[p].key==x)return tr[tr[p].l].size+1;
if(x<tr[p].key)return get_rank(x,tr[p].l);
return tr[tr[p].l].size+tr[p].cnt+get_rank(x,tr[p].r);
}
inline int read(){
re 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<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
signed main(){
build();
n=read(),m=read();
for(re int i=1;i<=n;i++)for(re int j=1;j<=m;j++)a[i][j]=read();
for(re int i=1;i<=m;i++)insert(a[n][i],root);
for(re int i=n-1;i;i--){
sort(a[i]+1,a[i]+1+m);
for(re int j=1;j<=m;j++){
int g=get_rank(a[i][j],root)-1;
ans+=g+(n-i)*j;
}
for(re int j=1;j<=m;j++)insert(a[i][j],root);
}
printf("%lld",ans);
return 0;
}