fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int len,n;
  4. vector< vector <int> > b(1000);
  5. void sqrt_decompose(int n){
  6. 	for(int i=0;i*len<n;i++){
  7. 		sort(b[i].begin(),b[i].end());
  8. /*		for(int j=0;j<b[i].size();j++){
  9. 			printf("%d ",b[i][j]);
  10. 		}
  11. 		printf("\n");*/
  12. 	}
  13. 	return;
  14. }
  15. int query(int l,int r,int *a,int x){
  16. 	int num=0;
  17. 	int c_l=(l-1)/len,c_r=(r-1)/len;
  18. //	printf("%d %d\n",c_l,c_r);
  19. 	if(c_l==c_r){
  20. 		for(int i=l-1;i<r;i++){
  21. 			if(a[i]<=x){
  22. 				num++;
  23. 			}
  24. 		}
  25. 	}
  26. 	else{
  27. 		for (int i=l-1, end=(c_l+1)*len; i<end; ++i){
  28. 			if(x>=a[i]){
  29. 				num++;
  30. 			}
  31. 		}
  32. 		for (int i=c_l+1; i<c_r; i++){
  33. 			num+=upper_bound(b[i].begin(),b[i].end(),x)-(b[i].begin());
  34. 		/*	for(int j=0;j<b[i].size();j++){
  35. 				printf("%d ",b[i][j]);
  36. 			}*/
  37. 			//printf("\n%d %d\n",(len)*i+1,upper_bound(b[i].begin(),b[i].end(),x)-(b[i].begin()));
  38. 		}
  39. 		for (int i=(c_r*len); i<r; ++i)
  40. 			if(x>=a[i]){
  41. 				num++;
  42. 			}
  43. 	}
  44. 	return num;
  45. }
  46. void update(int i,int m,int *a){
  47. 	int temp=i/len,ini,ter;
  48. 	a[i-1]=m;
  49. //	printf("%d %d %d\n",temp,len,a[i-1]);
  50. 	for(int j=0;j<len&&(len*temp+j)<n;j++){
  51. 		b[temp][j]=a[len*temp+j];
  52. 	//	printf("%d ",b[temp][j]);
  53. 	}
  54. //	printf("\n");
  55. 	sort(b[temp].begin(),b[temp].end());
  56. 	return;
  57. }
  58. int main(){
  59. 	int q;
  60. 	scanf("%d%d",&n,&q);
  61. 	int a[n+1];
  62. 	double d=sqrt(double(n));
  63. 	len=(int)d;
  64. 	if((double)len!=d){
  65. 		len++;
  66. 	}
  67. //	printf("%d\n",len);
  68. 	for(int i=0;i<n;i++){
  69. 		scanf("%d",&a[i]);
  70. 	}
  71. 	for(int i=0,j=0,k=0;i<n;i++,j++){
  72. 		if(j==len){
  73. 			j=0;
  74. 			k++;
  75. 		}
  76. 		b[k].push_back(a[i]);
  77. 	//	printf("%d ",b[k][j]);
  78. 	}
  79. 	sqrt_decompose(n);
  80.  
  81. 	while(q--){
  82. 		char c[5];
  83. 		scanf("%s",c);
  84. 		if(c[0]=='M'){
  85. 			int k,l;
  86. 			scanf("%d%d",&k,&l);
  87. 			update(k,l,a);
  88. 		}
  89. 		else{
  90. 			int l,r,x,count;
  91. 			scanf("%d%d%d",&l,&r,&x);
  92. 			count=query(l,r,a,x);
  93. 			printf("%d\n",count);
  94. 		}
  95. 	}
  96. 	return 0;
  97. }
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
24 2
1 2 3 2 3 4 6 7 8 9 2 3 4 5 6 7 8 9 4 5 6 7 8 9
M 2 3
C 1 5 2
stdout
copy 
2
https://ideone.com/FtH8Fs
language:
C++ (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!