[洛谷 5768,loj 2046][CQOI2016]路由表

题目链接

https://www.luogu.com.cn/problem/P5768

https://loj.ac/problem/2046

题解

本题容易看出是一个在 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;
}