线段树 TLE #11 求助
查看原帖
线段树 TLE #11 求助
237530
rzh123楼主2023/6/30 18:52
#include <cstdio>
#include <algorithm>
#include <utility>
#include <stack>
#include <unordered_set>
#include <bitset>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
constexpr int N=5e5+7,M=N*4,NC=3e6+5,P=1e9+7,EE=1.3e7+7;
constexpr ll INF=0x3f3f3f3fLL;
int n,m,nc,uu[M],n2,bel[NC];
int dft,dfn[NC],low[NC];
int ind[NC];
struct LR{
    int l,r;
    inline LR():l(INF),r(-INF){}
    inline LR(int v):l(v),r(v){}
    inline LR(int l,int r):l(l),r(r){}
    inline LR operator+(const LR &b)const{
        return LR(min(l,b.l),max(r,b.r));
    }
    inline LR &operator+=(const LR &b){
        l=min(l,b.l),r=max(r,b.r);
        return *this;
    }
    inline ll len()const{return r-l+1ll;}
}bom[NC],sz[NC],ans[NC];
struct B{ll l,r,x;}a[NC];
struct Grp{
    int id,ec,eh[NC];
    Grp(int id):id{id}{}
    struct E{int nxt,to;}e[EE];
    inline void adde(int u,int v){
        // if(id==1) printf("adde %d -> %d\n",u,v);
        // else printf(">>> ADDE %d -> %d\n",u,v);
        e[++ec]={eh[u],v},eh[u]=ec;
    }
}g1(1),g2(2);
struct SegTr{
    int pos[M];
    struct Node{int l,r,u;}tr[NC];
    void build(int k,int l,int r){
        tr[k].l=l,tr[k].r=r,tr[k].u=++nc;
        // printf("%d=[%d,%d]\n",tr[k].u,l,r);
        if(l==r) return pos[l]=tr[k].u,void();
        int md{(l+r)>>1};
        build(k<<1,l,md),build(k<<1|1,md+1,r);
        g1.adde(tr[k].u,tr[k<<1].u),g1.adde(tr[k].u,tr[k<<1|1].u);
    }
    void add(int k,int l,int r,int u){
        if(tr[k].l>r||tr[k].r<l) return;
        if(tr[k].l>=l&&tr[k].r<=r){
            g1.adde(u,tr[k].u);
            return;
        }
        int md{(tr[k].l+tr[k].r)>>1};
        if(l<=md) add(k<<1,l,r,u);
        if(r>md) add(k<<1|1,l,r,u);
    }
}tr;
// trf : u->[l,r]
// trt : [l,r]->u
// S-> trt.u -> trt.leaf -> trf.leaf -> trf.u -> T

inline int disc(){
    static ll b[M];
    int bc{0};
    for(int i{1};i<=n;++i){
        b[++bc]=a[i].l,
        b[++bc]=a[i].r,
        b[++bc]=a[i].x;
    }
    sort(b+1,b+bc+1),
    bc=unique(b+1,b+bc+1)-b-1;
    for(int i{1};i<=n;++i){
        a[i].l=lower_bound(b+1,b+bc+1,a[i].l)-b;
        a[i].r=lower_bound(b+1,b+bc+1,a[i].r)-b;
        a[i].x=lower_bound(b+1,b+bc+1,a[i].x)-b;
    }
    return bc;
}
inline void init(){
    tr.build(1,1,m);
    for(int i{1};i<=m;++i) uu[i]=tr.pos[i];
    for(int i{1};i<=n;++i) bom[uu[a[i].x]]+=LR(i);
}
inline void tarj(int u){
    static stack<int> stk;
    static bool ins[NC];
    dfn[u]=low[u]=++dft;
    stk.emplace(u),ins[u]=true;
    for(int i{g1.eh[u]};i;i=g1.e[i].nxt){
        int v{g1.e[i].to};
        if(!dfn[v]){
            tarj(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++n2;
        while(!stk.empty()){
            int t{stk.top()}; stk.pop(),ins[t]=false;
            bel[t]=n2,sz[n2]+=bom[t];
            if(t==u) break;
        }
    }
}
inline void make(){
    unordered_set<long long> evst;
    for(int i{1};i<=n;++i){
        tr.add(1,a[i].l,a[i].r,uu[a[i].x]);
    }
    fprintf(stderr,"nc=%d,ec=%d\n",nc,g1.ec);
    for(int i{1};i<=m;++i){
        if(!dfn[i]) tarj(i);
    }
    for(int u{1};u<=nc;++u){
        for(int j{g1.eh[u]};j;j=g1.e[j].nxt){
            int v{g1.e[j].to};
            if(bel[u]==bel[v]) continue;
            long long uvh{bel[u]*500005ll+bel[v]*1ll};
            if(evst.find(uvh)!=evst.end()) continue;
            g2.adde(bel[v],bel[u]);
            ++ind[bel[u]];
            evst.emplace(uvh);
        }
    }
}
inline void solve(){
    stack<int> q;
    static bool vst[M];
    for(int i{1};i<=n2;++i) ans[i]=sz[i],vst[i]=false;
    for(int i{1};i<=n2;++i){
        if(!ind[i]){
            vst[i]=true;
            q.emplace(i);
        }
    }
    while(!q.empty()){
        int u{q.top()};q.pop();
        for(int i{g2.eh[u]};i;i=g2.e[i].nxt){
            int v{g2.e[i].to};
            if(vst[v]) continue;
            ans[v]+=ans[u];
            if(!(--ind[v])){
                vst[v]=true;
                q.emplace(v);
            }
        }
    }
    return void();
}
int main(){
    scanf("%d",&n);
    for(int i{1};i<=n;++i){
        long long x,r;
        scanf("%lld%lld",&x,&r);
        a[i]=B{x-r,x+r,x};
    }
    m=disc();
    init();
    make();
    solve();
    long long out{0ll};
    for(int i{1};i<=n;++i){
        long long an=ans[bel[uu[a[i].x]]].len()%P;
        out=(out+1ll*i*an%P)%P;
    }
    printf("%lld\n",out);
    return 0;
}
2023/6/30 18:52
加载中...