暴力1:按照题意模拟即可,复杂度 \(O(32n^2)\),预计 30pts。
暴力2:将 IP 地址用 unsigned int
存下来,比较 \(a\),\(b\) 是否匹配就只需要用位运算 \(O(1)\) 判断即可,复杂度 \(O(n^2)\),预计 50pts。
正解:考虑将当前插入的所有 IP 地址建成一颗 01Trie,结尾打上标记。
对于每次询问,将路径上的所有标记存入一个维护单调递增序列的栈,二分 \(l\) 和 \(r\) 的位置并计算一下差值就行了。(信息量有些大......)
复杂度线性,预计 100pts。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5, N2 = 100 + 5;
int m, cnt = 0, tot = 1, nex[N][2], ed[N], st[N2];
void add(string t, int len, int id) { //建树
int cur = 1;
for (int i = 0; i < len; ++i) {
if (!nex[cur][t[i] - '0']) nex[cur][t[i] - '0'] = ++tot;
cur = nex[cur][t[i] - '0'];
}
ed[cur] = id;
}
void getans(string t, int l, int r) {
int cur = 1, tail = 0;
for (int i = 0; i < t.size(); ++i) {
if (nex[cur][t[i] - '0']) {
cur = nex[cur][t[i] - '0'];
if (ed[cur]) {
while (tail && st[tail] > ed[cur]) --tail;
st[++tail] = ed[cur];
}
} else break;
}
//二分l和r的位置
int p1 = lower_bound(st + 1, st + tail + 1, l) - st;
int p2 = upper_bound(st + 1, st + tail + 1, r) - st - 1;
cout << p2 - p1 + 1 << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> m;
for (int i = 1; i <= m; ++i) {
char op, c; cin >> op;
if (op == 'A') {
int x[6];
cin >> x[1] >> c >> x[2] >> c >> x[3] >> c >> x[4] >> c >> x[5];
string t = "";
for (int j = 1; j <= 4; ++j) {
for (int k = 7; k >= 0; --k) {
if ((1 << k) & x[j]) t.push_back('1');
else t.push_back('0');
}
}
add(t, x[5], ++cnt);
} else {
int x[6], l, r;
cin >> x[1] >> c >> x[2] >> c >> x[3] >> c >> x[4] >> l >> r;
string t = "";
for (int j = 1; j <= 4; ++j) {
for (int k = 7; k >= 0; --k) {
if ((1 << k) & x[j]) t.push_back('1');
else t.push_back('0');
}
}
getans(t, l, r);
}
}
return 0;
}