题意：
有n个方块，m 1个限制条件1，m 2个限制条件2，限制条件的描述如下：
1 : l , r , k表示区间[ l , r ]染色的方块数至少k个
2 : l , r , k表示除区间[ l , r ]染色的方块数至少k 个
思路：
如果只有条件1 11的话就是A B C 216的G了（传送门）
当时有贪心跟差分约束两种解法，但是加了条件2的话，就只能差分约束了。
先把条件都列出来，设s u m i
表示[ 1 , i ]中染色的方块数。
对于条件1 11的约束有：
sumr−suml−1>=k
移项变成了s u m l − 1 − s u m r > = k − s u m
由于这个式子有三个变量，可以考虑二分s u m n，即二分染色的总方块数。
因为每个限制条件都是至少为k，所以答案是具有单调性的，如果说染色x个可以，染色x + 1个也一定满足条件。
还有一些合理性的约束：
0<=sumi−sumi−1<=1m i d < = s u m n − s u m，这个是为了保证s u m n − s u m 0 = = m i d 的。
建图，想跑最短路的话，松弛条件为d i s v < = d i s u + w，建边从u − > v，权值为w，也就是d i s v − d i s u < = w，后者向前者连边。
具体做法，二分染色的总方块数，每次c h e c k的时候，建图跑最短路，用s p f a判断有没有负环。
这样可能还是会TLE，加一个判断负环的小优化：如果在最短路过程中d i s i < 0就一定存在负环，因为在上面的连边过程中，从i − > i − 1有一条权值为0的边了。
最长路解法博客
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 6; #define debug(x) cout << #x << ":" << x << endl; #define mst(x, a) memset(x, a, sizeof(x)) #define rep(i, a, b) for (int i = (a); i <= (b); ++i) int n,m1,m2,S,T; struct Node{ int l,r,k,op; }; vector<Node>Q; vector< pair<int,int> >e[maxn]; int vis[maxn],d[maxn],dist[maxn]; int spfa(int S) { int flag=0; queue<int>q; q.push(S); while(q.size()) { int fr = q.front(); q.pop(); vis[fr] =0 ; if(flag) break; for(auto frr:e[fr]) { int v = frr.first; int w = frr.second; if(dist[v]>dist[fr]+w) { dist[v] = dist[fr] + w; if(vis[v]==0) vis[v] = 1,q.push(v),d[v]++; if(d[v]>n+1) { flag=1; break; } if(dist[v]<0) return 1; } } } return flag; } int ok(int mid) { rep(i,0,n) e[i].clear(),vis[i] =0 ,d[i] =0 ,dist[i] =1e9 ; dist[0] =0 ;vis[0]=1;d[0]=1; rep(i,1,n) { e[i-1].push_back({i,1}); e[i].push_back({i-1,0}); } for(Node fr:Q) { int l = fr.l; int r = fr.r; int op = fr.op; int k = fr.k; if(k>mid) return 0; if(op==1) { e[r].push_back({l-1,-k}); } else { int T = k - mid; e[l-1].push_back({r,-T}); } } e[0].push_back({n,mid}); e[n].push_back({0,-mid}); return (!spfa(S)); } int main() { int _;scanf("%d",&_); while (_--) { scanf("%d",&n); scanf("%d",&m1); scanf("%d",&m2); Q.clear(); S = 0; // T = n + 4; for(int i=1 ;i<=m1 ;i++) { int l,r,k;scanf("%d%d%d",&l,&r,&k); Q.push_back({l,r,k,1}); } for(int i=1 ;i<=m2 ;i++) { int l,r,k;scanf("%d%d%d",&l,&r,&k); Q.push_back({l,r,k,2}); } // cout<<"##"<<endl; //for(int i=0;i<=n;i++) cout<<ok(i)<<endl; int L = 0,R = n ,ans=-1; while(L<=R) { int mid = (L+R)>>1; if(ok(mid)) ans = mid,R = mid- 1; else L = mid + 1; } printf("%d\n",ans); } return 0; } /* */
