posts - 64, comments - 4, trackbacks - 0, articles - 0

poj3264(自写rmq模板)

Posted on 2010-11-05 23:41 acronix 阅读(508) 评论(0)  编辑 收藏 引用 所属分类: hzshuai收集的模板




//rmq 求得最大最小值的序号。 
// 注意位运算优先级比+低。 
//
被字母(l)和 数字(1)搞了半天,最后终于看出来了 
#include 
<cstdio
>
#include <
algorithm
>
using
 
namespace std;

const int MAX = 
50005;
int rmqMin[MAX][20],rmqMax[MAX][
20];
int n,q;

void make_rmq(int len,
int a[])
{
     
int i,j,k,x1,y1,x2,y2;
     
for (i = 1; i <= len; i
++)
         rmqMin[i][
0= rmqMax[i][0
= i;
     
for (j = 1; (1 << j) <= len; j
++)
         
for (i = 1; i + (1 << j) - 1 <= len; i
++)
         {
             x1 
= rmqMin[i][j-
1];
             y1 
= rmqMin[i + (1<<(j-1))][j-
1];
             x2 
= rmqMax[i][j-
1];
             y2 
= rmqMax[i + (1<<(j-1))][j-
1];
             rmqMin[i][j] 
= a[x1] < a[y1] 
? x1 : y1; 
             rmqMax[i][j] 
= a[x2] > a[y2] 
? x2 : y2;
         }
}

int query_min(int lf,int rt,
int a[])
{
    
int d = rt - lf + 1,k = 
0,x,y;
    
while ((1<<(k+1)) 
< d)
          k 
++;
    x 
= rmqMin[lf][k];
    y 
= rmqMin[rt - (1 << k) + 
1][k];
    
return a[x] < a[y] 
? x : y;
}

int query_max(int lf,int rt,
int a[])
{
    
int d = rt - lf + 1, k = 
0, x, y;
    
while ((1<<(k+1)) 
< d)
          k
++;
    x 
= rmqMax[lf][k];
    y 
= rmqMax[rt - (1<<k) + 
1][k];
    
return a[x] > a[y] 
? x : y;
}

int main()
{
    
int he[MAX],i,lf,rt;
    
while (scanf("%d %d"&n, &q) 
!= EOF)
    {
          
for (i = 1; i <= n ; i
++)
              scanf(
"%d"
&he[i]);
          make_rmq(n,he);
          
for (i = 1; i <= q; i
++)
          {
              scanf(
"%d %d"&lf, 
&rt);
              printf(
"%d\n",he[query_max(lf,rt,he)] 
- he[query_min(lf,rt,he)]);
          }
    } 
    
return 
0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理