「BJOI2016」IP地址 - 离线+trie树

题目大意

    路由表中每一项对应了一个形如1011101?????????????????????????的规则，会匹配指定的前缀为给定形式的 ip 。当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。
    每一个时刻，会有一条规则被加入，或者之前被加入的某条规则会过期。
    给一系列 ip，问每一个 ip 在一个给定的时间区间内匹配到的生效规则变了几次？
    例如，有一系列事件：

• Add 110
• Add 11
• Del 110
• Del 11
• Add 110

    那么,IP 地址11011101001001010101011101000010在这五个时刻之后匹配到的生效规则分别是：

• 110（第一条）
• 110（第一条）
• 11（第二条）
• 空
• 110（第三条）

    其中，在第二个事件后到第五个事件后的这段过程中，一共变了$3$次。

---

题目分析

将所有操作与询问离线下来。
对操作字符串建立trie树，并将询问差分后按照询问排序。
将询问字符串也放在trie树上，每次修改都给对应结束位置$i$打上标记，该结束位置的子树中所有结点都应有这个标记，但由于询问是由最长的前缀限制的，因此若子树中还有一个结束位置$j$，则$j$的子树中不应该有$i$的标记，限制一下标记下传即可。

故询问的答案即为询问串位置的历史标记个数。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=100005,maxt=4000005;

struct Trie {
	struct Tree {
		int ch[2],lazy,end;
	} tree[maxt];
	int cnt;
	Trie() {cnt=1;}
#define ls(now) tree[now].ch[0]
#define rs(now) tree[now].ch[1]
#define end(now) tree[now].end
#define lazy(now) tree[now].lazy
	void push_down(int now) {
		if(!ls(now))ls(now)=++cnt;
		if(!rs(now))rs(now)=++cnt;
		if(!end(ls(now)))lazy(ls(now))+=lazy(now);
		if(!end(rs(now)))lazy(rs(now))+=lazy(now);
		lazy(now)=0;
	}
	int insert(string s,int f) {
		int now=1;
		for(auto x:s) {
			push_down(now);
			now=tree[now].ch[x-'0'];
		}
		if(f)lazy(now)++,end(now)+=f;
		return lazy(now);
	}
} trie;

struct Modification {
	int opt;
	char s[35];
} a[maxn];

struct Query {
	int x,delta,id;
	char s[35];
	bool operator < (const Query& b) const {
		return x<b.x;
	}
} q[maxn<<1];

int n,m,cnt=0,ans[maxn];

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++) {
		char opt[5];
		scanf("%s%s",opt,a[i].s);
		a[i].opt=opt[0]=='A'?1:-1;
	}
	for(int i=1; i<=m; i++) {
		scanf("%s",q[++cnt].s);q[cnt].x=Get_Int();q[cnt].delta=-1;q[cnt].id=i;
		memcpy(q[cnt+1].s,q[cnt].s,sizeof(q[cnt].s));q[++cnt].x=Get_Int();q[cnt].delta=1;q[cnt].id=i;
	}
	sort(q+1,q+cnt+1);
	for(int i=1,j=1; i<=n; i++) {
		trie.insert(a[i].s,a[i].opt);
		for(; q[j].x==i; j++)ans[q[j].id]+=q[j].delta*trie.insert(q[j].s,0);
	}
	for(int i=1; i<=m; i++)printf("%d\n",ans[i]);
	return 0;
}