fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define r(i,a,n) for(int (i)=a;i<n;i++)
  4. #define vii vector<int,int>
  5. #define ll long long int
  6. #define it iterator
  7. #define lr(i,a,n) for(long long int (i)=a;i<n;i++)
  8. int arr[100010];
  9. vector< pair<int,int> > stree[500010];
  10. map<int,int> que;
  11. int ma=0;
  12. void merge(int parent,int c1,int c2){
  13. int s1=stree[c1].size();
  14. int s2=stree[c2].size();
  15. int p1=0;
  16. int p2=0;
  17. while(p1<s1&&p2<s2){
  18. if(stree[c1][p1].first==stree[c2][p2].first){
  19. stree[parent].push_back(make_pair(stree[c1][p1].first,stree[c1][p1].second+stree[c2][p2].second));
  20. p1++;
  21. p2++;
  22. }
  23. else if(stree[c1][p1].first<stree[c2][p2].first){
  24. stree[parent].push_back(make_pair(stree[c1][p1].first,stree[c1][p1].second));
  25. p1++;
  26. }
  27. else{
  28. stree[parent].push_back(make_pair(stree[c2][p2].first,stree[c2][p2].second));
  29. p2++;
  30. }
  31. }
  32. while(p1<s1){
  33. stree[parent].push_back(make_pair(stree[c1][p1].first,stree[c1][p1].second));
  34. p1++;
  35. }
  36. while(p2<s2){
  37. stree[parent].push_back(make_pair(stree[c2][p2].first,stree[c2][p2].second));
  38. p2++;
  39. }
  40. return;
  41. }
  42. void buildsegmenttree(int s,int e,int si){
  43. if(s==e){
  44. stree[si].push_back(make_pair(arr[s],1));
  45. return;
  46. }
  47. else{
  48. int mid=(s+e)/2;
  49. buildsegmenttree(s,mid,si*2 + 1);
  50. buildsegmenttree(mid+1,e,si*2 +2);
  51. merge(si,si*2 + 1,si*2 + 2);
  52. return;
  53. }
  54. }
  55. void query(int s,int e,int qs,int qe,int si){
  56. //cout<<s<<e<<endl;
  57. if(s>qe || e<qs){
  58. return;
  59. }
  60. if(s>=qs && e<=qe){
  61. for(int i=0;i<stree[si].size();i++){
  62. map<int,int>::iterator it=que.find(stree[si][i].first);
  63. if(it==que.end()){
  64. que.insert(make_pair(stree[si][i].first,stree[si][i].second));
  65. ma=max(ma,stree[si][i].second);
  66. }
  67. else{
  68. it->second+=(stree[si][i].second);
  69. ma=max(ma,it->second);
  70. }
  71. }
  72. return;
  73. }
  74. int mid;
  75. mid=(s+e)/2;
  76. query(s,mid,qs,qe,si*2 +1);
  77. query(mid+1,e,qs,qe,si*2 +2);
  78. return;
  79. }
  80. int main()
  81. {
  82. int n,q;
  83. cin>>n>>q;
  84. for(int i=0;i<n;i++){
  85. cin>>arr[i];
  86. }
  87. buildsegmenttree(0,n-1,0);
  88. for(int i=0;i<q;i++){
  89. int a,b;
  90. cin>>a>>b;
  91. a--;
  92. b--;
  93. ma=0;
  94. que.clear();
  95. query(0,n-1,a,b,0);
  96. cout<<ma<<endl;
  97. }
  98. return 0;
  99. }
  100.  
Runtime error #stdin #stdout 0s 28176KB
stdin
Standard input is empty
stdout
Standard output is empty