fork download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3. #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
  4. #define rf freopen("in.in", "r", stdin)
  5. #define wf freopen("out.out", "w", stdout)
  6. using namespace std;
  7. const int mx=2.5e5+10, mxa=5e4+5, mxsqr=505;
  8.  
  9. static long long bit[mxsqr][mxa], totinv=0;
  10. int n, m, idx, val, a[mx], sqr;
  11.  
  12. inline void up(int x, int y, int v)
  13. {
  14. 	for(int i=x; i<mxsqr; i+=i&-i)
  15. 		for(int j=y; j<mxa; j+=j&-j)
  16. 			bit[i][j]+=v;
  17. }
  18. inline long long qu(int x, int y)
  19. {
  20. 	long long ret = 0;
  21. 	for(int i=x; i; i-=i&-i)
  22. 		for(int j=y; j; j-=j&-j)
  23. 			ret+=bit[i][j];
  24. 	return ret;
  25. }
  26.  
  27. inline long long qtype1(int buck, int idx)
  28. {
  29. 	long long ret=0;
  30. 	int e= buck*sqr-1 < n? buck*sqr-1 : n;
  31.  
  32. 	rep(i, idx+1, e)
  33. 		if(a[i] < a[idx]) ret++;
  34.  
  35. 	ret += qu(mxsqr-1, a[idx]-1) - qu(buck, a[idx]-1);
  36.  
  37. 	return ret;
  38. }
  39. inline long long qtype2(int buck, int idx)
  40. {
  41. 	long long ret=0;
  42. 	int s = sqr*(buck-1);
  43.  
  44. 	rep(i, s, idx-1)
  45. 		if(a[i] > a[idx]) ret++;
  46.  
  47. 	ret += qu(buck-1, mxa-1) - qu(buck-1, a[idx]);
  48.  
  49. 	return ret;
  50. }
  51.  
  52. int main()
  53. {
  54. 	//rf; wf;
  55. 	rep(i, 0, mx-1) a[i]=mx;
  56.  
  57. 	scanf("%d", &n); sqr=sqrt(n);
  58. 	rep(i, 0, n-1)
  59. 	{
  60. 		scanf("%d", &a[i]);
  61. 		up(i/sqr+1, a[i], 1);
  62. 		totinv += qtype1(i/sqr+1, i)+qtype2(i/sqr+1, i);
  63. 	}
  64.  
  65. 	scanf("%d", &m);
  66. 	while(m--)
  67. 	{
  68. 		scanf("%d %d", &idx, &val); idx--;
  69. 		int buck=idx/sqr+1;
  70.  
  71. 		totinv -= qtype1(buck, idx)+qtype2(buck, idx);
  72. 		up(buck, a[idx], -1);
  73.  
  74. 		a[idx]=val; up(buck, a[idx], 1);
  75. 		totinv += qtype1(buck, idx)+qtype2(buck, idx);
  76.  
  77. 		printf("%lld\n", totinv);
  78. 	}
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 201536KB
comments (?)
stdin
copy 
10
2 6 6 4 7 6 3 5 9 1 
7
8 8
5 1
5 6
10 5
7 1
10 10
4 6
stdout
copy 
Standard output is empty
https://ideone.com/u3C63e
language:
C++14 (gcc 8.3)
created:
9 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!