fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node
  5. {
  6. 	int d;
  7. 	map<int,int>m;
  8. 	int c;
  9. };
  10.  
  11. node tree[1000000];
  12. int a[100007];
  13. int n;
  14. vector<int>pos;
  15.  
  16. void merge(int si)
  17. {
  18. 	for(auto j:tree[2*si+1].m)
  19. 		tree[si].m[j.first]+=j.second;
  20. 	for(auto j:tree[2*si+2].m)
  21. 		tree[si].m[j.first]+=j.second;
  22. }
  23.  
  24. void maketree(int beg,int last,int si)
  25. {
  26. 	if(beg==last)
  27. 	{
  28. 		tree[si].m[a[beg]]++;
  29. 		tree[si].d=a[beg];
  30. 		tree[si].c=1;
  31. 		return;
  32. 	}
  33. 	maketree(beg,(beg+last)/2,2*si+1);
  34. 	maketree((beg+last)/2+1,last,2*si+2);
  35. 	merge(si);
  36. 	tree[si].c=tree[2*si+1].c+tree[2*si+2].c;
  37. 	int len=tree[si].c;
  38. 	if(2*tree[si].m[tree[2*si+1].d]>len)
  39. 		tree[si].d=tree[2*si+1].d;
  40. 	else if(2*tree[si].m[tree[2*si+2].d]>len)
  41. 		tree[si].d=tree[2*si+2].d;
  42. 	else
  43. 		tree[si].d=-1;
  44. }
  45.  
  46. bool update(int beg,int last,int p,int q,int si,int v)
  47. {
  48. 	if(beg>q||last<p)
  49. 		return false;
  50. 	if(beg==last)
  51. 	{
  52. 		tree[si].m[a[p]]--;
  53. 		tree[si].d=v;
  54. 		tree[si].m[v]++;
  55. 		return true;
  56. 	}
  57. 	bool flag1=update(beg,(beg+last)/2,p,q,2*si+1,v);
  58. 	bool flag2=update((beg+last)/2+1,last,p,q,2*si+2,v);
  59. 	if(flag1||flag2)
  60. 	{
  61. 		tree[si].m[a[p]]--;
  62. 		tree[si].m[v]++;
  63. 		//int len=last-beg+1;
  64. 		int len=tree[si].c;
  65. 		if(2*tree[si].m[v]>len)
  66. 			tree[si].d=v;
  67. 		else if(2*tree[si].m[a[p]]>len)
  68. 			tree[si].d=a[p];
  69. 		else
  70. 			tree[si].d=-1;
  71. 	}
  72. 	return (flag1|flag2);
  73. }
  74.  
  75. void query(int beg,int last,int p,int q,int si)
  76. {
  77. 	if(beg>q||last<p)
  78. 		return;
  79. 	if(p<=beg&&q>=last)
  80. 	{
  81. 		pos.push_back(si);
  82. 		return;
  83. 	}
  84. 	query(beg,(beg+last)/2,p,q,2*si+1);
  85. 	query((beg+last)/2+1,last,p,q,2*si+2);
  86. }
  87.  
  88. void func(int t,int x,int y)
  89. {
  90. 	if(t==1)
  91. 	{
  92. 		update(0,n-1,x-1,x-1,0,y);
  93. 		a[x-1]=y;
  94. 	}
  95. 	else
  96. 	{
  97. 		x--;y--;
  98. 		pos.clear();
  99. 		query(0,n-1,x,y,0);
  100. 		bool flag=false;
  101. 		for(auto j:pos)
  102. 		{
  103. 			if(tree[j].d==-1)
  104. 				continue;
  105. 			int temp=0,len=y-x+1;
  106. 			for(auto k:pos)
  107. 				temp+=tree[k].m[tree[j].d];
  108. 			if(2*temp>len)
  109. 			{
  110. 				flag=true;
  111. 				break;
  112. 			}
  113. 		}
  114. 		if(flag)
  115. 			printf("Yes\n");
  116. 		else
  117. 			printf("No\n");
  118. 	}
  119. }
  120.  
  121. int main()
  122. {
  123. 	//freopen("in.txt","r",stdin);
  124. 	int q;
  125. 	scanf("%d%d",&n,&q);
  126. 	for(int i=0;i<n;i++)
  127. 		scanf("%d",&a[i]);
  128. 	maketree(0,n-1,0);
  129. 	//merge(0);
  130. 	while(q--)
  131. 	{
  132. 		int t,x,y;
  133. 		scanf("%d%d%d",&t,&x,&y);
  134. 		func(t,x,y);
  135. 	}
  136. 	return 0;
  137. }
  138.  
Runtime error #stdin #stdout 0.02s 43168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tJUlHd
language:
C++14 (gcc 8.3)
created:
7 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!