POJ 3368 Frequent values RMQ 训练指南好题

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 const int maxn=1e5+5;
 5 const int inf=0x3f3f3f3f;
 6 
 7 inline int max(int x,int y)
 8 {
 9     return x>y?x:y;
10 }
11 
12 int a[maxn];
13 int left[maxn];
14 int right[maxn];
15 int num[maxn];
16 int dp[maxn][20];
17 
18 void init()
19 {
20     memset(a,0,sizeof a);
21     memset(left,-1,sizeof left);
22     memset(right,-1,sizeof right);
23 }
24 
25 void init_rmq(int n)
26 {
27     for(int i=1;i<=n;i++)
28         dp[i][0]=a[i];
29     for(int j=1;(1<<j)<=n;j++)
30     {
31         for(int i=1;i+(1<<j)-1<=n;i++)
32         {
33             dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
34         }
35     }
36 }
37 
38 int query(int l,int r)
39 {
40     if(l>r)
41         return 0;
42     int k=0;
43     while((1<<(k+1))<=r-l+1)
44         k++;
45     return max(dp[l][k],dp[r-(1<<k)+1][k]);
46 }
47 
48 void solve(int n,int q)
49 {
50     init_rmq(n);
51     for(int i=0;i<q;i++)
52     {
53         int L,R;
54         scanf("%d%d",&L,&R);
55         if(num[L]==num[R])
56         {
57             printf("%d
",R-L+1);
58             continue;
59         }
60         int ans=max(right[num[L]]-L+1,R-left[num[R]]+1);
61         ans=max(ans,query(num[L]+1,num[R]-1));
62         printf("%d
",ans);
63     }
64     return ;
65 }
66 
67 int main()
68 {
69     int cnt;
70     while(scanf("%d",&cnt))
71     {
72         if(!cnt)
73             break;
74         int q;
75         scanf("%d",&q);
76         init();
77         int pre=-inf;
78         int n=0;
79         for(int i=1;i<=cnt;i++)
80         {
81             int u;
82             scanf("%d",&u);
83             if(u!=pre)
84             {
85                 right[n]=i-1;
86                 a[++n]=1;
87                 left[n]=i;
88             }
89             else
90                 a[n]++;
91             num[i]=n;
92             pre=u;
93         }
94         right[n]=cnt;
95 
96         solve(n,q);
97     }
98     return 0;
99 }
View Code
POJ 3368 Frequent values RMQ 训练指南 好题

POJ 3368 Frequent values RMQ 训练指南好题
