fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. const int M=1e5+4;
  3. using namespace std;
  4. int a[M];
  5. struct node{
  6. 	unordered_map<int,int>co;
  7. 	int d;
  8. }seg[4*M];
  9. node merge(node a,node b,int ln)
  10. {
  11. 	int f=0;
  12. 	node c;
  13. 	if(a.d==-2) return b;
  14. 	if(b.d==-2) return a;
  15. 	unordered_map<int,int>::iterator it=a.co.begin();
  16. 	while(it!=a.co.end())
  17. 	{
  18. 	    c.co[it->first]+=it->second;
  19. 	    it++;
  20. 	}
  21. 	it=b.co.begin();
  22. 	while(it!=b.co.end())
  23. 	{
  24. 		c.co[it->first]+=it->second;
  25. 		it++;
  26. 	}
  27.     if(c.co[a.d]>ln/2) c.d=a.d;
  28.     else if(c.co[b.d]>ln/2) c.d=b.d;
  29.     else c.d=-1;
  30.     return c;
  31. }
  32. void build(int st,int en,int id)
  33. {
  34. 	if(st==en)
  35. 	{
  36. 		seg[id].co.clear();
  37. 		seg[id].co[a[st]]++;
  38. 		seg[id].d=a[st];
  39. 		return;
  40. 	}
  41. 	int m=(st+en)>>1;
  42. 	build(st,m,2*id);
  43. 	build(m+1,en,2*id+1);
  44. 	seg[id]=merge(seg[2*id],seg[2*id+1],en-st+1);
  45. }
  46. void upd(int st,int en,int id,int i,int val)
  47. {
  48. 	if(st==en)
  49. 	{
  50. 	    seg[id].co.clear();
  51. 	    seg[id].co[val]++;
  52. 	    seg[id].d=val;
  53. 	    a[st]=val;
  54. 	    return;	
  55. 	}
  56. 	int m=(st+en)>>1;
  57. 	if(st<=i && i<=m)
  58. 	upd(st,m,2*id,i,val);
  59. 	else
  60. 	upd(m+1,en,2*id+1,i,val);
  61. 	seg[id]=merge(seg[2*id],seg[2*id+1],en-st+1);
  62. }
  63. node qry(int st,int en,int id,int l,int r)
  64. {
  65. 	node tmp;
  66. 	//printf("%d %d\n",st,en);
  67. 	if(en<l|| r<st || l>r)
  68. 	{
  69. 	    tmp.d=-2;
  70. 	    return tmp;
  71. 	}
  72. 	if(l<=st && en<=r) return seg[id];
  73. 	int m=(st+en)>>1;
  74. 	tmp=merge(qry(st,m,2*id,l,r),qry(m+1,en,2*id+1,l,r),en-st+1);
  75. 	return tmp;
  76. }
  77. int main()
  78. {
  79. 	int n,q;
  80. 	scanf("%d%d",&n,&q);
  81. 	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  82. 	build(1,n,1);
  83. 	/*for(int i=1;i<2*n;i++)
  84. 	{
  85. 		printf("%d ",seg[i].d);
  86. 	}*/
  87. 	while(q--)
  88. 	{
  89. 		int ch,x,y;
  90. 		scanf("%d%d%d",&ch,&x,&y);
  91. 		if(ch==1)
  92. 		upd(1,n,1,x,y);
  93. 		else
  94. 		{
  95. 		   int ln=y-x+1,f=0; 
  96. 		   node tmp=qry(1,n,1,x,y);
  97. 		   for(auto x:tmp.co)
  98. 		   {
  99. 		   	if(x.second>ln/2) f=1;
  100. 		   }
  101. 		   if(f)
  102. 		   printf("Yes\n");
  103. 		   else
  104. 		   printf("No\n");
  105. 		}
  106. 	}
  107. 	return 0;
  108. }
Success #stdin #stdout 0.01s 28032KB
comments (?)
stdin
copy 
5 8
1 2 3 2 1
2 1 5
2 2 4
1 3 2
2 1 5
1 2 3
2 1 5
1 3 1
2 1 5
stdout
copy 
No
Yes
Yes
No
Yes
https://ideone.com/ppXmuf
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!