fork(15) download
copy 
  1. using namespace std;
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <string>
  5. #include <vector>
  6. #include <iostream>
  7. #include <algorithm>
  8. #define all(c) (c).begin(),(c).end()
  9. #define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
  10. typedef long long ll; 
  11. typedef pair<int,int> pii; 
  12. #define FOR(i,n) for (int i = 0; i < n; i++)
  13. #define SZ(x) ((int)x.size())
  14. #define PB push_back
  15. #define sf(x) scanf("%d",&x)
  16. #define pf(x) printf("%d\n",x)
  17. #define split(str) {vs.clear();istringstream ss(str);while(ss>>(str))vs.push_back(str);}
  18. #define MAX_N 100000
  19. #define LOGMAX_N 18
  20. struct node
  21. {
  22.   int lnum;
  23.   int lfreq;
  24.   int rnum;
  25.   int rfreq;
  26.   int mnum;
  27.   int mfreq;
  28. };
  29. int arr[MAX_N];
  30. pair<int,int> left1[2*(1<<LOGMAX_N)+1];
  31. pair<int,int> right1[2*(1<<LOGMAX_N)+1];
  32. pair<int,int> m1[2*(1<<LOGMAX_N)+1];
  33. void init(int ind,int s,int e)
  34. {
  35.   if(s==e)
  36.   {
  37.     pair<int,int> p;
  38.     p.first=arr[s];
  39.     p.second=1;
  40.     left1[ind]=p;
  41.     right1[ind]=p;
  42.     m1[ind]=p;
  43.   }
  44.   else
  45.   {
  46.     init(ind*2,s,(s+e)/2);
  47.     init(ind*2+1,(s+e)/2+1,e);
  48.     if(left1[ind*2].first==left1[ind*2+1].first)
  49.     {
  50.       left1[ind]=make_pair(left1[ind*2].first,left1[ind*2].second+left1[ind*2+1].second);
  51.     }
  52.     else
  53.       left1[ind]=left1[ind*2];
  54.     if(right1[ind*2].first==right1[ind*2+1].first)
  55.       right1[ind]=make_pair(right1[ind*2].first,right1[ind*2].second+right1[ind*2+1].second);
  56.     else
  57.       right1[ind]=right1[ind*2+1];
  58.     pii p= (m1[ind*2].second>m1[ind*2+1].second)?m1[ind*2]:m1[ind*2+1];
  59.     m1[ind]=p;
  60.     if(right1[ind*2].first==left1[ind*2+1].first)
  61.       if(right1[ind*2].second+left1[ind*2+1].second>m1[ind].second)
  62. 	m1[ind]=make_pair(right1[ind*2].first,right1[ind*2].second+left1[ind*2+1].second);
  63.   }
  64.   //cout<<s<<" "<<e<<" "<<m1[ind].second<<endl;
  65. }
  66. node query(int ind,int s,int e,int a,int b)
  67. {
  68.  
  69.   node n;
  70.   n.lnum=-1000000;
  71.   if(e<a||s>b)
  72.     return n;
  73.   if(a<=s&&e<=b)
  74.   {
  75.     n.lnum=left1[ind].first;
  76.     n.lfreq=left1[ind].second;
  77.     n.rnum=right1[ind].first;
  78.     n.rfreq=right1[ind].second;
  79.     n.mnum=m1[ind].first;
  80.     n.mfreq=m1[ind].second;
  81. //    cout<<s<<" "<<e<<" "<<n.mfreq<<endl;
  82.     return n;
  83.   }
  84.   else
  85.   {
  86.     node n1=query(ind*2,s,(s+e)/2,a,b);
  87.     node n2=query(ind*2+1,(s+e)/2+1,e,a,b);
  88.     if(n1.lnum==-1000000)return n2;
  89.     if(n2.lnum==-1000000)return n1;
  90.     if(n1.lnum==n2.lnum)
  91.     {
  92.       n.lnum=n1.lnum;
  93.       n.lfreq=n1.lfreq+n2.lfreq;
  94.       //left1[ind]=make_pair(left1[ind*2].first,left1[ind*2].second+left1[ind*2+1].second);
  95.     }
  96.     else
  97.     {
  98.       n.lnum=n1.lnum;
  99.       n.lfreq=n1.lfreq;
  100.     }
  101.     if(n1.rnum==n2.rnum)
  102.     {
  103.       n.rnum=n1.rnum;
  104.       n.rfreq=n1.rfreq+n2.rfreq;
  105.     }
  106.     else
  107.     {
  108.       n.rnum=n1.rnum;
  109.       n.rfreq=n1.rfreq;
  110.     }
  111.     n.mnum= (n1.mfreq>n2.mfreq)?n1.mnum:n2.mnum;
  112.     n.mfreq= (n1.mfreq>n2.mfreq)?n1.mfreq:n2.mfreq;
  113.     if(n1.rnum==n2.lnum)
  114.       if(n1.rfreq+n2.lfreq>n.mfreq)
  115.       {
  116. 	n.mnum=n1.rnum;
  117. 	n.mfreq=n1.rfreq+n2.lfreq;
  118.       }
  119. //    cout<<s<<" "<<e<<" "<<n.mfreq<<endl;
  120.     return n;
  121.   }
  122. }
  123. int main()
  124. {
  125.   while(true)
  126.   {
  127.     int n;sf(n);
  128.     if(n==0)break;
  129.     int q;sf(q);
  130.     FOR(i,n){int a;sf(a);arr[i]=a;}
  131.     init(1,0,n-1);
  132.     while(q--)
  133.     {
  134.       int a,b;sf(a);sf(b);
  135.       node n1=query(1,0,n-1,a-1,b-1);
  136.       printf("%d\n",n1.mfreq);
  137.     }
  138.   }
  139. }
Success #stdin #stdout 0.02s 15408KB
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/7XiVC
language:
C++ (gcc 8.3)
created:
12 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!