线段树优化建图

适用题目特征

一个点/区间向一个区间上的所有点建边。

原理

对每个需要建边的区间上的所有点建立一棵线段树，通过向线段树建边，取代向线段树上所有叶子节点建边的操作。

例题

Luogu P3588
代码如下

/*
Luogu P3588
*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5e5+5;
const int INF=0x3f3f3f3f;
int n,s,m;
int id[maxn*(4+1)],cnt;
struct segmentTree{
    int l,r;
}tr[maxn*(4+1)];
int head[maxn*(4+1)],tot=1;
int in[maxn];
struct node{
    int from,to,w;
}edge[(maxn*(4+1))<<1];
void add(int from,int to,int w){
    edge[++tot].from=head[from],edge[tot].to=to,edge[tot].w=w,head[from]=tot,in[to]++;
}
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r;
    if(l==r) {id[rt]=l;return;}
    id[rt]=++cnt;
    int mid=l+r>>1;
    build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
    add(id[rt<<1],id[rt],0),add(id[rt<<1|1],id[rt],0);
}
void update(int rt,int l,int r,int x){
    if(l<=tr[rt].l&&tr[rt].r<=r){add(id[rt],x,0);return;}
    int mid=tr[rt].l+tr[rt].r>>1;
    if(l<=mid) update(rt<<1,l,r,x);
    if(r>mid) update(rt<<1|1,l,r,x);
}
queue<int>q;
int a[maxn*(4+1)],dis[maxn*(4+1)];
int v[maxn*(4+1)];
void toposort(){
    rep(i,1,cnt) {dis[i]=dis[i]?dis[i]:1;if(!in[i]) q.push(i);}
    while(q.size()){
        int x=q.front();q.pop();v[x]=1;
        for(int i=head[x];i;i=edge[i].from){
            int y=edge[i].to,w=edge[i].w;
            dis[y]=max(dis[x]+w,dis[y]);
            if(a[y]&&dis[y]>a[y]){printf("NIE");exit(0);}
            if(--in[y]==0) q.push(y);
        }
    }
}
void solve(){
    int l,r,k;
    rep(i,1,m){
        scanf("%d%d%d",&l,&r,&k);
        int pre=l-1;cnt++;
        int x;while(k--){
            scanf("%d",&x);
            if(x>pre+1) update(1,pre+1,x-1,cnt);
            add(cnt,x,1);pre=x;
        }
        if(pre<r) update(1,pre+1,r,cnt);
    }
    toposort();
    rep(i,1,n) if(!v[i]||dis[i]>1e9){printf("NIE");return;}
    printf("TAK\n");
    rep(i,1,n) printf("%d ",dis[i]);
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("PUS.in","r",stdin);
    scanf("%d%d%d",&n,&s,&m);cnt=n;
    build(1,1,n);
    int p,d;
    rep(i,1,s) scanf("%d%d",&p,&d),a[p]=dis[p]=d;
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif