Solution
看一下如何建最小割模型：
先求$sum=\sum b_i+w_i$。
如果某一个格子$i$选择了黑色，那么贡献是$-w_i$；如果满足是它奇怪的格子，还有额外贡献$-p_i$。
如果选择了白色，那么贡献是$-b_i$。
总贡献加上$sum$就是答案。
对于如上条件，可以对每一个格子建立一个单元：
可以发现，如果选择白色，那么直接割去$b[i]$这条边。那么要怎么影响之后的黑格呢？
对于每一个点$i$，对于所有的$j>i$，使得$i$按题目要求可以使$j$成为奇怪的格子，那么由$i$向$j'$连一条$\infty$的边。
如果第$i$个格子选择白色，那么对$j$的单元来说，必须割掉$p[j]$这条边，加上原本一定要割的$w[j]$，就是$j$成为奇怪格子的贡献。
由此建模完成。
但是边数高达$O(n^2)$
看看题目的要求是$i<j$，也就是说对于格子$i$，在$1...i-1$的范围内找权值为$[l_i,r_i]$的格子，对单元进行连接。
看起来好像主席树啊，那就关于$a_i$建权值主席树吧。
类似线段树优化网络流建边地，往主席树插入第$i$个格子的时候，将$i$（单元里面的那个$i$点）连向新链上每一个新节点，再由原节点连向新节点，流量都是$\infty$。
注意不能像平时用线段树跑网络流一样在叶子底部连接，然后从儿子往父亲流。因为这样会出现版本的冲突。
跑一下就好了。
PS:边的计数器忘记初始化调了整整一个上午服了。。。
#include <cstdio> #include <algorithm> #include <queue> using namespace std; const int N=5010,NS=100010,INF=2147000000; int n,a[N],b[N],w[N],lb[N],rb[N],p[N],sum; int h[NS],tot,cnt,root[N]; int list[NS],ltot,maxs; int ch[NS][2]; int S,T,dis[NS],cur[NS]; queue<int> q; struct Edge{int v,f,next;}g[1000010]; inline void addEdge(int u,int v,int f){g[++tot].v=v; g[tot].f=f; g[tot].next=h[u]; h[u]=tot;g[++tot].v=u; g[tot].f=0; g[tot].next=h[v]; h[v]=tot; } void lsh(){sort(list+1,list+1+ltot);ltot=unique(list+1,list+1+ltot)-list-1;maxs=ltot;for(int i=1;i<=n;i++){a[i]=lower_bound(list+1,list+1+ltot,a[i])-list;lb[i]=lower_bound(list+1,list+1+ltot,lb[i])-list;rb[i]=lower_bound(list+1,list+1+ltot,rb[i])-list;} } int copy(int u){int v=++cnt;ch[v][0]=ch[u][0]; ch[v][1]=ch[u][1];if(u)addEdge(u,v,INF);return v; } void insert(int u,int &v,int l,int r,int pos,int who){v=copy(u); addEdge(who*2-1,v,INF);if(l==r) return;int mid=(l+r)>>1;if(pos<=mid)insert(ch[u][0],ch[v][0],l,mid,pos,who);elseinsert(ch[u][1],ch[v][1],mid+1,r,pos,who); } void link(int u,int l,int r,int L,int R,int node){if(!u) return;if(L<=l&&r<=R){addEdge(u,node,INF);return;}int mid=(l+r)>>1;if(R<=mid) link(ch[u][0],l,mid,L,R,node);else if(mid<L) link(ch[u][1],mid+1,r,L,R,node);else{link(ch[u][0],l,mid,L,mid,node);link(ch[u][1],mid+1,r,mid+1,R,node);} } bool bfs(){while(!q.empty()) q.pop();q.push(S);for(int i=1;i<=cnt;i++) dis[i]=-1;dis[S]=0;while(!q.empty()){int u=q.front(); q.pop();for(int i=h[u],v;i;i=g[i].next)if(g[i].f&&dis[v=g[i].v]==-1){dis[v]=dis[u]+1;if(v==T) return true;q.push(v);}}return dis[T]!=-1; } int dfs(int u,int delta){if(u==T) return delta;int ret=0,get;for(int i=cur[u],v;i&δi=g[i].next)if(g[i].f&&dis[v=g[i].v]==dis[u]+1){get=dfs(v,min(delta,g[i].f));g[i].f-=get;g[i^1].f+=get;if(g[i].f) cur[u]=i;delta-=get;ret+=get;}if(!ret) dis[u]=-1;return ret; } int dinic(){int ret=0;while(bfs()){for(int i=1;i<=cnt;i++) cur[i]=h[i];ret+=dfs(S,INF);}return ret; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d%d%d%d",&a[i],&b[i],&w[i],&lb[i],&rb[i],&p[i]);list[++ltot]=a[i];list[++ltot]=lb[i];list[++ltot]=rb[i];sum+=b[i]+w[i];}lsh();S=n*2+1; T=n*2+2;tot=1;for(int i=1;i<=n;i++){cnt+=2;addEdge(cnt,cnt-1,p[i]);addEdge(S,cnt-1,w[i]);addEdge(cnt-1,T,b[i]);}cnt+=2;for(int i=1;i<=n;i++)insert(root[i-1],root[i],1,maxs,a[i],i); for(int i=2;i<=n;i++)link(root[i-1],1,maxs,lb[i],rb[i],i*2);int get=dinic();printf("%d\n",sum-get);return 0; }