fork download
copy 
  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 z=0;
  83.     while(z==0){			
  84.     int n,q;
  85.     cin>>n>>q;
  86.     if(n==0)
  87.     {
  88.     	z=1;
  89.     	break;
  90.     }
  91.     for(int i=0;i<n;i++){
  92.         cin>>arr[i];
  93.     }
  94.     buildsegmenttree(0,n-1,0);
  95.     for(int i=0;i<q;i++){
  96.         int a,b;
  97.         cin>>a>>b;
  98.         a--;
  99.         b--;
  100.         ma=0;
  101.        que.clear();
  102.        query(0,n-1,a,b,0);
  103.        cout<<ma<<endl;}
  104.     }
  105.     return 0;
  106. }
Success #stdin #stdout 0s 27352KB
comments (?)
stdin
copy 
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
copy 
1
4
3
https://ideone.com/2HnTTN
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!