fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 1e5 + 5;
  5. const int S = 320;
  6. //
  7. struct query
  8. {
  9.     int l, r, id;
  10.     //
  11.     bool operator < (const query &other)
  12.     {
  13.         if (l / S != other.l / S)
  14.             return l < other.l;
  15.         return l / S & 1 ? r < other.r : r > other.r;
  16.     }
  17. };
  18. struct Fenwick_Tree
  19. {
  20.     int bit[mx];
  21.     //
  22.     void update (int idx, int val)
  23.     {
  24.         if (idx == 0)
  25.             return;
  26.         for (; idx < mx; idx += idx & -idx)
  27.             bit[idx] += val;
  28.     }
  29.     int sum (int idx)
  30.     {
  31.         int res = 0;
  32.         //
  33.         for (; idx > 0; idx -= idx & -idx)
  34.             res += bit[idx];
  35.         return res;
  36.     }
  37.     int get (int l, int r)
  38.     {
  39.         return sum(r) - sum(l - 1);
  40.     }
  41. };
  42. //
  43. int n, q, P[mx];
  44. long long ans[mx];
  45. query Q[mx];
  46. Fenwick_Tree FT;
  47. //
  48. void calc (void)
  49. {
  50.     int l = 0, r = 0;
  51. 	long long res = 0;
  52.     //
  53.     for (int i = 1; i <= q; ++i)
  54.     {
  55.         while (l < Q[i].l)
  56.         {
  57.             FT.update(P[l], -1);
  58.             res -= FT.get(1, P[l]);
  59.             ++l;
  60.         }
  61.         while (l > Q[i].l)
  62.         {
  63.             --l;
  64.             res += FT.get(1, P[l]);
  65.             FT.update(P[l], 1);
  66.         }
  67.         while (r < Q[i].r)
  68.         {
  69.             ++r;
  70.             res += FT.get(P[r], n);
  71.             FT.update(P[r], 1);
  72.         }
  73.         while (r > Q[i].r)
  74.         {
  75.             FT.update(P[r], -1);
  76.             res -= FT.get(P[r], n);
  77.             --r;
  78.         }
  79.         ans[Q[i].id] = res;
  80.     }
  81. }
  82. //
  83. void process (void)
  84. {
  85.     cin >> n >> q;
  86.     for (int i = 1; i <= n; ++i)
  87.         cin >> P[i];
  88.     for (int i = 1; i <= q; ++i)
  89.         cin >> Q[i].l >> Q[i].r,
  90.         Q[i].id = i;
  91.  
  92.     sort(Q + 1, Q + q + 1);
  93.     calc();
  94.  
  95.     for (int i = 1; i <= q; ++i)
  96.         cout << ans[i] << '\n';
  97. }
  98. //
  99. signed main (void)
  100. {
  101.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  102.     process();
  103. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ji1ADj
https://m...content-available-to-author-only...j.com/problem/262
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!