首页 > 代码库 > POJ3067 Japan

POJ3067 Japan

2024-08-14 08:45:36   211人阅读

题解:

将一边排序过后就是裸的逆序题了

这里有2种方法

1.add()往下更新,sum()往上更新 求逆序sum(a+1);

2.add)往上更新,sum()往下更新 求逆序sum(maxn)-sum(a);

代码:

1.

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=20100;const int N=110;const int mod=1e9+7;const int INF=1e9;int T,n,m,k;LL c[maxn];P p[maxn*100];int lowbit(int x){return x&-x;}void add(int x){    while(x){        c[x]++;        x-=lowbit(x);    }}LL sum(int x){    LL cnt=0;    while(x<maxn){        cnt+=c[x];        x+=lowbit(x);    }    return cnt;}int main(){    int Case=1;    scanf("%d",&T);    while(T--){        CLR(c);        scanf("%d%d%d",&n,&m,&k);        for(int i=1;i<=k;i++) scanf("%d%d",&p[i].fs,&p[i].se);        sort(p+1,p+k+1);        LL Sum=0;        for(int i=1;i<=k;i++){            Sum+=sum(p[i].se+1);            //cout<<Sum<<endl;            add(p[i].se);        }        printf("Test case %d: %lld\n",Case++,Sum);    }    return 0;}

 

2.

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=20100;const int N=110;const int mod=1e9+7;const int INF=1e9;int T,n,m,k;LL c[maxn];P p[maxn*100];int lowbit(int x){return x&-x;}void add(int x){    while(x<maxn){        c[x]++;        x+=lowbit(x);    }}LL sum(int x){    LL cnt=0;    while(x){        cnt+=c[x];        x-=lowbit(x);    }    return cnt;}int main(){    int Case=1;    scanf("%d",&T);    while(T--){        CLR(c);        scanf("%d%d%d",&n,&m,&k);        for(int i=1;i<=k;i++) scanf("%d%d",&p[i].fs,&p[i].se);        sort(p+1,p+k+1);        LL Sum=0;        for(int i=1;i<=k;i++){            Sum+=sum(maxn)-sum(p[i].se);            //cout<<Sum<<endl;            add(p[i].se);        }        printf("Test case %d: %lld\n",Case++,Sum);    }    return 0;}

 

POJ3067 Japan


联系
我们