lx-blog - 博客生活

RMQ的妙用、

刚学了RMQ算法。

做pku 2201 的时候。刚开始根本没啥好的算法。按照一般的思路走下来肯定是超时。

后来看了讨论，用不熟练的RMQ写了个。（搞惨了，这个程序整了我一整天）

#include<algorithm>
#include<cmath>
#include<stdlib.h>
#include <algorithm>
using namespace std;
#define MAX 50005
struct Node{
       int parent;
       int left;
       int right;
       int id;
       int key;
       int akey;
};
Node tree[MAX];
int n,f[MAX][16];
bool cmpbykey(Node n1,Node n2){
     return (n1.key<n2.key);
}

bool cmpbyid(Node n1,Node n2){
     return (n1.id<n2.id);
}
void RMQ(){
     sort(tree+1,tree+n+1,cmpbykey);
     for(int i=1;i<=n;i++){
         f[i][0]=i;
     }
     for(int j=1;j<=log((double)(n))/log(2.0);j++)
     for(int i=1;(i+(1<<j)-1)<=n;i++){
             f[i][j]=f[i][j-1];
             if(tree[f[i+(1<<(j-1))][j-1]].akey<tree[f[i][j]].akey){
                    f[i][j]=f[i+(1<<(j-1))][j-1];
             }
     }
     /*for(int j=0;j<=log((double)(n-1))/log(2.0);j++)
     for(int i=1;i+(1<<j)-1<=n;i++){
        printf("%d",f[i][j]);

        system("pause");
     }*/

}

int Min_setbyRmq(int left,int right){
                 int m;
                 m=(log((double)(right-left+1))/log(2.0));
                 if(tree[f[left][m]].akey<tree[f[right-(1<<(m))+1][m]].akey)
                 return f[left][m];
                 else return f[right-(1<<m)+1][m];

}
bool maketree(int left,int right){
     if(left==right) {
       tree[left].left=0;
       tree[left].right=0;
       return true;
     }
     int root,rootleft,rootright;
     root=Min_setbyRmq(left,right);

     if(root!=left){
         rootleft=Min_setbyRmq(left,root-1);

     }
     if(root!=right){
          rootright=Min_setbyRmq(root+1,right);
     }
     bool check1=true,check2=true;
     if(root!=left&&tree[root].key>tree[rootleft].key){
              tree[root].left=tree[rootleft].id;
              tree[rootleft].parent=tree[root].id;
              check1=maketree(left,root-1);
     }
     if(root!=right&&tree[root].key<tree[rootright].key){
              tree[root].right=tree[rootright].id;
              tree[rootright].parent=tree[root].id;
              check2=maketree(root+1,right);
     }
     return (check1&&check2);
}
int main(){
        int i,t;
        scanf("%d",&n);

        for(i=1;i<=n;i++){
            scanf("%d%d",&tree[i].key,&tree[i].akey);
            tree[i].id=i;
        }
        RMQ();
        if(maketree(1,n)){
        /* for(i=1;i<=n;i++){

            printf("%d %d %d\n",tree[i].parent,tree[i].left,tree[i].right);
            system("pause");
        }*/
        printf("YES\n");
        sort(tree+1,tree+n+1,cmpbyid);
        for(i=1;i<=n;i++){
            printf("%d %d %d\n",tree[i].parent,tree[i].left,tree[i].right);
            system("pause");
        }
      }
      else printf("NO\n");
}

//主要是调试的时候，整死就是过不去。

//虽然不是完全独立坐下来的。不过还是感到很高兴、

posted @ 2009-08-15 17:27 昨日重现阅读(115) | 评论 (0) | 编辑收藏

pku 3264 第一个一次过的线段树。

#include<stdio.h>

#include<string.h>
#include<stdlib.h>
#define MAX 500000

struct Node{
       int left,right;
       int max,min;
}tree[MAX];
int Min,Max;
void build(int root,int left,int right){
     tree[root].left=left;
     tree[root].right=right;
     tree[root].max=0;
     tree[root].min=9999999;
     if(right-left==0) return;
     int mid=(left+right)>>1;
     build(2*root,left,mid);
     build(2*root+1,mid+1,right);
}
void add(int root,int w,int h){
     int lf=tree[root].left;
     int rf=tree[root].right;
     if(tree[root].max<h)
     tree[root].max=h;
     if(tree[root].min>h)
     tree[root].min=h;
     if(lf==rf) return;
     int mid= (rf+lf)>>1;
     if(w<=mid) add(2*root,w,h);
     else        add(2*root+1,w,h);
}
void query(int root,int left,int right){
     int lf=tree[root].left;
     int rf=tree[root].right;
     if(lf==left&&rf==right){
          if(tree[root].max>Max)
          Max=tree[root].max;
          if(tree[root].min<Min)
          Min=tree[root].min;
          return;
     }
     //if(lf==rf) return;
     int mid=(lf+rf)>>1;
     if(mid>=right)
     query(2*root,left,right);
     else if(mid<left)
     query(2*root+1,left,right) ;
     else
     {query(2*root,left,mid);
      query(2*root+1,mid+1,right);
     }
}
int main(){
    int n,m,i,j,high,left,right;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    /*for(i=1;i<=12;i++){
       printf("%d %d %d %d",tree[i].left,tree[i].right,tree[i].min,tree[i].max);
       system("pause");
     }*/
    for(i=1;i<=n;i++){
        scanf("%d",&high);
        add(1,i,high);
    }
    for(j=1;j<=m;j++){
        scanf("%d%d",&left,&right);
        Min=9999999;
        Max=0;
        query(1,left,right);
        printf("%d\n",Max-Min);
       // system("pause");
    }
}
//不过还不会用ST算法。听说ST更好。继续学吧！