fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int arr[100001];
  4. class Node
  5. {
  6. public:
  7.     pair<int,int> pre,suf;
  8.     int ans;
  9. } segTree[270000];
  10. void connect(int pos,int a,int b)
  11. {
  12.     if(segTree[b].pre.first==segTree[a].pre.first)
  13.         segTree[pos].pre={segTree[a].pre.first,segTree[b].pre.second+segTree[a].pre.second};
  14.     else
  15.         segTree[pos].pre={segTree[a].pre.first,segTree[a].pre.second};
  16.     if(segTree[b].suf.first==segTree[a].suf.first)
  17.         segTree[pos].suf={segTree[b].suf.first,segTree[b].suf.second+segTree[a].suf.second};
  18.     else
  19.         segTree[pos].suf={segTree[b].suf.first,segTree[b].suf.second};
  20.     if(segTree[a].suf.first==segTree[b].pre.first)
  21.         segTree[pos].ans=max(segTree[pos].pre.second,max(segTree[pos].suf.second,segTree[a].suf.second+segTree[b].pre.second));
  22.     else
  23.         segTree[pos].ans=max(segTree[pos].pre.second,segTree[pos].suf.second);
  24. }
  25. void maketree(int low,int high,int pos)
  26. {
  27.     if(low==high){
  28.         segTree[pos].pre= {arr[low],1};
  29.         segTree[pos].suf= {arr[low],1};
  30.         segTree[pos].ans=1;
  31.         return;
  32.     }
  33.     int mid=(low+high)/2;
  34.     maketree(low,mid,2*pos+1);
  35.     maketree(mid+1,high,2*pos+2);
  36.     connect(pos,2*pos+1,2*pos+2);
  37. }
  38. Node jointhem(Node temp1,Node temp2)
  39. {
  40.     if(temp1.ans==0)
  41.         return temp2;
  42.     Node temp;
  43.     if(temp2.pre.first==temp1.pre.first)
  44.         temp.pre={temp1.pre.first,temp2.pre.second+temp1.pre.second};
  45.     else
  46.         temp.pre={temp1.pre.first,temp1.pre.second};
  47.     if(temp2.suf.first==temp1.suf.first)
  48.         temp.suf={temp2.suf.first,temp2.suf.second+temp1.suf.second};
  49.     else
  50.         temp.suf={temp2.suf.first,temp2.suf.second};
  51.     if(temp1.suf.first==temp2.pre.first)
  52.         temp.ans=max(temp.pre.second,max(temp.suf.second,temp1.suf.second+temp2.pre.second));
  53.     else
  54.         temp.ans=max(temp.pre.second,temp.suf.second);
  55.     return temp;
  56. }
  57. Node query(int low,int high,int qlow,int qhigh,int pos)
  58. {
  59.     if(high<qlow || low>qhigh){
  60.         Node temp;
  61.         temp.pre={0,0},temp.suf={0,0},temp.ans=0;
  62.         return temp;
  63.     }
  64.     if(low>=qlow && high<=qhigh)
  65.         return segTree[pos];
  66.     int mid=(low+high)/2;
  67.     Node temp1=query(low,mid,qlow,qhigh,2*pos+1);
  68.     Node temp2=query(mid+1,high,qlow,qhigh,2*pos+2);
  69.     return jointhem(temp1,temp2);
  70. }
  71. int main()
  72. {
  73.     int n,q,i,j,temp;
  74.     while(cin>>n){
  75.         if(n==0)
  76.             return 0;
  77.         cin>>q;
  78.         temp=2*((int)(pow(2,ceil(log2(100001)))+0.5))-1;
  79.         for(i=0; i<n; i++)
  80.             cin>>arr[i];
  81.         maketree(0,n-1,0);
  82.         int a,b;
  83.         Node temp;
  84.         for(i=0;i<q;i++){
  85.             cin>>a>>b;
  86.             temp=query(0,n-1,a-1,b-1,0);
  87.             cout<<temp.ans<<endl;
  88.         }
  89.     }
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0s 8868KB
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/JJB1iw
language:
C++14 (gcc 8.3)
created:
3 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!