已完成神秘基于值域算法解决高维偏序大学习
2026-07-06 15:41:08
发布于：广东
15阅读
0回复
0点赞
其实就是 ABC465F。
Difficulty：4.6 / Medium-
Tag：容斥原理
题意解析：给定你 个 元组 ，每个有一个权值， 次询问，每次询问给出两个 元组 ，问你满足对于所有 都满足 的 的权值之和。
。
显然，这是一个 维偏序问题。常规解法有 的 CDQ 套扫描线树状数组， 的 K-D Tree 和 的 bitset（存疑）。显然都很难通过。
注意到这题值域非常小。所以考虑复杂度基于值域的解法。
首先考虑不算 。
我们可以预处理出每种可能的 ，求出如果只考虑 的限制权值之和。查询时查表即可。
这一部分可以枚举子集，将某些 减一，然后容斥起来。
比如说计算 ，就可以通过 一共 种子集容斥起来计算。有些 包含 ，不需要把含 的那几位减一。
然后考虑算 。
如果有 ，显然答案为 。考虑所有 的情况。
显然，依旧可以容斥。我们可以枚举 元组 共 种，分别求出 的权值之和，然后容斥计算。显然可以查上面的表。
朴素枚举每一位可以做到 ，精细化实现可以省掉一个 。具体见代码。ATCoder 官方使用了一种更巧妙的实现方法，做到了 预处理。我不会，所以就不写了。
namespace cjdst{
const int N = 1000000, M = 6;
ll pre[N + 5];
int ksm[]{1, 10, 100, 1000, 10000, 100000};
int dabiao[N + 5][(1 << M) + 5];
short zero[N + 5];
void solve(){
int n;
std::cin >> n;
for(int i = 1; i <= n; i++){
int x, y;
std::cin >> x >> y;
pre[x] += y;
}
for(int i = 0; i < N; i++){
for(short j = 1; j < (1 << M); j++){
register int lg = std::__lg(j & (-j));
dabiao[i][j] = dabiao[i][j & (j - 1)] + ksm[lg] * (i / ksm[lg] % 10);
}
}
register char popcount[(1 << M)]{};
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(i / ksm[j] % 10 == 0) zero[i] |= (1 << j);
}
}
for(int i = 0; i < (1 << M); i++){
popcount[i] = popcount[i >> 1] + (i & 1);
}
for(int i = 0; i < N; i++){
for(short j = 1; j < (1 << M); j++){
if(zero[i] & j) continue;
int cur = i - dabiao[111111][j];
pre[i] += pre[cur] * (popcount[j] % 2 ? 1 : -1);
}
}
int q;
std::cin >> q;
while(q--){
int x, y;
std::cin >> x >> y;
ll ans = 0;
bool flag = 0;
for(int i = 0; i < M; i++){
if(x / ksm[i] % 10 > y / ksm[i] % 10){
std::cout << "0\n";
flag = 1;
break;
}
}
if(flag) continue;
for(short i = 0; i < (1 << M); i++){
if(zero[x] & i) continue;
int cur = y - dabiao[y][i] + dabiao[x - 111111 + dabiao[111111][zero[x]]][i];
ans += pre[cur] * (popcount[i] % 2 ? -1 : 1);
}
std::cout << ans << '\n';
}
}
}
时间复杂度：。
有帮助，赞一个