P5460 [BJOI2016]IP地址 Solution
我去
·
·
题解
P5460 [BJOI2016]IP地址 Solution
分析
$\bullet$ 规则的集合随着时间在改变，考虑对规则的集合建$0-1 Trie$树
$\bullet$ 询问一个$IP$地址在时间$[l+1,r]$（题目说的是“在第$a$个事件后”）内变化了多少次，可以转换为$[1,r]-[1,l]
$\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$标记就会被清空（不会对下面的点产生影响）**
## 代码
```cpp
#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;
}
```