fork(3) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <list>
  5. #include <queue>
  6. #include <map>
  7. #include <set>
  8. #include <utility>
  9. #include <functional>
  10. #include <string>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <ctime>
  15. #include <cassert>
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef pair<int,int> pii;
  21. typedef map<int,int> mii;
  22. typedef vector<int> vi;
  23. typedef vector< vector<int> > vvi;
  24. typedef vector<char> vc;
  25. typedef vector<bool> vb;
  26. typedef vector<string> vs;
  27.  
  28. #define rep(i,n) for(int i=0;i<(n);i++)
  29. #define forup(i,a,b) for(int i=(a);i<=(b);i++)
  30. #define fordn(i,a,b) for(int i=(a);i>=(b);i--)
  31. #define drep(i,n) for(i=0;i<(n);i++)
  32. #define dforup(i,a,b) for(i=(a);i<=(b);i++)
  33. #define dfordn(i,a,b) for(i=(a);i>=(b);i--)
  34. #define all(x) x.begin(),x.end()
  35. #define permute(x) next_permutation(all(x))
  36. #define pb push_back
  37. #define mp make_pair
  38. #define fi first
  39. #define sc second
  40. #define gi(x) scanf("%d",&x)
  41.  
  42. /************************BIT Codechunk**************************/
  43.  
  44. struct BIT
  45. {
  46. 	int bn; //bn>0
  47. 	vector<int> bA;
  48.  
  49. 	BIT(){ bn=0; }
  50. 	BIT(int bn_){ bn=bn_; bA.resize(bn+1); fill(bA.begin(),bA.end(),0); }
  51.  
  52. 	int prefix(int bposn)
  53. 	{
  54. 		if(bposn<=0) return 0;
  55. 		if(bposn>bn) bposn=bn;
  56.  
  57. 		int ret=0;
  58. 		for(int i=bposn; i>0; i-=((i)&(-i)))
  59. 			ret+=bA[i];
  60. 		return ret;
  61. 	}
  62.  
  63. 	void update(int bposn, int bincr)
  64. 	{
  65. 		if(bposn<=0) return;
  66. 		if(bposn>bn) return;
  67.  
  68. 		for(int i=bposn; i<=bn; i+=((i)&(-i)))
  69. 			bA[i]+=bincr;
  70. 	}
  71.  
  72. 	int query(int bl, int br)
  73. 	{
  74. 		if(br<=0 or bl>bn or bl>br) return 0;
  75. 		if(bl<=0) bl=1;
  76. 		if(br>bn) br=bn;
  77. 		return (prefix(br)-prefix(bl-1));
  78. 	}
  79. };
  80.  
  81. /******************End of BIT Codechunk*************************/
  82.  
  83. struct query_t {
  84. 	int l,r,ix;
  85. 	query_t(int l_,int r_,int ix_) {
  86. 		l=l_; r=r_; ix=ix_;
  87. 	}
  88. };
  89.  
  90. bool operator<(query_t q1,query_t q2) {
  91. 	return (q1.r<q2.r);
  92. }
  93.  
  94. const int max_n=20010;
  95. const int max_q=20010;
  96. int n,q,l,r;
  97. int a[max_n]; int ta[max_n];
  98. mii M; int cnt;
  99. vector<query_t> chunks[150];
  100. int ans[max_q];
  101. BIT bit;
  102.  
  103. int main() {
  104. 	gi(n);
  105. 	assert(n <= 20000);
  106. 	assert(n >= 1);
  107. 	int root=(int)ceil(sqrt(double(n)));
  108. 	rep(i,n) {
  109. 		gi(a[i]);
  110. 		assert(a[i] <= 1000000000);
  111. 		assert(a[i] >= 0);
  112. 		ta[i]=a[i];
  113. 	}
  114. 	gi(q);
  115. 	assert(q <= 20000);
  116. 	assert(q >= 1);
  117. 	rep(i,q) {
  118. 		gi(l); gi(r);
  119. 		assert(l <= r);
  120. 		assert(r <= n);
  121. 		assert(l >= 1);
  122. 		l--; r--;
  123. 		chunks[l/root].pb(query_t(l,r,i));
  124. 	}
  125.  
  126. 	sort(ta,ta+n);
  127. 	cnt=int(unique(ta,ta+n)-ta);
  128. 	rep(i,n)
  129. 		a[i]=1+int(lower_bound(ta,ta+cnt,a[i])-ta);
  130. 	int sz=(n+root-1)/root;
  131. 	n=cnt;
  132. 	rep(i,sz) {
  133. 		int cl=root*i;
  134. 		int cr=cl-1;
  135. 		int res=0;
  136. 		bit=BIT(n);
  137. 		sort(chunks[i].begin(),chunks[i].end());
  138. 		rep(j,chunks[i].size()) {
  139. 			l=chunks[i][j].l; r=chunks[i][j].r; int ix=chunks[i][j].ix;
  140. 			while(cr!=r) {
  141. 				++cr;
  142. 				res+=bit.query(a[cr]+1,n);
  143. 				bit.update(a[cr],1);
  144. 			}
  145. 			if(l>=cl) {
  146. 				while(cl!=l) {
  147. 					res-=bit.prefix(a[cl]-1);
  148. 					bit.update(a[cl],-1);
  149. 					++cl;
  150. 				}
  151. 			}
  152. 			else {
  153. 				while(cl!=l) {
  154. 					--cl;
  155. 					res+=bit.prefix(a[cl]-1);
  156. 					bit.update(a[cl],1);
  157. 				}
  158. 			}
  159. 			ans[ix]=res;
  160. 		}
  161. 	}
  162. 	rep(i,q) printf("%d\n",ans[i]);
  163. 	return 0;
  164. }
Success #stdin #stdout 0s 3064KB
comments (?)
stdin
copy 
7
7 9 3 5 1 6 4
4
1 4
3 5
1 2
1 7
stdout
copy 
4
2
0
14
https://ideone.com/MIhTks
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!