自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:14:12，当前版本为作者最后更新于2020-02-17 21:38:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题容易看出是一个在 Trie 树上的匹配问题。

对于每个添加操作，我们只需按题意将指定 ip 的前 $x$ 位插入即可（$x$ 位后面的内容显然没有意义），并在结束位置打一个标记 $ed$，表示这是第 $ed$ 条表项。

对于查询操作，题目最后的提示告诉我们可以差分。

也就是说一个查询 $[l,r]$ 可以变成两个查询 $[1,r]$ 和 $[1,l-1]$，最后把结果相减即可。

我们现在考虑如何解决一个 $[1,x]$ 类型的查询。

我们还是在 Trie 树上走，并用一个单调栈维护我们遇到的标记。每遇到一个有效标记（在查询范围内），就先将栈内时间比它靠后的标记弹出（这些标记都是无用的），再将该标记插入栈中。

最后结果就是栈内的元素数目。

#include <cstdio>
#include <stack>
using namespace std;
typedef unsigned ui;
struct trie
{
 struct node
 {
  int son[2],ed;
 }p[10000005];
 int tot=1,id=0;
 void insert(ui ip,int len)
 {
  int u=1;
  for(int i=31;32-i<=len;i--)
  {
   int v=(ip>>i)&1;
   if(p[u].son[v])u=p[u].son[v];
   else
   {
    p[u].son[v]=++tot;
    u=tot;
   }
  }
  p[u].ed=++id;
 }
 int query(ui ip,int t)
 {
  stack<int> s;
  int u=1,pos=31;
  while(1)
  {
   if(p[u].ed&&p[u].ed<=t)
   {
    int ed=p[u].ed;
    while(!s.empty()&&ed<s.top())
     s.pop();
    s.push(ed);
   }
   int v=(ip>>pos)&1;
   if(!p[u].son[v])break;
   else u=p[u].son[v];
   pos--;
  }
  return s.size();
 }
}tr;
char op[5];
ui getip()
{
 ui ip=0;
 int a,b,c,d;
 scanf("%d.%d.%d.%d/",&a,&b,&c,&d);
 ip=(ip<<8)+a,ip=(ip<<8)+b,ip=(ip<<8)+c,ip=(ip<<8)+d;
 return ip;
}
int main()
{
 int m;
 scanf("%d",&m);
 while(m--)
 {
  scanf("%s",op);
  if(op[0]=='A')
  {
   ui ip=getip();
   int len;
   scanf("%d",&len);
   tr.insert(ip,len);
  }
  else
  {
   ui ip=getip();
   int a,b;
   scanf("%d%d",&a,&b);
   printf("%d\n",tr.query(ip,b)-tr.query(ip,a-1));
  }
 }
 return 0;
}