线段树 10pts求调
查看原帖
线段树 10pts求调
351679
shaun2000楼主2024/9/1 09:08

record

#include <bits/stdc++.h>

using namespace std;
int n,m;
int ls(int x)
{
    return x<<1;
}
int rs(int x)
{
    return x<<1|1;
}
int ans[400005];
int tag[400005];
void push_up(int p)
{
    ans[p]=ans[ls(p)]+ans[rs(p)];
}

void f(int p,int l,int r)
{
    tag[p]^=1;
    ans[p]=(r-l+1-ans[p]);

}
void push_down(int p,int l,int r)
{

    if(tag[p])
    {
        int mid=(l+r)/2;
        f(ls(p),l,mid);
        f(rs(p),mid+1,r);
        tag[p]=0;
    }
}
void update(int p,int l,int r,int nl,int nr)
{
    if(nl<=l && r<=nr)
    {
        tag[p]^=1;
        ans[p]=(r-l+1-ans[p]);
        return;
    }
    int mid=(l+r)/2;
    if(nl<=mid)
        update(ls(p),l,mid,nl,nr);
    if(nr>mid)
        update(rs(p),mid+1,r,nl,nr);
    push_up(p);
}
int query(int p,int l,int r,int nl,int nr)
{

    if(nl<=l && nr>=r)
        return ans[p];

    push_down(p,l,r);
    int mid=(l+r)/2,res=0;
    if(nl<=mid)
        res+=query(ls(p),l,mid,nl,nr);
    if(nr>mid)
        res+=query(rs(p),mid+1,r,nl,nr);
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(; m; m--)
    {
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(op==0)
        {
            update(1,1,n,a,b);
        }
        else
            printf("%d\n",query(1,1,n,a,b));
    }



    return 0;
}
2024/9/1 09:08
加载中...