线段树WA了第一个点┭┮﹏┭┮

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

dry_ @ 2023-09-12 21:33:34

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
long long ans;
struct node
{
    int l; int r;
    long long num;
    long long add;
}tree[800012];
int up1(int ind) { return ind << 1 ; }
int up2(int ind){return ind << 1 | 1;}
void build(int l,int r,int ind)
{
    tree[ind].num = (r - l + 1);
    tree[ind].l = l;
    tree[ind].r = r;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(l,mid,up1(ind));
    build(mid + 1,r,up2(ind));
}
void check(int ind)
{
    if(tree[ind].add)
    {
        tree [ up1(ind) ].num -= tree [ ind ].add * ( tree [ up1( ind ) ].r - tree [ up1( ind ) ].l + 1 );
        tree [ up2(ind) ].num -= tree [ ind ].add * ( tree [ up2( ind ) ].r - tree [ up2( ind ) ].l + 1 );
        tree [ up1(ind) ].add += tree[ind].add ; tree[up2(ind)].add += tree[ind].add ; tree[ind].add = 0 ;
        if(tree[up1(ind)].num < 0)tree[up1(ind)].num = 0;if(tree[up2(ind)].num < 0)tree[up2(ind)].num = 0;
    }
}
void amend(int l,int r,int ind)
{
    if(l <= tree[ind].l && r >= tree[ind].r)
    {tree[ind].num -= (tree[ind].r - tree[ind].l + 1);
     tree[ind].add += 1; if(tree[ind].num < 0)
     tree[ind].num = 0; return; } check(ind);
    if(tree[up1(ind)].r >= l) amend(l,r,up1(ind));
    if(tree[up2(ind)].l <= r) amend(l,r,up2(ind));
    long long p1 = tree[up1(ind)].num;
    long long p2 = tree[up2(ind)].num;
    tree[ind].num = p1 + p2;
}
int main()
{
    scanf("%d %d",&n,&m);
    build(1,n,1);for(int i = 1;i <= m;i++)
    {scanf("%d %d",&l,&r);if(l <= 0)l = 1;
    if(r <= 0) r = 1; amend(l,r,1);
    } printf("%lld\n",tree[1].num);
}

by dry_ @ 2023-09-12 21:36:26

哦对了,```cpp printf("%lld\n",tree[ind].num);

要写成```
printf("%lld\n",tree[ind].num + 1);

by tjtdrxxz @ 2023-09-16 21:52:15

已AC,少初始化了一个点...


by dry_ @ 2023-09-16 22:07:15

那个是我小号(回的时候用错了)


|