这啥唐题。

考虑 $|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$ 次，刚好卡满。

:::success[代码]

#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;
}

:::