为什么线段树会T啊

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

    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 ezoixx130 @ 2020-08-08 11:17:35

你不把线段树放出来谁知道你线段树写错了没有。。。

by djwj233 @ 2020-08-08 11:19:07

是这个吗

by MVP_Harry @ 2020-08-08 11:19:24

@SleepinDog 线段树的锅吧，线段树只有用了懒标记才是logn的

by Soknock @ 2020-08-08 11:20:36

哦哦不好意思@ezoixx130

#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

void update(int rt){
    z[rt]=max(z[rt<<1],z[rt<<1|1]);
}

void build(int l,int r,int rt){
    if(l==r){
        return;
    }
    int m=l+r>>1;
    build(lson);
    build(rson);
    update(rt);
}

void add(int l,int r,int rt,int p,int k){
    if(l==r){
        z[rt]=k;
        return;
    }
    int m=l+r>>1;
    if(p<=m)add(lson,p,k);
    else add(rson,p,k);
    update(rt);
}

by Soknock @ 2020-08-08 11:21:42

@djwjfkewhfkhdwfds ？为啥呀

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

@MVP_Harry 这个题只是点修改，没有区间修改，应该也是logn的吧

by t162 @ 2020-08-08 11:23:54

@djwjfkewhfkhdwfds 就是 \operatorname O(\log n)

by djwj233 @ 2020-08-08 11:24:19

@SleepinDog 不是，我紫菜

眼瞎看错了

by ezoixx130 @ 2020-08-08 11:30:06

@SleepinDog ？你 query 呢

by Soknock @ 2020-08-08 11:30:27

是排序+建树+每次询问和修改然后常数过大了吗？？？

我下的数据都是范围卡满的