• Greetings

    Problem - 1915F - Codeforces

    题意

    给一些(l,r)找到所有能够包含(l,r)的数目

    引入

    也就是找逆序对个数

    要用到归并排序中的思想：

    1. //https://www.luogu.com.cn/problem/P1216
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #define int long long
    14. #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    15. #define  long long
    16. #define PI acos(-1.0)
    17. using namespace std;
    18. typedef long long ll;
    19. typedef pair<int, int> PII;
    20. const int INF = 1e18 + 10;
    21. const int N = 2e5 + 10;
    22. const int M = 1e7 + 10;
    23. const int mod = 1e9 + 7;
    24. int n, m, k, ans;
    25. int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
    26. int a[N];
    27. bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
    28. int b[N];
    29. void merge(int l,int r)
    30. {
    31.     // 拆分
    32.     if(l == r) return;
    33.     int mid = l + r >> 1;
    34.     merge(l,mid);
    35.     merge(mid+1,r);
    36.     // 合并
    37.     int i = l,j = mid + 1,k = l;
    38.     while(i <= mid && j <= r)
    39.     {
    40.         if(a[i] <= a[j]) b[k ++] = a[i ++];
    41.         else b[k ++] = a[j ++];
    42.     }
    43.     while(i <= mid) b[k ++] = a[i ++];
    44.     while(j <= r) b[k ++] = a[j ++];
    45.     for(i = l;i <= r;i ++) a[i] = b[i];
    46. }
    47.  
    48. void gzy()
    49. {
    50.     cin >> n;
    51.     for(int i = 1;i <= n;i ++) cin >> a[i];
    52.     merge(1,n);
    53.     for(int i = 1;i <= n;i ++) cout << a[i] << ' ';
    54.     puts("");
    55. }
    56. signed main()
    57. {
    58.     IOS;
    59.     int _ = 1; 
    60.     while (_--) gzy();
    61.     return 0;
    62. }

    思路

    只需要加一个 sum += mid - i + 1;

    code

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #define int long long
    13. #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    14. #define  long long
    15. #define PI acos(-1.0)
    16. using namespace std;
    17. typedef long long ll;
    18. typedef pair<int, int> PII;
    19. const int INF = 1e18 + 10;
    20. const int N = 5e5 + 10;
    21. const int M = 1e7 + 10;
    22. const int mod = 1e9 + 7;
    23. int n, m, k, ans;
    24. int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
    25. int a[N];
    26. bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
    27. int b[N];
    28. int sum = 0;
    29. void merge(int l,int r)
    30. {
    31.     // 拆分
    32.     if(l == r) return;
    33.     int mid = l + r >> 1;
    34.     merge(l,mid);
    35.     merge(mid+1,r);
    36.     // 合并
    37.     int i = l,j = mid + 1,k = l;
    38.     while(i <= mid && j <= r)
    39.     {
    40.         if(a[i] <= a[j])
    41.         {
    42.             b[k ++] = a[i ++];
    43.             
    44.         }
    45.         else 
    46.         {
    47.             sum += mid - i + 1;
    48.             b[k ++] = a[j ++];
    49.         }
    50.     }
    51.     while(i <= mid) b[k ++] = a[i ++];
    52.     while(j <= r) b[k ++] = a[j ++];
    53.     for(i = l;i <= r;i ++) a[i] = b[i];
    54. }
    55.  
    56. void gzy()
    57. {
    58.     cin >> n;
    59.     for(int i = 1;i <= n;i ++) cin >> a[i];
    60.     merge(1,n);
    61.     // for(int i = 1;i <= n;i ++) cout << a[i] << ' ';
    62.     // puts("");
    63.     cout << sum << endl;
    64. }
    65. signed main()
    66. {
    67.     IOS;
    68.     int _ = 1; 
    69.     while (_--) gzy();
    70.     return 0;
    71. }

    思路

    就是对first排序之后 找到second中的逆序对个数

    code

    1. //https://www.luogu.com.cn/problem/P1216
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include  
    12. #include
    13. #define int long long
    14. #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    15. #define  long long
    16. #define PI acos(-1.0)
    17. using namespace std;
    18. typedef long long ll;
    19. typedef pair<int, int> PII;
    20. const int INF = 1e18 + 10;
    21. const int N = 5e5 + 10;
    22. const int M = 1e7 + 10;
    23. const int mod = 1e9 + 7;
    24. int n, m, k, ans;
    25. int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
    26. PII d[N];
    27. bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
    28. int a[N],b[N];
    29. int sum = 0;
    30. void merge(int l,int r)
    31. {
    32.     // 拆分
    33.     if(l == r) return;
    34.     int mid = l + r >> 1;
    35.     merge(l,mid);
    36.     merge(mid+1,r);
    37.     // 合并
    38.     int i = l,j = mid + 1,k = l;
    39.     while(i <= mid && j <= r)
    40.     {
    41.         if(a[i] <= a[j])
    42.         {
    43.             b[k ++] = a[i ++];   
    44.         }
    45.         else 
    46.         {
    47.             sum += mid - i + 1;
    48.             b[k ++] = a[j ++];
    49.         }
    50.     }
    51.     while(i <= mid) b[k ++] = a[i ++];
    52.     while(j <= r) b[k ++] = a[j ++];
    53.     for(i = l;i <= r;i ++) a[i] = b[i];
    54. }
    55.  
    56. void gzy()
    57. {
    58.     sum = 0;
    59.     cin >> n;
    60.     for(int i = 1;i <= n;i ++) cin >> d[i].first >> d[i].second;
    61.     sort(d+1,d+1+n);
    62.     for(int i = 1;i <= n;i ++) a[i] = d[i].second;
    63.     merge(1,n);
    64.     cout << sum << endl;
    65. }
    66. signed main()
    67. {
    68.     IOS;
    69.     int _ = 1; cin >> _;
    70.     while (_--) gzy();
    71.     return 0;
    72. }

  • 相关阅读:
    Ubuntu Kafka开机自启动服务
    华为、小米OV折叠屏市场再厮杀
    2.mysql的安装
    @JSONField注解的使用
    【大二Web课程设计】基于HTML+CSS技术制作抗疫感动专题网页设计
    SpringBoot导出Jar包并测试（使用IDEA）
    一篇文章搞懂残差网络算法
    数字化转型“黑话”知多少？一文让你不仅听得懂、还会落地执行
    {草履虫都能看懂的} 数据结构串的PM、next和nextval数组的求法
    JavaScript学习笔记
  • 原文地址：https://blog.csdn.net/chunyou_/article/details/136722270