首页 > 代码库 > 51nod 1107(树状数组、逆序数)
51nod 1107(树状数组、逆序数)
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107
思路:其实就是升级版的逆序数,x坐标当作位置,y坐标当作数值val,只是可能有相等的数,稍作修改即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e4 + 3; int lowbit(int x) { return x & (-x); } struct node { int x,y,order; }q[N]; int a[N],c[N],n; bool cmp1(node t1,node t2) { if(t1.x != t2.x) return t1.x < t2.x; return t1.y < t2.y; } bool cmp2(node t1,node t2) { if(t1.y != t2.y) return t1.y < t2.y; return t1.order < t2.order; } void update(int pos,int val) { for(int i = pos; i <= n; i += lowbit(i)) c[i] += val; } int sum(int pos) { int ans = 0; for(int i = pos; i > 0; i -= lowbit(i)) ans += c[i]; return ans; } int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%d %d",&q[i].x,&q[i].y); sort(q+1,q+n+1,cmp1); for(int i = 1; i <= n; i++) q[i].order = i; sort(q+1,q+n+1,cmp2); for(int i = 1; i <= n; i++) a[q[i].order] = i; int ans = 0; for(int i = 1; i <= n; i++) { update(a[i],1); ans += i - sum(a[i]); } printf("%d\n",ans); return 0; }
51nod 1107(树状数组、逆序数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。