这啥唐题。
考虑 \(|S|=2\) 怎么做。把序列劈成左右两半，分别问两边，这样可以得到两个元素都在左半区间/右半区间的集合个数。还要计算一个在左半边，另一个在右半边的集合个数。容易想到把序列劈成 \(4\) 份，左半边有 \(2\) 个，右半边也有 \(2\) 个，从左右各选一个小区间拼在一起查询，然后再容斥减去两个元素都在小区间内的部分即可。
扩展到 \(|S|\in \{2,3\}\) 的情况。考虑把序列平均分成 \(6\) 份，查询从中任选 \(1/2/3\) 个小区间拼在一起的答案。这样会算重，需要容斥一下。从大到小考虑小区间个数 \(k\)：
- \(k=3\)：落在 \(3\) 个小区间内的集合会被恰好计算 \(1\) 次，容斥系数为 \(c_3=1\)。
- \(k=2\)：只落在 \(2\) 个小区间内的集合会在 \(k=3\) 时被计算 \(4\) 次（两个区间固定，剩下一个区间任选），因此 \(4c_3+c_2=1\)，解得 \(c_2=-3\)。
- \(k=1\)：只落在 \(1\) 个小区间内的集合会在 \(k=3\) 时被计算 \(\dbinom 52=10\) 次，在 \(k=2\) 时被计算 \(5\) 次，因此 \(10c_3+5c_2+c_1=1\)，解得 \(c_1=6\)。
询问次数为 \(\dbinom 61+\dbinom 62+\dbinom 63=41\) 次，刚好卡满。
代码
#include <bits/stdc++.h>using namespace std;int query(vector<int>);int solve(int N) {vector<int> vec[6];int q = N / 6, r = N % 6, cur = 0;for (int i = 0; i < 6; ++i) {int cnt = q + (i < r);for (int j = 0; j < cnt; ++j) vec[i].emplace_back(cur++);}int res = 0;for (int i = 0; i < 6; ++i)for (int j = i + 1; j < 6; ++j)for (int k = j + 1; k < 6; ++k) {vector<int> qr;for (int x : vec[i]) qr.emplace_back(x);for (int x : vec[j]) qr.emplace_back(x);for (int x : vec[k]) qr.emplace_back(x);res += query(qr);}for (int i = 0; i < 6; ++i)for (int j = i + 1; j < 6; ++j) {vector<int> qr;for (int x : vec[i]) qr.emplace_back(x);for (int x : vec[j]) qr.emplace_back(x);res -= query(qr) * 3;}for (int i = 0; i < 6; ++i) res += query(vec[i]) * 6;return res;
}