题目传送门
分析：
首先把公式换一下。。。
ans=sigma(i<=n){w[i]+b[i]} - sigma(i为白色){b[i]} -sigma(i为黑色){w[i]} - sigma(i奇怪){p[i]}
然后我们就需要后面那一块最小。。。
非黑即白是一对矛盾关系，奇怪的点也是一个矛盾关系
于是考虑最小割
首先每个点分别向S和T连边，容量分别是b[i]与w[i]
然后每个点 i 复制出一个 i' 连容量为p[i]的边
i' 再向所有矛盾的 j 连边，容量INF
demo，边数好像会炸
然后发现非法的 j 是区间
然后就线段树连边
编号还要比 i 小。。。
那就只有主席树了
这么强行地把主席树和网络流联系起来吗，无力吐槽2333
8是很懂，这个范围能过。。。
1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<vector> 5 #include<algorithm> 6 #include<iostream> 7 #include<cstring> 8 9 #define maxn 5005 10 #define maxm 1000005 11 #define INF 0x3f3f3f3f 12 #define opst(i) (((i-1)^1)+1) 13 14 using namespace std; 15 16 inline int getint() 17 { 18 int num=0,flag=1;char c; 19 while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; 20 while(c>='0'&&c<='9')num=num*10+c-48,c=getchar(); 21 return num*flag; 22 } 23 24 int n,S,T,N; 25 int fir[maxn*20],nxt[maxm],to[maxm],cap[maxm],cnt; 26 int h[20*maxn]; 27 int A[maxn],L[maxn],R[maxn],B[maxn],W[maxn],P[maxn],Q[3*maxn]; 28 struct node{int lc,rc;}t[maxn*20]; 29 int rt[maxn],tot; 30 int ans,maxflow; 31 32 inline void newnode(int u,int v,int w) 33 {to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,cap[cnt]=w;} 34 inline void Add(int u,int v,int w) 35 {newnode(u,v,w),newnode(v,u,0);} 36 37 inline int find(int num) 38 { 39 int l=1,r=N; 40 while(l<r) 41 { 42 int mid=(l+r)>>1; 43 if(Q[mid]>=num)r=mid; 44 else l=mid+1; 45 } 46 return l; 47 } 48 49 inline void Link(int now,int l,int r,int i) 50 { 51 if(R[i]<l||L[i]>r)return; 52 if(L[i]<=l&&r<=R[i]){Add(i+n,T+now,INF);return;} 53 int mid=(l+r)>>1; 54 if(t[now].lc)Link(t[now].lc,l,mid,i); 55 if(t[now].rc)Link(t[now].rc,mid+1,r,i); 56 } 57 58 inline void insert(int &now,int pre,int l,int r,int i) 59 { 60 if(!now||now==pre)now=++tot,t[now]=t[pre]; 61 if(l==r){Add(T+now,i,INF);if(pre)Add(T+now,T+pre,INF);return;} 62 int mid=(l+r)>>1; 63 if(A[i]<=mid)insert(t[now].lc,t[pre].lc,l,mid,i); 64 else insert(t[now].rc,t[pre].rc,mid+1,r,i); 65 if(t[now].lc)Add(T+now,T+t[now].lc,INF); 66 if(t[now].rc)Add(T+now,T+t[now].rc,INF); 67 } 68 69 inline bool bfs() 70 { 71 memset(h,-1,sizeof h);h[S]=0; 72 queue<int>Q;Q.push(S); 73 while(!Q.empty()) 74 { 75 int u=Q.front();Q.pop(); 76 for(int i=fir[u];i;i=nxt[i]) 77 if(cap[i]&&!~h[to[i]]) 78 h[to[i]]=h[u]+1,Q.push(to[i]); 79 } 80 return ~h[T]; 81 } 82 83 inline int dfs(int u,int flow) 84 { 85 int used=0; 86 if(u==T)return flow; 87 for(int i=fir[u];i;i=nxt[i]) 88 if(cap[i]&&h[to[i]]==h[u]+1) 89 { 90 int w=flow-used; 91 w=dfs(to[i],min(w,cap[i])); 92 cap[i]-=w,cap[opst(i)]+=w,used+=w; 93 if(used==flow)return flow; 94 } 95 if(!used)h[u]=-1; 96 return used; 97 } 98 99 inline void dinic() 100 {while(bfs())maxflow+=dfs(S,INF);} 101 102 int main() 103 { 104 n=getint(); 105 for(int i=1;i<=n;i++) 106 { 107 A[i]=getint(),ans+=B[i]=getint(),ans+=W[i]=getint(); 108 L[i]=getint(),R[i]=getint(),P[i]=getint(); 109 Q[++N]=A[i],Q[++N]=L[i],Q[++N]=R[i]; 110 } 111 sort(Q+1,Q+N+1),N=unique(Q+1,Q+N+1)-(Q+1); 112 T=2*n+1; 113 for(int i=1;i<=n;i++) 114 { 115 A[i]=find(A[i]); 116 L[i]=find(L[i]); 117 R[i]=find(R[i]); 118 Add(S,i,B[i]),Add(i,T,W[i]),Add(i,i+n,P[i]); 119 } 120 for(int i=1;i<=n;i++) 121 { 122 if(i>1)Link(rt[i-1],1,N,i); 123 insert(rt[i],rt[i-1],1,N,i); 124 } 125 dinic(); 126 printf("%d\n",ans-maxflow); 127 }