为什么线段树会T啊

P1439 【模板】最长公共子序列

Soknock @ 2020-08-08 11:14:47

rt
记得线段树一次操作是logn级别的

然后枚举数字的时候是O(n)

总体也是O(nlogn)啊？？

求教QAQ

这是主程序的一部分

    cin>>n;
    for(int a=1;a<=n;a++){
        cin>>per1[a].data;
        per1[a].id=a;
    }
    for(int b=1;b<=n;b++){
        cin>>per2[b].data;
        per2[b].id=b;
    }
    sort(per2+1,per2+n+1,cmp);
    for(int a=1;a<=n;a++)
        id[a]=per2[a].id;
    for(int a=1;a<=n;a++)
        per1[a].id=id[per1[a].data];
    build(root);
    for(int a=1;a<=n;a++){
        int maxx=query(root,1,per1[a].id-1);
        f[per1[a].id]=maxx+1;
        add(root,per1[a].id,f[per1[a].id]);
    }

by Soknock @ 2020-08-08 11:31:00

@ezoixx130

int query(int l,int r,int rt,int nowl,int nowr){
    if(l==r){
        return z[rt];
    }
    int m=l+r>>1;
    if(nowl<=m){
        if(nowr<=m)return query(lson,nowl,nowr);
        else return max(query(lson,nowl,nowr),query(rson,nowl,nowr));
    }
    else return query(rson,nowl,nowr);
}

by 云浅知处 @ 2020-08-08 11:32:05

@SleepinDog 能说下线段树怎么求LCS吗......我太菜想不出线段树咋求啊/kel

by tongyf @ 2020-08-08 11:39:37

不应该是树状数组求吗

by Soknock @ 2020-08-08 11:40:04

@云浅知处这个是转化后求LIS的

设f[i]表示以 i 数字结尾的最长上升子序列

然后按数字出现顺序依次推

方程

f[i] = max(f[j])+1f[i]=max(f[j])+1

(1<=j<=i-1)

本来求max是需要一重循环O(n)的，然后就可以用线段树优化降成O(logn)

大概是这样,我刚刚markdown炸了

by Soknock @ 2020-08-08 11:41:00

@tongyf 懂了，马上去学

上一页 |