题解：P11048 [蓝桥杯 2024 省 Java B] 拼十字

Lysra · 2024-11-14 23:22:11 · 题解

提供一种双指针二位偏序写法。

首先分三类讨论，将颜色 0、1、2 分开来，避免多统计。

接着我们考虑将当前颜色矩阵与非当前颜色矩阵都按照 l 从小到大排序，这样后满足 l_i< l_j 的 j 指针就可以做到单调不降了。

至于 c_i>c_j，用树状数组维护即可。

注意取模，注意不取等。

代码：

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
#define lowbit(x) (x&(-x))
using namespace std;
struct node{
    int l,w;
}e[N],d[N];
const int mx=1e5,M=1e9+7;
int n,l[N],w[N],c[N],cnte,cntd,t[N],ans;
bool cmp(node x,node y){
    return x.l<y.l;
}
void add(int x,int y){
    for(int i=x;i<=mx;i+=lowbit(i)) t[i]+=y;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=t[i];
    return res;
}
void solve(int x){
    cnte=cntd=0;
    for(int i=1;i<=n;i++){
        if(c[i]==x) e[++cnte]={l[i],w[i]};
        else d[++cntd]={l[i],w[i]};
    }
    sort(d+1,d+cntd+1,cmp),sort(e+1,e+cnte+1,cmp);
    int j=1;
    for(int i=1;i<=cnte;i++){
        while(j<=cntd&&d[j].l<e[i].l) add(d[j].w,1),j++;
        ans=(ans+query(mx)-query(e[i].w))%M;
    }
    for(int i=1;i<j;i++) add(d[i].w,-1);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>w[i]>>c[i];
    for(int T=0;T<=2;T++) solve(T);
    cout<<ans;
    return 0;
}