bzoj4628

4628: [BeiJing2016]IP地址

Time Limit: 20 Sec   Memory Limit: 256 MB Submit: 99   Solved: 22 [ Submit][ Status][ Discuss]

Description

路由表中每一项对应了一个形如 1011101?????????????????????????的规则，会匹配指定的前缀为给定形式的 ip 。 当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。每一个时刻，会有一 条规则被加入，或者之前被加入的某条规则会过期。给一系列 ip，问每一个 ip 在一个给定的时间区间内匹配到 的生效规则变了几次？ 例如，有一系列事件： Add 110 Add 11 Del 110 Del 11 Add 110 那么,IP 地址 11011101001001010101011101000010在这五个时刻之后匹配到 的生效规则分别是： 110（第一条）， 110（第一条）， 11（第二条）， 空， 110（第三条）。 其中，在第二个事件后到第五个事件后的这段过程中，一共变了3次。

Input

第一行两个整数 N 和 Q，表示时刻的个数与查询的个数。 接下来 N 行，每行描述一个事件。事件的格式是 Add s 表示新建一个规则，匹配前缀为 s 的所有 ip. Del s 表示把当前前缀 s 对应的规则删掉（过期）。保证之前有这样的一条规则还没被删。 接下来 Q 行，每行一个 ip 与两个整数 a,b，表示查询 ip 在第 a 个事件（从 1 开始数） 后到第 b 个事件后的这段时间里，这个 ip 匹配到的生效规则变化的次数。 ip 用01字符串来表示。 1 ≤ N, Q ≤ 10^5，串长不超过32

Output

对每个查询，输出所求的变化次数.

Sample Input

5 1 Add 110 Add 11 Del 110 Del 11 Add 110 11011101001001010101011101000010 2 5

Sample Output

3 题解： 去年省选就不会的题今年还是不会。。。 把所有操作离线，一个询问的答案是时间r的前缀改变次数减去时间l的前缀改变次数。 前缀改变次数就是时间从1到x时这个ip匹配的答案。 可以用trie树维护这个东西。 加入一个或删除一个前缀时，把trie树的节点打一个子树的lazy，表示整颗子树答案加1。 但是发lazy时如果发现这个子节点是一个当前时间可以匹配的前缀的话，向这个点发的lazy就不发了，并且删除这个lazy。因为这颗子树匹配的是这个子节点，不受子节点上边的加入或删除影响。 #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; //mem const int maxn = 101000; struct so { int t , i , f; } s[maxn*2]; struct trie { int lazy , f , s; int ch[4]; } p[maxn*70]; int top , tops; int n , m; char op[maxn][10] , str[maxn][35]; char z[maxn][35]; int l[maxn] , r[maxn]; int ans[maxn]; bool cmp ( so x1 , so x2 ) { return x1.t < x2.t; } void pushdown ( int id ) { if ( p[id].lazy ) { if ( !p[p[id].ch[0]].f ) { p[p[id].ch[0]].lazy += p[id].lazy; p[p[id].ch[0]].s += p[id].lazy; } if ( !p[p[id].ch[1]].f ) { p[p[id].ch[1]].lazy += p[id].lazy; p[p[id].ch[1]].s += p[id].lazy; } p[id].lazy = 0; } } void change ( int now ) { int kind , i , l , j; if ( op[now][1] == 'A' ) kind = 1; else kind = -1; l = strlen ( str[now] + 1 ); j = 1; //printf ( "%d %s\n" , l , str[now] ); for ( i = 1 ; i <= l ; i++ ) { if ( !p[j].ch[0] ) p[j].ch[0] = ++top; if ( !p[j].ch[1] ) p[j].ch[1] = ++top; pushdown ( j ); j = p[j].ch[str[now][i]-'0']; //printf ( " %d\n" , j ); } p[j].lazy++; p[j].s++; p[j].f += kind; } int query ( int now ) { int i , j = 1; for ( i = 1 ; i <= 32 ; i++ ) { if ( !p[j].ch[0] ) p[j].ch[0] = ++top; if ( !p[j].ch[1] ) p[j].ch[1] = ++top; pushdown ( j ); j = p[j].ch[z[now][i]-'0']; } return p[j].s; } void work () { int i , j; scanf ( "%d%d" , &n , &m ); for ( i = 1 ; i <= n ; i++ ) { scanf ( "%s%s" , op[i] + 1 , str[i] + 1 ); } for ( i = 1 ; i <= m ; i++ ) { scanf ( "%s%d%d" , z[i] + 1 , &l[i] , &r[i] ); s[++tops].f = -1; s[tops].i = i; s[tops].t = l[i]; s[++tops].f = 1; s[tops].i = i; s[tops].t = r[i]; } sort ( s + 1 , s + 1 + tops , cmp ); j = 1; top = 1; for ( i = 1 ; i <= tops ; i++ ) { while ( j <= s[i].t ) { change ( j ); j++; } ans[s[i].i] += query ( s[i].i ) * s[i].f; } for ( i = 1 ; i <= m ; i++ ) printf ( "%d\n" , ans[i] ); } int main () { work (); return 0; }