NlogN | Comzyh的博客

RMQ(range minimum/maximum query)问题

给定一组数，给定给定一个区间，求区间最值，算法大致有以下几种

O(n)算法,直接扫描一遍区间,求最值.
优点:编程简单,可动态求解(数组可动态更改)
缺点:不能处理大量数据.
使用线段树,可以优化成Log(N)
优点:时间复杂度低,更改操作复杂度低
缺点:编程复杂度大.
预处理O(N log N),查询O(1)的Sparse_Table(稀疏表)算法
优点:编程简单,可动态求解(数组可动态更改)
缺点:没啥,基本算法不能处理动态更改，改进后可以更改(复杂度貌似不小，大于LogN).
快速选择法 Quick Slect(打酱油的,不是RMQ)，能在O(N) (我估算是1.5N)的时间内得到区间第K大/小值

下面主要介绍ST算法
Continue reading “用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法”

MY CODE:

#include<stdio.h>
//nlogn算法
/*把10000搞成1000了，错了一下午*/ 
int n,max;
int b[10001],a[10001],len[10001];
 int bins(int key) {
    static int l,r,y;
    l=0;r=n;
    while (l<=r){
          y=(l+r)>>1;
          if (b[y]>key) r=y-1;else
          if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便
          else return y;
          }
    }
int main(){
    int i,j;
    scanf("%d\n",&n);
    for (i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=20000;}
    b[0]=0;//这个初始化要比所有元素小
    for (i=1;i<=n;i++){
         len[i]=bins(a[i]-1)+1;
         if (len[i]>max) max=len[i];
         if (b[len[i]]>a[i]) b[len[i]]=a[i];
         }
        printf("%d",max);
        return 0;       
    }

#include<stdio.h>

//nlogn算法

/*把10000搞成1000了，错了一下午*/

int n,max;

int b[10001],a[10001],len[10001];

int bins(int key) {

static int l,r,y;

l=0;r=n;

while (l<=r){

y=(l+r)>>1;

if (b[y]>key) r=y-1;else

if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便

else return y;

}

int main(){

int i,j;

scanf("%d\n",&n);

for (i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=20000;}

b[0]=0;//这个初始化要比所有元素小

for (i=1;i<=n;i++){

len[i]=bins(a[i]-1)+1;

if (len[i]>max) max=len[i];

if (b[len[i]]>a[i]) b[len[i]]=a[i];

}

printf("%d",max);

return 0;

}

Continue reading “P156 吞噬比赛 NlogN最长不下降子序列”