CF1566D2 题解

题意 & 简单分析在 D1

沿着 D1 的思路，我们只需要维护当前进入的人，所在行视力比他差的人的个数，这个可以用树状数组维护每一行。但 a_i 的范围很大，且只需要大小关系，可以离散化。

但如果同一视力的人跨越了很多行呢？同样顺延 D1 的贪心，因为不要求输出方案，同一行里随便进，先进靠前的行。这个实际也比较好想，因为在靠前的交界处这个人的列数必定靠后，先放这个必然不会更劣。处理就是离散化的时候用 stable_sort，顺便处理出每个人的位置，就可以保证进入时间靠前的位置也靠前。

详见代码

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
#define lowbit(x) x&-x 
using namespace std;
map<int,int> mp;
struct node {
    int elem,id;
    bool operator<(const node b) const {
        return this->elem<b.elem;
    }
}a[100005],b[100005];
int cnt,n,m;
int tree[305][90005];
//树状数组板子
//p是行数，每行用一个树状数组维护
inline void update(int p,int x) {
    for(;x<=cnt;x+=lowbit(x)) tree[p][x]++;
}
inline int query(int p,int x){
    int sum=0;
    for(;x;x-=lowbit(x)) sum+=tree[p][x];
    return sum;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n*m;i++)
            scanf("%d",&a[i].elem),b[i].elem=a[i].elem,b[i].id=i;
        stable_sort(b+1,b+n*m+1);
        mp.clear(),cnt=0;
        for(int i=1;i<=n*m;i++) {
            a[b[i].id].id=i;//a.id表示该人座位
            //离散化
            if(mp.find(b[i].elem)==mp.end()) mp[b[i].elem]=++cnt;
        }
        //十年CF一场空，memset见祖宗
        for(int i=1;i<=n;i++)
            for(int j=1;j<=cnt;j++)
                tree[i][j]=0;
        for(int i=1;i<=n*m;i++) {
            int l=(a[i].id-1)/m+1;//该人的行数
            //树状数组里存的是离散化后对应值的个数
            //所以query直接查询小于当前值的前缀和就是所需
            ans+=query(l,mp[a[i].elem]-1);
            update(l,mp[a[i].elem]);
        }
        cout<<ans<<'\n';
    } 
    return 0;
}