POJ 3368 & UVA 11235

RMQ应用题。

解题思路参考：http://blog.csdn.net/libin56842/article/details/46482803

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define MAXN 100000+5
 6 using namespace std;
 7 
 8 int num[MAXN],a[MAXN];
 9 int n,q,seg_num;
10 struct Seg{
11     int value,left,right,len;
12 }seg[MAXN];
13 
14 int dp[MAXN][20];
15 void RMQ_init()
16 {
17     for(int i=1;i<=seg_num;i++) dp[i][0]=seg[i].len;
18     double j_max=(log(seg_num)/log(2.0));
19     for(int j=1;j<=j_max;j++)
20     {
21         for(int i=1;i<=seg_num;i++)
22             if(i+(1 << j)-1 <= seg_num) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
23     }
24 }
25 int query(int l,int r)
26 {
27     int k=log(r-l+1)/log(2.0);
28     return max(dp[l][k],dp[r-(1<<k)+1][k]);
29 }
30 
31 int main()
32 {
33     //freopen("input.txt","r",stdin);
34     //freopen("output.txt","w",stdout); 
35     while(scanf("%d",&n) && n!=0)
36     {
37         scanf("%d",&q);
38         seg_num=1;
39         for(int i=1;i<=n;i++)
40         {
41             scanf("%d",&a[i]);
42             if(i==1)
43             {
44                 seg[seg_num].value=a[1];
45                 seg[seg_num].len=1;
46                 seg[seg_num].left=1;
47                 seg[seg_num].right=1;
48                 num[i]=seg_num;
49             }
50             else if(a[i]==a[i-1])
51             {
52                 seg[seg_num].len++;
53                 seg[seg_num].right++;
54                 num[i]=seg_num;
55             }
56             else
57             {
58                 seg_num++;
59                 seg[seg_num].value=a[i];
60                 seg[seg_num].left=i;
61                 seg[seg_num].right=i;
62                 seg[seg_num].len=1;
63                 num[i]=seg_num;
64             }
65         }
66         RMQ_init();
67         while(q--)
68         {
69             int l,r;
70             scanf("%d%d",&l,&r);
71             if(num[l]==num[r])
72             {
73                 printf("%d
",r-l+1);
74             }
75             else
76             {
77                 int ans=0;
78                 if(num[l]+1 <= num[r]-1) ans=query(num[l]+1,num[r]-1);
79                 ans=max( ans , max( seg[ num[l] ].right - l  + 1 , r - seg[ num[r] ].left + 1 ) );
80                 printf("%d
",ans);
81             }
82         }
83     }
84 }

附一个网上的数据生成器：

 1 #include<iostream>
 2 #include<fstream>
 3 #include<cstdlib>
 4 #include<time.h>
 5 using namespace std;
 6 ofstream fout("input.txt");
 7 int main(){
 8     
 9     srand((unsigned)time(NULL));
10     
11     int n = rand()%100 + 1;
12     int q = rand()%100 + 1;
13     
14     fout<<n<<" "<<q<<endl;
15     
16     int start = rand()%1000 - 500;
17     for(int i =1; i<= n;i++){
18         start += rand()%2;
19         fout<<start<<" ";
20     }
21     
22     fout<<endl;
23     for(int i = 0;i < q;i++){
24         start = rand()%n + 1;
25         int end = min(rand()%(n - start + 1) + start,n);
26         fout<<start<<" "<<end<<endl;
27     }
28     
29     fout<<"0"<<endl;
30     return 0;
31 }