P1908-逆序对

喜欢ヅ旅行 2021-11-09 07:40 331阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     4 const int maxn = 500009;
     5 typedef long long ll;
     6 int n;
     7 ll a[maxn],c[maxn];
     8 ll ans = 0;
     9 inline ll read()
    10 {
    11     ll ans = 0;
    12     char ch = getchar(), last = ' ';
    13     while(!isdigit(ch)) last = ch, ch = getchar();
    14     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    15     if(last == '-') ans = -ans;
    16     return ans;
    17 }
    18 inline void write(ll x)
    19 {
    20     if(x < 0) x = -x, putchar('-');
    21     if(x >= 10) write(x / 10);
    22     putchar(x % 10 + '0');
    23 }
    24 void msort(int le,int rr)
    25 {
    26     if(le==rr)
    27         return ;
    28     int mid = (le+rr)/2;
    29     msort(le,mid),msort(mid+1,rr);
    30     int i = le,j = mid+1;
    31     int k = le;
    32     while(i <= mid && j <= rr)
    33     {
    34         if(a[i]<=a[j])
    35             c[k++] = a[i++];
    36         else
    37         {
    38             c[k++] = a[j++];
    39             ans += mid-i+1;
    40         }
    41     }
    42     memcpy(c+k,a+i,(mid-i+1)*(sizeof(ll)));
    43     k += mid-i+1;
    44     memcpy(c+k,a+j,(rr-j+1)*(sizeof(ll)));
    45     memcpy(a+le,c+le,(rr-le+1)*(sizeof(ll)));
    46 }
    47 int main()
    48 {
    49     n = read();
    50     _for(i,0,n)
    51     a[i] = read();
    52 
    53     msort(0,n-1);
    54     write(ans);
    55     return 0;
    56 }

转载于:https://www.cnblogs.com/Asurudo/p/11258504.html

发表评论取消回复

表情：

评论列表（有 0 条评论，331人围观）

还没有评论，来说两句吧...

相关阅读

相关 P1908 逆序对

P1908 逆序对题意： > 给你一个长度为 $ n $ 的数组，求其中的逆序对数量。解法： > 数据范围很大 $ (n \\leq 5 \\t...

冷不防/ 2024年04月20日 10:33/ 0 赞/ 71 阅读

相关 P1908 逆序对 (归并排序实现)

题目描述 > 猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之

朱雀/ 2023年05月29日 11:56/ 0 赞/ 234 阅读

相关求逆序对

题型: 编程题语言: 不限定 Description 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列

ゞ浴缸里的玫瑰/ 2023年02月11日 03:21/ 0 赞/ 19 阅读

相关 P3531 [POI2012]LIT-Letters（求逆序对）

题目传送门：[https://www.luogu.com.cn/problem/P3531][https_www.luogu.com.cn_problem_P3531] 题

布满荆棘的人生/ 2022年12月31日 01:26/ 0 赞/ 122 阅读

相关 1013 逆序对

Description 给定一个长度为N的int型数组a[0,1,2,...N-1], 请计算逆序对个数.当i<j且a[i]>a[j], 则称a[i]与a[j]是一对

墨蓝/ 2022年09月11日 15:21/ 0 赞/ 177 阅读

相关洛谷P1908 逆序对

题目描述猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“

客官°小女子只卖身不卖艺/ 2022年05月30日 06:44/ 0 赞/ 208 阅读

相关逆序对数目 java

逆序对数目 java 题目描述：设A\[1…n\]是一个包含n个两两不同数的数组。若在i<j的情况下，有A\[i\]>A\[j\]，则(i,j)称为A中的一个逆序对

偏执的太偏执、/ 2022年05月11日 14:33/ 0 赞/ 225 阅读

相关排序---逆序对

题目：[https://www.acwing.com/problem/content/description/109/][https_www.acwing.com_proble

喜欢ヅ旅行/ 2022年02月23日 09:34/ 0 赞/ 230 阅读

相关逆序对个数

题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的

蔚落/ 2022年01月30日 08:21/ 0 赞/ 246 阅读

相关 P1908-逆序对

1 include <bits/stdc++.h> 2 using namespace std; 3 define _for(i,a,b) for(

喜欢ヅ旅行/ 2021年11月09日 07:40/ 0 赞/ 332 阅读