fork download
copy 
  1. // This is AC solution
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define ff first
  6. #define ss second
  7.  
  8. vector<pair<ll,ll> > tree(400001);
  9. void build_tree(ll int *a, ll int s,ll int e, ll int index)
  10. {
  11. 	if(s==e)
  12. 	{
  13. 		tree[index] = {a[s],1};
  14. 		return;
  15. 	}
  16. 	ll int mid = (s+e)/2;
  17. 	build_tree(a,s,mid,2*index);
  18. 	build_tree(a,mid+1,e,2*index+1);
  19.  
  20. 	if(tree[2*index].ff < tree[2*index + 1].ff)
  21. 	tree[index] = {tree[2*index].ff, tree[2*index].ss};
  22. 	else if(tree[2*index].ff > tree[2*index + 1].ff)
  23. 	tree[index] = {tree[2*index+1].ff, tree[2*index+1].ss};
  24. 	else
  25. 	tree[index] = {tree[2*index].ff , tree[2*index].ss + tree[2*index+1].ss };
  26. 	return;
  27. }
  28. ll query(ll int ss,ll int se,ll int qs,ll int qe ,ll int index)
  29. {
  30. 	//complete overlap
  31. 	if(ss>=qs and se<=qe)
  32. 	{
  33. 		return tree[index].ff;
  34. 	}
  35. 	//No Overlap
  36. 	if(qe<ss || qs>se)
  37. 	return INT_MAX;
  38.  
  39. 	//partial overlap
  40. 	ll int mid = (ss + se)/2;
  41. 	ll l1 = query(ss,mid,qs,qe,2*index);
  42. 	ll l2 = query(mid+1,se,qs,qe,2*index+1);
  43. 	return min(l1,l2);
  44.  
  45. }
  46. //point update
  47. void point_update(ll int ss,ll int se, ll int i,ll int inc,ll int index)
  48. {
  49. 	if(i>se || i<ss)
  50. 	return;
  51. 	if(ss == se)
  52. 	{
  53. 		tree[index] = {inc,1};
  54. 		return;
  55. 	}
  56. 	ll int mid = (ss + se)/2;
  57. 	point_update(ss,mid,i,inc,2*index);
  58. 	point_update(mid+1,se,i,inc,2*index+1);
  59.  
  60. 	if(tree[2*index].ff < tree[2*index + 1].ff)
  61. 	tree[index] = {tree[2*index].ff, tree[2*index].ss};
  62. 	else if(tree[2*index].ff > tree[2*index + 1].ff)
  63. 	tree[index] = {tree[2*index+1].ff, tree[2*index+1].ss};
  64. 	else
  65. 	tree[index] = {tree[2*index].ff , tree[2*index].ss + tree[2*index+1].ss };
  66. 	return;
  67. }
  68. ll count_mini(ll int ss,ll int se,ll int qs,ll int qe ,ll num,ll int index)
  69. {
  70. 	if(ss>qe || se<qs)
  71. 	return 0;
  72. 	if((se<=qe || ss>=qs)&&tree[index].ff>num)
  73. 	return 0;
  74. 	if(ss>=qs && se<=qe)
  75. 	{
  76. 		if(tree[index].ff == num)
  77. 		return tree[index].ss;
  78. 		else
  79. 		return 0;
  80.     }
  81.     ll int mid = (ss + se)/2;
  82. 	ll left =  count_mini(ss,mid,qs,qe,num,2*index);
  83. 	ll right = count_mini(mid+1,se,qs,qe,num,2*index+1);
  84. 	return left+right;
  85. }
  86.  
  87. void solve()
  88. {
  89. 	int n,q;
  90. 	cin>>n>>q;
  91.  
  92. 	ll a[n];
  93. 	for(int i=0;i<n;i++)
  94. 	cin>>a[i];
  95.  
  96. 	build_tree(a,0,n-1,1);
  97.  
  98. 	// for(int i=1;i<=4*n;i++)
  99. 	// cout<<tree[i]<<endl;
  100. 	while(q--)
  101. 	{
  102. 		ll num,l,r;
  103. 		cin>>num>>l>>r;
  104. 		if(num==1)
  105. 		point_update(0,n-1,l,r,1);
  106.  
  107. 		else
  108. 		{
  109. 			ll int num1 = query(0,n-1,l,r-1,1);
  110. 			ll int num2 = count_mini(0,n-1,l,r-1,num1,1);
  111. 			cout<<num1<<" "<<num2<<endl;
  112. 		}
  113.  
  114. 	}
  115.  
  116. }
  117. int main()
  118. {
  119. 	ios_base::sync_with_stdio(false); 
  120.     	cin.tie(NULL); 
  121.  
  122. 	    ll int t=1;
  123. 		 // cin>>t;
  124. 		while(t--)
  125. 		{  
  126. 	      solve();
  127. 	    }
  128.  
  129. 		return 0;
  130. }
  131.  
Runtime error #stdin #stdout 0.69s 2096052KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6758Co
language:
C++14 (clang 8.0)
created:
3 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!