萌新刚学OI,线段树90分求助!

P1047 [NOIP2005 普及组] 校门外的树

__erinww @ 2023-06-25 11:22:23

qw,WA#1了。。

代码:

#include <stdio.h>

#define MAXN 16384

struct TREE_NODE{
    int l,r;
    int value;
} tree[MAXN << 2];

int n,m;
int a[MAXN];

inline void BUILD(int p,int l,int r){
    tree[p].l = l;tree[p].r = r;
    if(l == r){
        tree[p].value = 1;
        return ;
    }
    int mid = l+r >> 1;
    BUILD(p << 1,l,mid);
    BUILD(p << 1|1,mid+1,r);
    tree[p].value = tree[p << 1].value+tree[p << 1|1].value;
}

inline void UPDATE(int p,int l,int r){
    int &x = tree[p].l;int &y = tree[p].r;
    if(x == y){
        tree[p].value = 0;
        return ;
    }
    int mid = x+y >> 1;
    if(l <= mid)    UPDATE(p << 1,l,r);
    if(r >  mid)    UPDATE(p << 1|1,l,r);
    tree[p].value = tree[p << 1].value+tree[p << 1|1].value;
}

inline int SEARCH(int p,int l,int r){
    int &x = tree[p].l;int &y = tree[p].r;
    if(x >= l && y <= r)    return tree[p].value;
    int mid = x+y >> 1;
    int step = 0;
    if(l <= mid)    step += SEARCH(p << 1,l,r);
    if(r >  mid)    step += SEARCH(p << 1|1,l,r);
    return step;
}

signed main(){
    scanf("%d%d",&n,&m);
    BUILD(1,1,n);
    while(m --){
        int l,r;
        scanf("%d%d",&l,&r);
        UPDATE(1,l,r);
    }printf("%d",SEARCH(1,1,n)+1);

    return 0;
}

(=・ω・=)


by __erinww @ 2023-06-25 11:25:38

模拟太难了,所以我打了个线段树()


by jiangjiangQwQ @ 2023-06-25 11:49:54

《模拟太难了》


by _Cyan_ @ 2023-06-25 12:03:40

这活整的不错,下次不要再整了


by hjqhs @ 2023-06-25 12:53:05

@__erinww 位置0也是有树的


by __erinww @ 2023-06-25 13:01:51

@hjqhs 谢谢%


by RisefromtheAshes @ 2023-06-25 13:29:24

简单题直接用模拟,否则会把自己整死(


|