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
comments (?)
stdin 
6 3
1 4 3 3 2 5
1 1
1 3
2 5
stdout 
5
6
0
https://ideone.com/tgs2nU
language:
C++14 (gcc 8.3)
created:
5 years 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!