fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define sz 200100
  5.  
  6. vector<ll>tr[4 * sz];
  7. ll ar[sz];
  8.  
  9. void build(ll s, ll e, ll idx)
  10. {
  11. if (s == e)
  12. {
  13. tr[idx].push_back(ar[s]);
  14. return;
  15. }
  16. ll m = (s + e) / 2;
  17. build(s, m, 2 * idx);
  18. build(m + 1, e, 2 * idx + 1);
  19. merge(tr[2 * idx].begin(), tr[2 * idx].end(),
  20. tr[2 * idx + 1].begin(), tr[2 * idx + 1].end(),
  21. back_inserter(tr[idx]));
  22. }
  23.  
  24. ll quelo(ll s, ll e, ll idx, ll qs, ll qe, ll v)
  25. {
  26. if (qs > e || qe < s || qs > qe)
  27. return 0;
  28. if (qs <= s && qe >= e)
  29. return lower_bound(tr[idx].begin(), tr[idx].end(), v) - tr[idx].begin();
  30. ll m = (s + e) / 2;
  31. ll a = quelo(s, m, 2 * idx, qs, qe, v);
  32. ll b = quelo(m + 1, e, 2 * idx + 1, qs, qe, v);
  33. return a + b;
  34. }
  35.  
  36. ll quehi(ll s, ll e, ll idx, ll qs, ll qe, ll v)
  37. {
  38. if (qs > e || qe < s || qs > qe)
  39. return 0;
  40. if (qs <= s && qe >= e)
  41. return e - s + 1 - (upper_bound(tr[idx].begin(), tr[idx].end(), v) - tr[idx].begin());
  42. ll m = (s + e) / 2;
  43. ll a = quehi(s, m, 2 * idx, qs, qe, v);
  44. ll b = quehi(m + 1, e, 2 * idx + 1, qs, qe, v);
  45. return a + b;
  46. }
  47.  
  48. int main()
  49. {
  50. ios::sync_with_stdio(0);
  51. cin.tie(0); cout.tie(0);
  52. ll n, m; cin >> n >> m;
  53. for (ll i = 0; i < n; i++)
  54. cin >> ar[i];
  55. build(0, n - 1, 1);
  56. ll ansF = 0;
  57. for (ll i = 0; i < n; i++)
  58. ansF += quehi(0, n - 1, 1, 0, i, ar[i]);
  59. while (m--)
  60. {
  61. ll ans = ansF;
  62. ll L, R; cin >> L >> R; L--; R--;
  63. ll a = quelo(0, n - 1, 1, L + 1, R - 1, ar[L]); ans -= a;
  64. ll b = quehi(0, n - 1, 1, L + 1, R - 1, ar[L]); ans += b;
  65. ll c = quehi(0, n - 1, 1, L + 1, R - 1, ar[R]); ans -= c;
  66. ll d = quelo(0, n - 1, 1, L + 1, R - 1, ar[R]); ans += d;
  67. if (ar[L] < ar[R])
  68. ans++;
  69. else if (ar[L] > ar[R])
  70. ans--;
  71. cout << ans << endl;
  72. }
  73. return 0;
  74. }
Success #stdin #stdout 0.01s 22328KB
stdin
6 3
1 4 3 3 2 5
1 1
1 3
2 5
stdout
5
6
0