链接：https://www.nowcoder.net/acm/contest/71/E
来源：牛客网
题目描述
有一个长为 n 的数列 A，其中有 m 个限制条件，条件有两种：
1、对于区间 [l,r]，其区间元素按位或和等于 x
2、对于区间 [l,r]，其区间元素按位与和等于 x
求出一个数列 A，使得满足给定的 m 个条件，保证有解。
1、对于区间 [l,r]，其区间元素按位或和等于 x
2、对于区间 [l,r]，其区间元素按位与和等于 x
求出一个数列 A，使得满足给定的 m 个条件，保证有解。
输入描述:
输入第一行两个正整数 n,m，意义如上
接下来 m 行，每行四个整数 op,l,r,x，表示一组限制
op = 1 表示是限制 1，op = 2 表示是限制 2
输出描述:
输出仅一行，n 个整数 a
表示数列 A。要求 0 <= a
< 10
输入例子:
4 3
1 1 2 9
2 3 4 2
1 2 3 11
输出例子:
1 9 2 6
-->
示例1
输入
4 3
1 1 2 9
2 3 4 2
1 2 3 11
输出
1 9 2 6
备注:
1<=n,m<=10^5, 1<=l<=r<=n, 0<=x<2^20
题解
差分约束系统，剪枝。
每一位分开考虑，可以列出一系列不等式，只要求出一组可行解。
剪枝：
对于某些位置，在没有跑差分约束系统之前，就可以确定一定是$1$，也就是可以多增加一些不等式，形如$sum[i] - sum[0] >= x$，用来剪枝。
#include <bits/stdc++.h>
using namespace std; const int maxn = 1e5 + 10;
int n, m;
int op[maxn], L[maxn], R[maxn], x[maxn];
int h[maxn], v[maxn * 10], w[maxn * 10], nx[maxn * 10];
int sz;
int ans[maxn]; int dis[maxn], f[maxn];
int sum[maxn]; void init() {
for(int i = 0; i <= n; i ++) {
h[i] = -1;
sum[i] = 0;
}
sz = 0;
} void add(int a, int b, int c) {
//printf("%d -> %d : %d\n", a, b, -c);
v[sz] = b;
w[sz] = -c;
nx[sz] = h[a];
h[a] = sz ++;
} void spfa() {
queue<int> q;
for(int i = 0; i <= n; i ++) {
dis[i] = maxn;
f[i] = 0;
}
dis[0] = 0;
q.push(0);
f[0] = 1;
while(!q.empty()) {
int top = q.front();
q.pop();
f[top] = 0;
for(int i = h[top]; i != -1; i = nx[i]) {
if(dis[top] + w[i] < dis[v[i]]) {
dis[v[i]] = dis[top] + w[i];
if(f[v[i]] == 0) {
f[v[i]] = 1;
q.push(v[i]);
}
}
}
}
} int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d%d", &op[i], &L[i], &R[i], &x[i]);
}
for(int t = 0; t < 20; t ++) {
init();
// 0 <= sum[x] - sum[x - 1] <= 1
// ! sum[x] - sum[x - 1] >= 0
// ! sum[x - 1] - sum[x] >= -1
for(int i = 1; i <= n; i ++) {
add(i - 1, i, 0);
add(i, i - 1, -1);
}
for(int i = 1; i <= m; i ++) {
if(op[i] == 1) {
if(x[i] & (1 << t)) {
// [L, R] 至少有一个1
// sum[R] - sum[L - 1] >= 1
add(L[i] - 1, R[i], 1);
} else {
// [L, R] 全为0
// 0 <= sum[R] - sum[L - 1] <= 0
// ! sum[R] - sum[L - 1] >= 0
// ! sum[L - 1] - sum[R] >= 0
add(L[i] - 1, R[i], 0);
add(R[i], L[i] - 1, 0);
}
} else {
if(x[i] & (1 << t)) {
// [L, R] 全为1
// R - L + 1 <= sum[R] - sum[L - 1] <= R - L + 1
// ! sum[R] - sum[L - 1] >= R - L + 1
// ! sum[L - 1] - sum[R] >= -(R - L + 1)
add(L[i] - 1, R[i], R[i] - L[i] + 1);
add(R[i], L[i] - 1, -(R[i] - L[i] + 1));
sum[L[i]] ++;
sum[R[i] + 1] --;
} else {
// [L, R] 不全为1
// 0 <= sum[R] - sum[L - 1] <= R - L
// ! sum[R] - sum[L - 1] >= 0
// ! sum[L - 1] - sum[R] >= L - R
add(L[i] - 1, R[i], 0);
add(R[i], L[i] - 1, L[i] - R[i]);
}
}
}
for(int i = 1; i <= n; i ++) {
sum[i] += sum[i - 1];
}
for(int i = 1; i <= n; i ++) {
if(sum[i]) sum[i] = 1;
}
for(int i = 1; i <= n; i ++) {
sum[i] += sum[i - 1];
add(0, i, sum[i]);
}
spfa();
for(int i = 1; i <= n; i ++) {
dis[i] = -dis[i];
}
for(int i = n; i >= 1; i --) {
dis[i] = dis[i] - dis[i - 1];
}
for(int i = 1; i <= n; i ++) {
ans[i] = ans[i] + dis[i] * (1 << t);
}
}
for(int i = 1; i <= n; i ++) {
printf("%d", ans[i]);
if(i < n) printf(" ");
else printf("\n");
}
return 0;
} /*
v[j] - v[i] >= k, 问v[t] - v[s]最小值
建边 i -> j, 权值为k, s到t的最长路就是答案
*/