Luogu

LOJ

分析

因为 IP 地址可以看做长度为 $32$ 的二进制串，所以可以考虑用 Trie 树维护。

考虑查询。可以发现一个 IP 地址的匹配最大明确度是单增的，因此求出链上修改时间的单调栈即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X;
}

const int N=1000000+10;

int ch[N*32][2],tim[N*32],tot=1;
int sta[40],top;
void insert(ll S,int l,int t) {
    int u=1;
    for (int i=31;32-i<=l;--i) {
        int w=(S>>i)&1;
        if (!ch[u][w]) ch[u][w]=++tot;
        u=ch[u][w];
    }
    tim[u]=t;
}
int query(ll S,int l,int r) {
    top=0; int u=1;
    for (int i=31;~i;--i) {
        int w=(S>>i)&1;
        if (!ch[u][w]) break;
        u=ch[u][w];
        if (tim[u]) {
            while (top&&tim[u]<sta[top]) --top;
            sta[++top]=tim[u];
        }
    }
    int res=0;
    for (int i=1;i<=top;++i) res+=(sta[i]>=l)&&(sta[i]<=r);
    return res;
}

int main() {
    int m=read();
    for (int cnt=0;m;--m) {
        char op[4]; scanf("%s",op);
        if (op[0]=='A') {
            ll S=(read()<<24)|(read()<<16)|(read()<<8)|read();
            insert(S,read(),++cnt);
        } else {
            ll S=(read()<<24)|(read()<<16)|(read()<<8)|read();
            int l=read(),r=read();
            printf("%d\n",query(S,l,r));
        }
    }
    return 0;
}