P2082 题解

lhz2022 · 2024-11-24 21:31:40 · 题解

本题的另外一个做法可以是动态开点线段树。

前置知识：线段树。

我们发现，本题的左，右端点都是 10^{17} 级别的，所以我们肯定没法开一个 4 \times 10^{17} 的数组。

我们发现，线段树的很多节点都是不用建出来的。我们只需要在修改、下传标记的时候新建即可。

我们在学线段树的时候，我们知道：

任何一个线段都可以拆分成不超过 2\times t 条线段，其中，t 代表了线段树的深度。

假设在最坏情况下，所有线段都需要新建，那么节点个数就是 O(n \log \text{值域}) 级别的，这里的 n 代表操作个数。

那么它的空间复杂度就是 O(n \log \text{值域})。

新建节点的方法可以参考字典树。

最后维护区间和即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() puts("I AK")
#define N 100007
#define INF 0x3f3f3f3f
int n,rt,tot;
struct tree{
    int lc,rc,val,lazy;
}tr[N*64];
int new_node(){
    ++tot;
    tr[tot]={0,0,0,0};
    return tot;
}
void push_up(int rt){
    tr[rt].val=tr[tr[rt].lc].val+tr[tr[rt].rc].val;
}
void push_down(int rt,int l,int r){
    if(l==r||tr[rt].lazy==0) return;
    int mid=(l+r)>>1;
    if(!tr[rt].lc) tr[rt].lc=new_node();
    tr[tr[rt].lc].val=mid-l+1;
    tr[tr[rt].lc].lazy=1;
    if(!tr[rt].rc) tr[rt].rc=new_node();
    tr[tr[rt].rc].val=r-mid;
    tr[tr[rt].rc].lazy=1;
    tr[rt].lazy=0;
}

void update_one(int &rt,int l,int r,int idx,int add){
    if(!rt) rt=new_node();
    if(l==r){
        tr[rt].val+=add;
        return;
    }
    int mid=(l+r)/2;
    if(idx<=mid) update_one(tr[rt].lc,l,mid,idx,add);
    else update_one(tr[rt].rc,mid+1,r,idx,add);
    push_up(rt);
}
void update(int &rt,int l,int r,int ul,int ur){
    if(!rt) rt=new_node();
    if(ul<=l&&ur>=r){
        tr[rt].val=r-l+1;
        tr[rt].lazy=1;
        return;
    }
    push_down(rt,l,r);
    int mid=(l+r)/2;
    if(ul<=mid) update(tr[rt].lc,l,mid,ul,ur);
    if(ur>mid) update(tr[rt].rc,mid+1,r,ul,ur);
    push_up(rt);
}
int query(int &rt,int l,int r,int ql,int qr){
    if(!rt) rt=new_node();
    if(ql<=l&&qr>=r) return tr[rt].val;
    push_down(rt,l,r);
    int mid=(l+r)>>1;
    if(qr<=mid) return query(tr[rt].lc,l,mid,ql,qr);
    if(ql>mid) return query(tr[rt].rc,mid+1,r,ql,qr);
    return query(tr[rt].lc,l,mid,ql,qr)+query(tr[rt].rc,mid+1,r,ql,qr);
}
int r=1e17;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,u,v;i<=n;++i){
        cin>>u>>v;
        update(rt,1,r,u,v);
    }
    cout<<query(rt,1,r,1,r);
    return 0;
}