一般的に知られている \(p_1\sim p_k\) 展開する準備ができています \(e_1 \sim e_k\)複雑 \(O(k^2)\)。
これは NTT 分割統治を使用して実行できます。 \(O(k \log^2 k)\)GFを使用して多項式を当てはめる \(\exp\) それをしてください \(O(k \log k)\)。これらのテクノロジはこの記事の範囲を超えているため、省略されています。
これは魔法のアプリケーションです。この方法は Xueshengyi から来ています。
維持する \(n\) コレクション \(S_1\sim S_n\)、サポート \(q\) 操作:
与えられた \(l,r,x\)、右 \(私は\中 [l,r]\) 作る \(S_i \gets S_i \cup \ \le k\)。操作前に必ず確認してください \(x\) 含まれていません。
与えられた \(l,r,x\)、右 \(私は\中 [l,r]\) 作る \(S_i \gets S_i \setminus\S_u\)。操作前に必ず確認してください \(x\) が含まれています。
与えられた \(u,v\)、判定 \(S_u\) そして \(S_v\) 包含関係が保証するもの \(\textcolor\left-\)。
具体的には、次のように決定する必要があります。 \(S_u =S_v\) または \(S_u \subsetneq S_v\) または \(S_v \subsetneq S_u\) またはその他。
\(n,q \le 2 \times 10^6\)、\(k \le 30\)、そして \(n \times k,q \times k \le 6 \times 10^6\)6秒、1024MB。
大きな素数を取る \(p=2^{61}-1\) 存在する \(\mathbb{Z}_p\) 中程度の動作。ペアのセット \(S\)べき乗と \(H_i(S)=\sum \limits_{x \in S} h^i(x)\) ハッシュ値として。要素のハッシュ \(h\) はい \(U\to \mathbb{Z}_{p}\) ランダムなマッピング。
作る \(k=n+1\) ニュートンの恒等式に代入すると、次のようになります。
\[p_{n+1}=\sum_{i=1}^{n} (-1)^{i-1} e_ip_{n+1-i}
\]
上の式は次のようになります。 \(p_1 \sim p_{n+1}\) はい \(n\) 数のべき乗の和の必要条件。
設定してもいいかもしれません \(S_v \サブセット S_u\)差分セットハッシュ
\[\begin{aligned}
H_i(S_u \setminus S_v)&=H_i(S_u)-H_i(S_v)\\
&=\sum _{x \in S_u \setminus S_v} h^i(x)
\end{aligned}
\]
でなければなりません \(|S_u|-|S_v|\) 数値のべき乗の合計はニュートンの同一性テストに合格できます。逆に、ハッシュの差は、肯定的な項目の数から否定的な項目の数を引いたものにすぎず、テストに失敗する可能性が高くなります。
実際の検査中に私たちは主張しました \(p_1 \sim p_{n+1}\) はべき乗の和であり、推定できます \(e_1\はい e_n\) 数式を入力することで後から確認することもできます。データ構造を使用して保守するだけです \(k+1\) 力の合計。
開ける \(k+1\) 差分ツリー配列。間隔と単一点のクエリをサポートします。シンプルな実装 \(O(qk \log n+qk^2)\),多項式 \(\exp\) に最適化できます \(O(qk \log k)\)。
const int N = 2e6 + 5;
int n, q, k;
umap mp;
mint h(i64 x) {
if (mp.find(x) != mp.end()) return mp[x];
return mp[x] = rand64();
}
template
struct BIT {
mint *a;
void init() {
a = new mint[n + 5];
memset(a, 0, sizeof(mint) * (n+5));
}
void add(int x, mint c) {
for (; x <= n; x += lowbit(x)) a[x] += c;
}
void add(int l, int r, mint c) {
add(l, c), add(r+1, -c);
}
mint ask(int x) {
mint res = 0;
for (; x >= 1; x -= lowbit(x)) res += a[x];
return res;
}
};
BIT S;
BIT T[32];
mint inv[40], p[40], e[40];
bool check(int x, int y, int n) {
// y is subset of x
for (int i = 1; i <= n+1; i++)
p[i] = T[i].ask(x) - T[i].ask(y);
fill(e + 1, e + n + 2, 0), e[0] = 1;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= k; i++) {
if (i & 1) e[k] += e[k-i] * p[i];
else e[k] -= e[k-i] * p[i];
}
e[k] *= inv[k];
}
mint res = 0;
for (int i = 1; i <= n; i++)
if (i & 1) res += e[i] * p[n+1-i];
else res -= e[i] * p[n+1-i];
return res == p[n+1];
}
void _main() {
cin >> n >> q >> k; S.init();
for (int i = 1; i <= k+1; i++) inv[i] = ~mint(i), T[i].init();
for (i64 op, l, r, x, y; q--; ) {
cin >> op;
if (op == 1) {
cin >> l >> r >> x;
S.add(l, r, 1);
mint h0 = h(x), hi = h0;
for (int i = 1; i <= k+1; i++, hi *= h0)
T[i].add(l, r, hi);
} else if (op == 2) {
cin >> l >> r >> x;
S.add(l, r, -1);
mint h0 = h(x), hi = h0;
for (int i = 1; i <= k+1; i++, hi *= h0)
T[i].add(l, r, -hi);
} else {
cin >> x >> y;
int w = 4, s1 = S.ask(x), s2 = S.ask(y);
if (s1 == s2 && T[1].ask(x) == T[1].ask(y)) w = 3;
else if (s1 < s2 && check(y, x, s2 - s1)) w = 2;
else if (s1 > s2 && check(x, y, s1 - s2)) w = 1;
cout << w << '\n';
}
}
}
