专栏首页wymHDU 6318 树状数组求逆序数

HDU 6318 树状数组求逆序数

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6318

#define N 100005 #include <bits/stdc++.h> using namespace std; int c[N];  int n; int lowbit(int i) {     return i&(-i); } int insert(int i,int x) {     while(i<=n){         c[i]+=x;         i+=lowbit(i);     }     return 0; }

int getsum(int i) {     int sum=0;     while(i>0){         sum+=c[i];         i-=lowbit(i);     }      return sum; } void output() {     for(int i=1;i<=n;i++) cout<<c[i]<<" ";     cout<<endl; } struct node{     int v;     int id;     bool operator <(const node &b)const{     if(v==b.v)      return id<b.id;      else return v<b.v;     } }; node a[N]; int main() {     int x,y;     while(~scanf("%d %d %d",&n,&x,&y)){         long long ans=0;         memset(c,0,sizeof(c));         for(int i=1;i<=n;i++){             scanf("%d",&a[i].v);             a[i].id=i;         }         sort(a+1,a+1+n);         for(int i=1;i<=n;i++)             {             insert(a[i].id,1);             ans+=i-getsum(a[i].id);//统计当前序列中大于a的元素的个数          }         cout<<ans*min(x,y)<<endl;     }     return 0; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • 区间更新与点值

    用户2965768
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • 01:数制转换

    01:数制转换 总时间限制: 1000ms 内存限制: 65536kB描述 求任意两个不同进制非负整数的转换(2进制~16进制),所给整数在long所能表达...

    attack
  • 写一个程序检查一个整数是2的幂?

    用户4645519
  • C语言中一些不被熟知的特性

    限定词restricted用于限定一个指针(如名,告诉编译器该指针的内存访问在任何情况下都只能通过该指针进行,其余指向无效.如

    racaljk
  • Codeforces Round #186 (Div. 2)A、B、C、D、E

    Ilya得到了一个礼物,可以在删掉银行账户最后和倒数第二位的数字(账户有可能是负的),也可以不做任何处理。

    xindoo
  • 天池在线编程限时赛 --- 【夕阳下的奔跑场】脱单队

    杨鹏伟
  • 挑战程序竞赛系列(26):3.5二分图匹配(1)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 力扣(LeetCode)刷题,简单题(第19期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿

扫码关注云+社区

领取腾讯云代金券