校门外的树 - zzf - Vijos

题解
3159968027 LV 6 MOD @ 2018-10-15 19:03:57

#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 2000500;
const int M = 6000000;
struct Node
{
    int l,r,tot;//这个点表示区间[l,r]的和
    int mid;//表示这个点的左子节点是[l,mid]，右子节点是[mid+1,r]，如果当前点是叶节点mid没有用
    long long val;//区间[l,r]的和
    long long tag;//表示标记 
}tree[M];
int n,m;
void MakeTree(int x,int l,int r)
{
    tree[x].l=l;
    tree[x].r=r;
    tree[x].tot=r-l+1;
    if(l==r)
    {
        tree[x].val=1;
    }
    else
    {
        int mid=(l+r)/2;
        tree[x].mid=mid;
        MakeTree(x*2,l,mid);
        MakeTree(x*2+1,mid+1,r);
        tree[x].val=tree[x*2].val+tree[x*2+1].val;
    }
}

void AddNode(int v,long long z)
{
    tree[v].val+=z*tree[v].tot;
    if (tree[v].val<0) tree[v].val=0; 
    tree[v].tag+=z;
}

void Clear(int v)
{
    AddNode(v*2,tree[v].tag);
    AddNode(v*2+1,tree[v].tag);
    tree[v].tag=0;
}

void Add(int v,int a,int b,int z)//表示[a,b]要增加z，现在处理点v 
{
    if(tree[v].l==a && tree[v].r==b)
    {
        AddNode(v,z);
        return;
    }
    Clear(v);
    if(b<=tree[v].mid)
        Add(v*2,a,b,z);
    else if(a>tree[v].mid)
        Add(v*2+1,a,b,z);
    else
    {
        Add(v*2,a,tree[v].mid,z);
        Add(v*2+1,tree[v].mid+1,b,z);
    }
    tree[v].val=tree[v*2].val+tree[v*2+1].val;
    if (tree[v].val<0) tree[v].val=0; 
}

long long Find(int v,int a,int b)//表示求[a,b]的和，现在处理点v 
{
    if(tree[v].l==a && tree[v].r==b)
        return tree[v].val;
    Clear(v);
    if(b<=tree[v].mid)
        return Find(v*2,a,b);
    if(a>tree[v].mid)
        return Find(v*2+1,a,b);
    return Find(v*2,a,tree[v].mid)+Find(v*2+1,tree[v].mid+1,b);
}

int main()
{
    int i;
    scanf("%d",&n);
    MakeTree(1,0,n);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        Add(1,a,b,-1);
    }
    printf("%lld",Find(1,0,n));
}

PA_lotusbl LV 5 MOD @ 2018-10-15 20:05:12

#include <iostream>
#include <cstdio>
#include <algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define N 10001
using namespace std;

int l,m;
struct zzf{
    int left,right,tot;
    int mid;
    long long tree,tag;
}zzf_[N];

void maketree(int bb,int ll,int n){
    zzf_[n].left=bb;
    zzf_[n].right=ll;
    zzf_[n].tot=ll-bb+1;
    if(bb==ll){
        zzf_[n].tree=1;
    }
    else{
        int mid=(bb+ll)/2;
        zzf_[n].mid=mid;
        maketree(bb,mid,n*2);
        maketree(mid+1,ll,n*2+1);   
        zzf_[n].tree=zzf_[n*2].tree+zzf_[n*2+1].tree;
    }
    

}

void addnode(int v,long long z){
    zzf_[v].tree+=z*zzf_[v].tot;
    if(zzf_[v].tree<0) zzf_[v].tree=0;
    zzf_[v].tag+=z;
}

void clear(int v){
    addnode(v*2,zzf_[v].tag);
    addnode(v*2+1,zzf_[v].tag);
    zzf_[v].tag=0;
}

void add(int v,int x,int y,int z){
    if(zzf_[v].left==x && zzf_[v].right==y){
        addnode(v,z);
        return;
    }
    clear(v);
    if(y<=zzf_[v].mid)
        add(v*2,x,y,z);
    else if(x>zzf_[v].mid)
        add(v*2+1,x,y,z);
    else {
        add(v*2,x,zzf_[v].mid,z);
        add(v*2+1,zzf_[v].mid+1,y,z);
    }       
    zzf_[v].tree=zzf_[v*2].tree+zzf_[v*2+1].tree;
    if(zzf_[v].tree<0) zzf_[v].tree=0;
}   

long long find(int v,int x,int y){
    if(zzf_[v].left==x && zzf_[v].right==y)
        return zzf_[v].tree;
    clear(v);
    if(y<=zzf_[v].mid)
        return find(v*2,x,y);
    if(x>zzf_[v].mid)
        return find(v*2+1,x,y);
    return find(v*2,x,zzf_[v].mid)+find(v*2+1,zzf_[v].mid+1,y);         
}

int main(void){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d%d",&l,&m);
    maketree(0,l,1);
    For(i,1,m)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(1,a,b,-1);
        }
    
    printf("%lld",find(1,0,l));
    

    fclose(stdin);
    fclose(stdout);
    return 0;
}

PA_lotusbl LV 5 MOD @ 2018-10-15 19:43:04

啦啦啦啦啦啦啦啦啦啦啦啦啦
PA_lotusbl LV 5 MOD @ 2018-10-15 19:04:49

域主^(*￣(oo)￣)^
又发题解啦

水一水

棒棒棒