NKOJ 3615(CQOI 2016) 路由表（trie）

发表于 |
字数统计: 890字 | 阅读时长 ≈ 4min

P3615【CQOI2016 Day2】路由表

问题描述
这里写图片描述

输入格式

第一行，一个整数n，表示操作次数。
接下来n行，每行描述一次操作，操作有两种：
A D/L
其中D为一个IP地址，L为整数(1<=L<=32)。添加一条表项至路由表，其目的地址为D，掩码长度为L。下一条地址由于没有用到，故省略。
Q D a b
其中，D为一个IP地址，a、b为正整数(a<=b).查询从第a到第b次调价表项期间（含a,b）,目的地址D的路由表项选择发生了多少次变化。保证查询时表中至少有b个表项目

输出格式

若干行，每行一个整数，表示对应查询操作

样例输入

11
A 0.0.0.0/8
Q 1.2.3.4 1 1
A 1.0.0.0/9
A 1.128.0.0/10
A 1.0.0.0/10
A 1.0.0.0/8
Q 1.2.3.4 1 5
A 1.2.0.0/16
A 1.2.3.1/32
Q 1.2.3.4 5 7
Q 1.2.3.1 5 7

样例输出

0
2
1
2

提示

对于一次查询的一种理解方式是：无视其它所有查询操作，只看添加操作。先清空路由表，然后执行第1到a-1次添加操作。之后再统计第a到b次添加操作过程中，统计匹配改变的次数。
设一条表项的掩码长度为L，数据保证将目的地址转为二进制串后，末尾的32-L位均为0

数据范围：n<=$10^5$

此题只需要将IP转化为一个字符串后添加入一个trie中，每次查询时暴力匹配，将1到b次添加操作之间的串拿出来，按照操作顺序排序，然后按题目要求搞就行了。由于要求改变量，所以必须知道1-a-1次操作后的情况。

附上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{int son[2],num,len;}trie[5000000],A[123456];
int tot=1,rt=1,cnt;
char s[45];
bool cmp(node a,node b)
{return a.num<b.num;}
void CHA(int l,int x)
{
	for(int i=7;i>=0;i--)
	s[++l]=(1&(x>>i))+48;
}
void TRA(int a,int b,int c,int d)
{
	CHA(0,a);
	CHA(8,b);
	CHA(16,c);
	CHA(24,d);
}
void Ins(int L,int k)
{
	int p=1,i,c;
	for(i=1;i<=L;i++)
	{
		c=s[i]-48;
		if(!trie[p].son[c])trie[p].son[c]=++tot;
		p=trie[p].son[c];
	}
	trie[p].num=k;
	trie[p].len=L;
}
void Find(int L,int b)
{
	int p=1,i,c;
	for(i=1;i<=L;i++)
	{
		c=s[i]-48;
		if(!trie[p].son[c])return;
		p=trie[p].son[c];
		if(trie[p].num<=b&&trie[p].num)
		{
			cnt++;
			A[cnt].num=trie[p].num;
			A[cnt].len=trie[p].len;
		}
	}
}
void ADD(int k)
{
	int a,b,c,d,l;
	scanf("%d.%d.%d.%d/%d",&a,&b,&c,&d,&l);
	TRA(a,b,c,d);Ins(l,k);
}
void Solve()
{
	int i,a,b,c,d,l,r,k=0,ans=0;cnt=0;
	scanf("%d.%d.%d.%d%d%d",&a,&b,&c,&d,&l,&r);
	TRA(a,b,c,d);Find(32,r);
	if(cnt==0){puts("0");return;}
	sort(A+1,A+cnt+1,cmp);
	for(i=1;i<=cnt;i++)
	if(A[i].len>k)
	{
	    k=A[i].len;
		if(A[i].num>=l)ans++;
	}
	printf("%d\n",ans);
}
int main()
{
	int i,k=0,n;char a;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		a=getchar();
		while(a!='A'&&a!='Q')a=getchar();
		if(a=='A')ADD(++k);
		else Solve();
	}
}