fork download 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<ctype.h>
  4. #include<string.h>
  5. #include<stdlib.h>
  6. #include<math.h>
  7. #include<string>
  8. #include<algorithm>
  9. #include<vector>
  10. #include<sstream>
  11. #include<stack>
  12. #include<queue>
  13. #include<map>
  14. #include<set>
  15. using namespace std;
  16.  
  17. const int SIZE=100005;
  18. struct TT{
  19.     int aa,bb;
  20. };
  21. int arr[SIZE],tree[SIZE*3];
  22. TT brr[SIZE*3];
  23. map<int,int>MP;
  24. int t,cases,test,n,q,i,a,b,val;
  25.  
  26. int func(int m,int n){
  27.     int i,t,asg=0;
  28.     for(i=brr[m].aa;i<=brr[m].bb;i++){
  29.         t=arr[i];
  30.         if(MP.find(t)==MP.end()) MP[t]=asg++;
  31.     }
  32.     for(i=brr[n].aa;i<=brr[n].bb;i++){
  33.         t=arr[i];
  34.         if(MP.find(t)==MP.end()) MP[t]=asg++;
  35.     }
  36.     t=MP.size();
  37.     MP.clear();
  38.     return t;
  39. }
  40.  
  41. void find(int node,int low,int high){
  42.     int mid,add,left,right;
  43.     if(low==high){
  44.         tree[node]=1;
  45.         return;
  46.     }
  47.     left=node<<1;
  48.     right=left+1;
  49.     mid=(low+high)>>1;
  50.     brr[left]={low,mid};
  51.     brr[right]={mid+1,high};
  52.     brr[node]={low,high};
  53.     find(left,low,mid);
  54.     find(right,mid+1,high);
  55.     tree[node]=func(left,right);
  56. }
  57.  
  58. int query(int node,int low,int high,int i,int j){
  59.     if(i>high || j<low) return 0;
  60.     if(low>=i && high<=j) return tree[node];
  61.     int left,right,mid,temp,temp2,add;
  62.     left=node<<1;
  63.     right=left+1;
  64.     mid=(low+high)>>1;
  65.     temp=query(left,low,mid,i,j);
  66.     temp2=query(right,mid+1,high,i,j);
  67.     add=max(temp,temp2);
  68.     return add;
  69. }
  70.  
  71. int main()
  72. {
  73.     #ifndef ONLINE_JUDGE
  74.     freopen("input.txt","r",stdin);
  75.     //freopen("output.txt","w",stdout);
  76.     #endif
  77.  
  78.     scanf("%d",&t);
  79.     while(t--){
  80.         scanf("%d%d",&n,&q);
  81.         for(i=1;i<=n;i++)
  82.             scanf("%d",&arr[i]);
  83.         find(1,1,n);
  84.         for(i=1;i<16;i++) printf("%d (%d %d) %d\n",i,brr[i].aa,brr[i].bb,tree[i]);
  85.         printf("Case %d:\n",++cases);
  86.         while(q--){
  87.             scanf("%d%d",&a,&b);
  88.             val=query(1,1,n,a,b);
  89.             printf("%d\n",val);
  90.         }
  91. 	}
  92.     return 0;
  93. }
  94.  
Success #stdin #stdout 0s 7340KB
comments (?)
stdin 
1
 
8 5
1 1 1 2 3 5 1 2
1 8
2 3
3 6
4 5
4 8
stdout 
1 (1 8) 4
2 (1 4) 2
3 (5 8) 4
4 (1 2) 1
5 (3 4) 2
6 (5 6) 2
7 (7 8) 2
8 (1 1) 1
9 (2 2) 1
10 (3 3) 1
11 (4 4) 1
12 (5 5) 1
13 (6 6) 1
14 (7 7) 1
15 (8 8) 1
Case 1:
4
1
2
1
4
https://ideone.com/53zyh9
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!