题解 SP4226 【MSE06H - Japan】

AmadeusSG · 2019-01-26 10:11:49 · 题解

树状数组求逆序对

先把东边城市排个序，然后求西边城市的逆序对就行了。

考虑到数据范围，本人用的树状数组实现。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=1000000+5;
ll n,m,ans,k;
ll A[maxn],C[maxn]/*Tree[]*/,D[maxn]/*离散化*/;
string s;
ll x,y;
struct way{int w,e;}g[maxn];
inline bool cmp(way x,way y)
{
    if(x.e==y.e)return x.w<=y.w;
    return x.e<y.e;
}
inline ll read()
{
    ll x=0;
    char c=getchar();
    bool f=false;
    while(!isdigit(c))
    {
        if(c=='-')f=true;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f?-x:x;
}
inline ll LowBit(ll k){return k&(-k);}//lowbit技术
ll Get_Sum(ll x)//求和操作
{
    ll ans=0;
    for(ll i=x;i>0;i-=LowBit(i))ans+=C[i];
    return ans;
}
inline void Update(ll x,ll d)//更新操作
{for(ll i=x;i<=m;i+=LowBit(i))C[i]+=d;}
void Discretize()
{
    sort(D+1,D+1+m);
    unique(D+1,D+1+m)-D-1;
    for(ll i=1;i<=m;i++)A[i]=lower_bound(D+1,D+1+m,A[i])-D;
}
int main()
{
    ll i,j,T;
    T=read();
    for(ll oo=1;oo<=T;oo++)
    {   
        ans=0;
        n=read();m=read();k=read();
        for(i=1;i<=k;i++)g[i].e=read(),g[i].w=read();
        sort(g+1,g+k+1,cmp);
        memset(C,0,sizeof(C));
        //for(i=1;i<=m;i++)A[i]=D[i]=g[i].w;
        //Discretize();
        for(i=1;i<=k;i++)
        {
            Update(g[i].w,1);
            ans+=(i-Get_Sum(g[i].w));
        }
        printf("Test case %lld: %lld\n",oo,ans);
    }
    return 0;
}