长乐 DAY9

今天是线段树LCA和倍增，就打了个线段树模板，贴段代码

#include
using namespace std;
long long f[900000],a[900000],n,m,t,y,z,k,sum,tag[900000];
void build(long long x,long long l,long long r)
{
    if(l==r) f[x]=a[l];
    else
    {
        int mid=(l+r)>>1;
        build(2*x,l,mid);
        build(2*x+1,mid+1,r);
        f[x]=f[2*x]+f[2*x+1];
    }
}
void downtag(long long x,long long l,long long mid,long long r)
{
    tag[2*x]+=tag[x];
    f[2*x]+=tag[x]*(mid-l+1);
    tag[2*x+1]+=tag[x];
    f[2*x+1]+=tag[x]*(r-mid);
    tag[x]=0;
}
void modify(long long x,long long l,long long r,long long ll,long long rr,long long d)
{
    if(tag[x]!=0) downtag(x,l,(l+r)/2,r);
    if(ll=r)
    {
        f[x]+=d*(r-l+1);
        tag[x]+=d;
    }
    else
    {
        if(ll>r || rr>1;
        modify(2*x,l,mid,ll,rr,d);
        modify(2*x+1,mid+1,r,ll,rr,d);
        f[x]=f[2*x]+f[2*x+1];
    }
}
void query(long long x,long long l,long long r,long long ll,long long rr)
{
    if(tag[x]!=0) downtag(x,l,(l+r)/2,r);
    if(ll=r) sum+=f[x];
    else
    {
        long long mid=(l+r)>>1;
        if(ll>r || rr<l) return;
        if(ll=l) query(2*x+1,mid+1,r,ll,rr);
    }
}
int main()
{
    freopen("explore.in","r",stdin);
    freopen("explore.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) a[i]=1;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&t);
        if(t==1)
        {
            scanf("%lld%lld",&y,&z);
            modify(1,1,n,y,z,-1);
        }
        if(t==2)
        {
            scanf("%lld%lld",&y,&z);
            modify(1,1,n,y,z,1);
        }
        if(t==3)
        {
            scanf("%lld",&y);
            sum=0;
            query(1,1,n,y,y);
            printf("%lld\n",sum);
        }
    }
    return 0;
}