本文共 2359 字，大约阅读时间需要 7 分钟。

一、题目

一不小心暴露了组织

二、解法

谢谢 ，写得很好

建图我都建的出来，还需要讲么？（图我就直接嫖了）

所以这道题的难点并不在建图，观察这个建边的条件 \(1<j<i,l_i\leq a_j\leq r_i\) ，也就是对于原序列的一个前缀连上所有 \(a_j\in[l_i,r_i]\) 的边，那么可以用 主席树优化建图（和线段树优化建图很类似啊）

为了帮助你理解，我精心（suibian）绘制了一张图：

注意最底层的点还要连同一个位置的 \(rt[i-1]\) 的底层点，然后本题需要离散化。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int M = 200005;const int inf = 0x3f3f3f3f;int read(){	int x=0,f=1;char c;	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}	return x*f;}int n,m,s,t,tot,f[M],a[M],h[M],L[M],R[M];int cnt,ans,rt[M],ls[M],rs[M],dis[M];struct edge{	int v,c,next;	edge(int V=0,int C=0,int N=0) : v(V) , c(C) , next(N) {}}e[5*M];void add(int u,int v,int c){	e[++tot]=edge(v,c,f[u]),f[u]=tot;	e[++tot]=edge(u,0,f[v]),f[v]=tot;}void ins(int &x,int y,int l,int r,int k){	x=++cnt;	ls[x]=ls[y];rs[x]=rs[y];	if(l==r)	{		if(y) add(x+t,y+t,inf);		add(x+t,k,inf);		return ;	}	int mid=(l+r)>>1;	if(a[k]<=mid) ins(ls[x],ls[y],l,mid,k);	else ins(rs[x],rs[y],mid+1,r,k);	if(ls[x]) add(x+t,ls[x]+t,inf);	if(rs[x]) add(x+t,rs[x]+t,inf);}void ask(int x,int l,int r,int k){	if(!x || l>R[k] || L[k]>r) return ;	if(L[k]<=l && r<=R[k])	{		add(k+n,x+t,inf);		return ;	}	int mid=(l+r)>>1;	ask(ls[x],l,mid,k);	ask(rs[x],mid+1,r,k);}int bfs(){	queue
        
          q; for(int i=s;i<=t+cnt;i++) dis[i]=0; q.push(s);dis[s]=1; while(!q.empty()) { int u=q.front();q.pop(); if(u==t) return 1; for(int i=f[u];i;i=e[i].next) { int v=e[i].v; if(!dis[v] && e[i].c>0) { dis[v]=dis[u]+1; q.push(v); } } } return 0;}int dfs(int u,int ept){ if(u==t) return ept; int flow=0,tmp=0; for(int i=f[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]==dis[u]+1 && e[i].c>0) { tmp=dfs(v,min(ept,e[i].c)); if(!tmp) continue; e[i].c-=tmp; e[i^1].c+=tmp; ept-=tmp; flow+=tmp; if(!ept) break; } } return flow;}signed main(){ n=read(); s=0;t=2*n+1;tot=1; for(int i=1,x=0;i<=n;i++) { a[i]=h[++m]=read(); add(s,i,x=read());ans+=x; add(i,t,x=read());ans+=x; L[i]=h[++m]=read(); R[i]=h[++m]=read(); add(i,i+n,read()); } sort(h+1,h+1+m); m=unique(h+1,h+1+m)-h-1; for(int i=1;i<=n;i++) { L[i]=lower_bound(h+1,h+1+m,L[i])-h; R[i]=lower_bound(h+1,h+1+m,R[i])-h; a[i]=lower_bound(h+1,h+1+m,a[i])-h; if(i>1) ask(rt[i-1],1,m,i); ins(rt[i],rt[i-1],1,m,i); } while(bfs()) ans-=dfs(s,inf); printf("%d\n",ans);}