fork download
copy 
  1. #include <bits/stdc++.h>`
  2.  
  3. #define slld(longvalue) scanf("%lld", &longvalue)
  4. #define plld(longvalue) printf("%lld\n", longvalue)
  5.  
  6. #define slf(longvalue) scanf("%lf", &longvalue)
  7. #define plf(longvalue) printf("%lf\n", longvalue)
  8. #define sc(letter) scanf("%c", &letter)
  9. #define pc(letter) printf("%c", letter)
  10.  
  11. #define ss(name) scanf("%s", name)
  12. #define ps(name) printf("%s", name)
  13.  
  14. #define pnew printf("\n")
  15.  
  16. #define ll long long
  17.  
  18. #define printcase(indexing,ans) printf("Case %lld: %lld\n", indexing, ans)
  19.  
  20. #define pb(x) push_back(x)
  21.  
  22. #define bug printf("BUG\n")
  23.  
  24. #define mxlld LLONG_MAX
  25. #define mnlld -LLONG_MAX
  26.  
  27. #define mxd 2e8
  28. #define mnd -2e8
  29.  
  30. #define pi 3.14159265359
  31.  
  32. #define mod 1000000009
  33.  
  34. #define lim 100005
  35. using namespace std;
  36.  
  37. ll arr[lim * 2];
  38. vector < ll > tree[4 * 2 * lim];
  39.  
  40. void merge_sort(ll node, ll a, ll b) {
  41. 	if (a == b) {
  42. 		tree[node].pb(arr[a]);
  43. 		return;
  44. 	}
  45. 	ll mid = (a + b) / 2 , left, right;
  46. 	left = node * 2 ; right = left + 1;
  47. 	merge_sort( left, a, mid);
  48. 	merge_sort( right, mid + 1, b);
  49.  
  50. 	merge( tree[left].begin() , tree[left].end() , tree[right].begin(), tree[right].end(), back_inserter(tree[node]));
  51. }
  52. ll low( ll valu, ll node ) {
  53. 	//cout<<valu<<' '<<node<<endl;
  54. 	ll l = 0 , r = tree[node].size() - 1 , mid;
  55. 	ll pos = 0;
  56.  
  57.     while ( l <= r )
  58.     {
  59. 		mid = (l + r) / 2;
  60.  
  61. 		if ( tree[node][mid] >= valu )
  62.         {
  63. 			r = mid - 1;
  64. 		}
  65. 		else
  66. 		{
  67.             pos = mid + 1;
  68. 			l = mid + 1;
  69. 		}
  70. 	}
  71.  
  72.  
  73. 	return pos;
  74. }
  75.  
  76. ll up( ll valu, ll node ) {
  77. 	//cout<<valu<<' '<<node<<endl;
  78. 	ll l = 0 , r = tree[node].size() - 1 , mid;
  79. 	ll pos = -1;
  80.  
  81. 	while ( l <= r )
  82.     {
  83. 		mid = (l + r) / 2;
  84.  
  85. 		if ( tree[node][mid] <= valu )
  86. 		{
  87. 			l = mid + 1;
  88. 		}
  89. 		else
  90. 		{
  91. 		    pos = mid + 1;
  92. 			r = mid - 1;
  93. 		}
  94. 	}
  95.  
  96. 	if(pos == -1) return 0;
  97.  
  98.  
  99. 	return tree[node].size() - pos + 1;
  100. }
  101.  
  102. ll query1(ll node, ll a, ll b, ll i, ll j, ll val) {
  103. 	if ( a > j || b < i ) return 0;
  104. 	if ( i <= a && b <= j ) {
  105.  
  106. 		ll ret = 0;
  107. 		if ( tree[node].size() )
  108. 			ret = low( val, node );
  109. 		//scout<<"ret "<<ret<<endl;
  110. 		return ret;
  111.  
  112. 	}
  113. 	ll r1 , r2;
  114. 	ll left, right, mid;
  115. 	left = node * 2 ;  right = left + 1;
  116. 	mid = (a + b) / 2;
  117. 	r1 = query1( left , a, mid, i , j , val );
  118. 	r2 = query1( right , mid + 1 , b, i, j, val);
  119. 	return r1 + r2;
  120.  
  121. }
  122.  
  123. ll query2(ll node, ll a, ll b, ll i, ll j, ll val) {
  124. 	if ( a > j || b < i ) return 0;
  125. 	if ( i <= a && b <= j ) {
  126.  
  127. 		ll ret = 0;
  128. 		if ( tree[node].size() )
  129. 			ret = up( val, node );
  130. 		//scout<<"ret "<<ret<<endl;
  131. 		return ret;
  132.  
  133. 	}
  134. 	ll r1 , r2;
  135. 	ll left, right, mid;
  136. 	left = node * 2 ;  right = left + 1;
  137. 	mid = (a + b) / 2;
  138. 	r1 = query2( left , a, mid, i , j , val );
  139. 	r2 = query2( right , mid + 1 , b, i, j, val);
  140. 	return r1 + r2;
  141.  
  142. }
  143.  
  144. struct node
  145. {
  146.     ll l, r, id, blc;
  147. };
  148.  
  149. node q[lim];
  150. ll ans[lim];
  151.  
  152. bool comp(node a, node b)
  153. {
  154.     if(a.blc != b.blc)
  155.     {
  156.         return a.blc < b.blc;
  157.     }
  158.  
  159.     if(a.blc % 2 == 0)
  160.     {
  161.         return a.r < b.r;
  162.     }
  163.     else
  164.     {
  165.         return a.r > b.r;
  166.     }
  167. }
  168.  
  169. ll cnt;
  170.  
  171.  
  172. int main()
  173. {
  174.     ll i, j, k, l, m, n, o;
  175.     ll testcase;
  176.     ll input, flag, tag;
  177.  
  178.     //freopen("in.txt", "r", stdin);
  179.  
  180.     slld(n);
  181.     slld(m);
  182.  
  183.     for(i = 1; i <= n; i++) slld(arr[i]);
  184.  
  185.     merge_sort(1,1,n);
  186.  
  187.     ll r;
  188.     ll ssq = sqrt(n) + 1;
  189.     for(i = 1; i <= m; i++)
  190.     {
  191.         slld(l);
  192.         slld(r);
  193.  
  194.         q[i].l = l;
  195.         q[i].r = r;
  196.         q[i].id = i;
  197.         q[i].blc = l / ssq;
  198.     }
  199.  
  200.     sort(q + 1,q + 1 + m,comp);
  201.  
  202.     l = 1;
  203.     r = 0;
  204.  
  205.     cnt = 0;
  206.  
  207.     for(i = 1; i <= m; i++)
  208.     {
  209.         //cout << q[i].l << " : " << q[i].r << endl;
  210.  
  211.         while(l < q[i].l)
  212.         {
  213.             //bug;
  214.             flag = query1(1,1,n,l + 1, r, arr[l]);
  215.  
  216.             cnt -= flag;
  217.  
  218.             l++;
  219.  
  220.             //cout << flag << " " << l <<
  221.         }
  222.  
  223.         while(l > q[i].l)
  224.         {
  225.             //bug;
  226.             flag = query1(1,1,n,l, r, arr[l - 1]);
  227.  
  228.             cnt += flag;
  229.  
  230.             l--;
  231.         }
  232.  
  233.         while(r < q[i].r)
  234.         {
  235.             flag = query2(1,1,n,l,r,arr[++r]);
  236.  
  237.             cnt += flag;
  238.  
  239.             //cout << flag << " : " << cnt << " : " << r << endl;
  240.         }
  241.  
  242.         while(r > q[i].r)
  243.         {
  244.             flag = query2(1,1,n,l,r - 1,arr[r]);
  245.  
  246.             cnt -= flag;
  247.  
  248.             r--;
  249.         }
  250.  
  251.         ans[q[i].id] = cnt;
  252.     }
  253.  
  254.     for(i = 1; i <= m; i++)
  255.     {
  256.         plld(ans[i]);
  257.     }
  258.  
  259.  
  260.  
  261.  
  262. }
  263.  
  264.  
  265.  
Success #stdin #stdout 0.01s 21988KB
comments (?)
stdin
copy 
5 3
1 4 2 3 1
1 2
3 5
1 5
stdout
copy 
0
2
5
https://ideone.com/wPb0AC
language:
C++14 (gcc 8.3)
created:
6 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!