自动搬运

查看原文

来自洛谷，原作者为

	我去 rp=INF;

搬运于2025-08-24 22:10:59，当前版本为作者最后更新于2020-09-19 16:24:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P5460 [BJOI2016]IP地址 Solution

分析

$\bullet$ 由$IP$地址是$01$串，匹配的是$IP$地址的前缀不难想到用$0-1 Trie$树

$\bullet$ 规则的集合随着时间在改变，考虑对规则的集合建$0-1 Trie$树

$\bullet$ 询问一个$IP$地址在时间$[l+1,r]$（题目说的是“在第$a$个事件后”）内变化了多少次，可以转换为$[1,r]-[1,l]$

$\bullet$ 如果只询问一个$IP$地址，那么就非常的简单直接暴力统计即可，所以现在要考虑如何同时维护多个$IP$地址

$\bullet$ 考虑在什么情况下对规则进行修改（包括添加和删除）会影响某一个$IP$地址的答案

    $\circ$ 加入新的规则，新的规则比原来和某个$IP$地址匹配的规则更优

    $\circ$ 删除与某个$IP$地址已匹配的规则

$\bullet$ 再考虑修改一个规则会对哪些$IP$地址的答案产生影响

    $\circ$ 因为匹配的是最优的规则，所以如果规则$B$是规则$A$的一个前缀，那么对规则$B$进行修改将不会影响与规则$A$匹配的$IP$地址

    $\circ$ 如上图，粉色涂出来的$IP$地址可以与以$2$节点为结尾的规则以及以$5$节点为结尾的规则匹配，但匹配的是最优的，所以是与以$5$节点为结尾的规则匹配。

    $\circ$ 此时对以$2$节点为结尾的规则进行修改，发现受影响的$IP$地址只有以$2$节点结尾的,以$3$节点结尾的和以$4$节点结尾的$IP$地址。所以说修改一个规则会对以当前规则结尾与下一个规则结尾之间的点产生影响

    $\circ$ 如上图，修改$6$节点结尾的规则，将不会对粉色涂出来以$4$节点结尾的$IP$地址产生影响，只会对以$6$节点结尾的$IP$地址和以$7$节点结尾的$IP$地址产生影响

$\bullet$ 于是对于$Tire$树上的点，记录一个值$times$表示执行完当前（对规则的）操作以这个点结尾的$IP$地址将会被更改多少次，在记录一个懒标记$tag$表示对这个值的修改，这个标记遇到对规则结尾打上的$end$标记就会被清空（不会对下面的点产生影响）

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<iostream>
#include<vector>
using namespace std;

const int MAXN = 1e5+5;
const int root = 0;

template <typename T>
inline void read(T&x){
	x=0; char temp=getchar(); bool f=false;
	while(!isdigit(temp)){if(temp=='-') f=true; temp=getchar();}
	while(isdigit(temp)){x=(x<<1)+(x<<3)+temp-'0'; temp=getchar();}
	if(f) x=-x;
}
template <typename T>
void print(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

//basic
int n,q,opt[MAXN],ans[MAXN];
string str[MAXN];
struct Question{
	string ip; int id;
}ques[MAXN];
vector<int> del[MAXN],add[MAXN];

//Trie
struct node{
	int son[2],end,times,tag;
	inline void Update(int val){times+=val,tag+=val;}
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define end(x) t[x].end
#define times(x) t[x].times
#define tag(x) t[x].tag
}t[MAXN*32];
int cnt;

inline void Pushdown(int id){
	if(!ls(id)) ls(id)=++cnt;
	if(!rs(id)) rs(id)=++cnt;
	if(tag(id)==0) return;
	if(!end(ls(id))) t[ls(id)].Update(tag(id));
	if(!end(rs(id))) t[rs(id)].Update(tag(id));
	tag(id)=0;
}

inline void Modify(string s,int val){
	int now=root,len=s.length();
	for(register int i=0;i<len;i++){
		Pushdown(now);
		now=t[now].son[s[i]-'0'];
	}
	end(now)+=val,tag(now)++,times(now)++;
}

inline int Query(string s){
	int now=root,len=s.length();
	for(register int i=0;i<len;i++){
		Pushdown(now);
		now=t[now].son[s[i]-'0'];
	}
	return times(now);
}

int main(){
	read(n),read(q);
	for(register int i=1;i<=n;i++){
		char s[6]; scanf("%s",s),cin>>str[i];
		if(s[0]=='A') opt[i]=1;
		else opt[i]=-1;
	}
	for(register int i=1;i<=q;i++){
		cin>>ques[i].ip,ques[i].id=i;
		int l,r; read(l),read(r);
		del[l].push_back(i),add[r].push_back(i);
	}
	for(register int i=1;i<=n;i++){
		Modify(str[i],opt[i]);
		for(register int j=0,tmp=del[i].size();j<tmp;j++) ans[ques[del[i][j]].id]-=Query(ques[del[i][j]].ip);
		for(register int j=0,tmp=add[i].size();j<tmp;j++) ans[ques[add[i][j]].id]+=Query(ques[add[i][j]].ip);
	}
	for(register int i=1;i<=q;i++) print(ans[i]),puts("");
	return 0;
}