首页 > 代码库 > POJ_3067 Japan[ 逆序数 树状数组 or 归并排序)
POJ_3067 Japan[ 逆序数 树状数组 or 归并排序)
传送门:POJ_3067
题目:n,m,k;左右两列数,数的范围分别1-n,1-m,然给k个连线。
Sample Input
1 3 4 4 1 4 2 3 3 2 3 1
Sample Output
Test case 1: 5
思路:逆序数
代码:
//树状数组版
//块状数组 #include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> #include<string> #include<map> #include<vector> #include<queue> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof a) #define read_ freopen("i.txt","r",stdin) using namespace std; typedef long long LL; const int N=1010; int n,m,k; int c[N]; struct node{ int a,b; }p[1000010]; int cmp(node a,node b) { if(a.a==b.a) return a.b<b.b; return a.a<b.a; } int lowbit(int x) { return x&(-x); } void add(int x,int v) { while(x<=m) { c[x]+=v; x+=lowbit(x); } } LL sum(int x) { LL ret=0; while(x>0) { ret=ret+c[x]; x-=lowbit(x); } return ret; } int main() { int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { mem(c,0); scanf("%d%d%d",&n,&m,&k); for(int i=0;i<k;i++) scanf("%d%d",&p[i].a,&p[i].b); sort(p,p+k,cmp); LL ans=0; for(int i=0;i<k;i++){ add(p[i].b,1); ans+=sum(m)-sum(p[i].b); } printf("Test case %d: %I64d\n",cas,ans); } return 0; }
POJ_3067 Japan[ 逆序数 树状数组 or 归并排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。