[BZOJ4628][BeiJing2016]IP地址可持久化线段树+字典树

2019-11-06 09:13:21

字体：大中小

来源：转载

供稿：网友

按深度建可持久化线段树

/************************************************************** PRoblem: 4628 User: di4CoveRy Language: C++ Result: Accepted Time:3556 ms Memory:259828 kb****************************************************************/#include <bits/stdc++.h>#define N 500050#define PB push_backusing namespace std;inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct Node{ int l,r,sum; }ans;Node id = (Node){-1,-1,-1};Node Operator+ (Node p1,Node p2) { return (Node){ p1.l , p2.r, p1.sum + p2.sum - (p1.r == p2.l)};}struct Monster{ int t,l,r; };int len,n,q,rt[N],o[N];char s[33];struct Segment_Tree{ #define mid ( (l + r) >> 1 ) #define L ls[t] #define R rs[t] Node tr[20*N]; int tot,ls[20*N],rs[20*N],ag[20*N],ll,rr,v; int new_node(int x) { ag[ ++tot ] = ag[x]; ls[tot] = ls[x] , rs[tot] = rs[x] , tr[tot] = tr[x]; return tot; } void push_down(int &t) { #define c ag[t] L = new_node(L) ,R = new_node(R); if (c == -1) return ; tr[L] = tr[R] = (Node){c,c,1}; ag[L] = ag[R] = c; c = -1; } Node build(int l,int r,int &t) { t = new_node(0); ag[t] = 0; return l == r ? tr[t] = (Node){0,0,1} : tr[t] = build(l,mid,ls[t]) + build(mid+1,r,rs[t]); } void update(int l,int r,int rta,int &rtb) { if (l > rr || r < ll) return ;// rtb = new_node(rta); if (l >= ll && r <= rr) return tr[rtb].l = tr[rtb].r = ag[rtb] = v , tr[rtb].sum = 1 , (void)0; push_down(rtb); update(l,mid,ls[rta],ls[rtb]); update(mid+1,r,rs[rta],rs[rtb]); tr[rtb] = tr[ ls[ rtb ] ] + tr[ rs[ rtb ] ]; } void query(int l,int r,int t) { if (l > rr || r < ll) return ; if (l >= ll && r <= rr) return ans = ans + tr[t] , (void)0; push_down(t); query(l,mid,ls[t]); query(mid+1,r,rs[t]); tr[t] = tr[L] + tr[R]; }}T;struct Trie{#define nex ( ch[p][ s[_]-'0' ] ? ch[p][ s[_]-'0' ] : ch[p][ s[_]-'0' ] = ++tot ) int ch[N][2],tot,dep[N]; vector<int> vis[N]; vector<Monster> que[N]; void add(int tme) { int p = 1; for (int _=1;_<=len;_++) p = nex; vis[p].PB(tme); } void q(Monster Q) { int p = 1; for (int _=1;_<=len;_++) if (ch[p][ s[_]-'0' ]) p = nex; else break; que[p].PB(Q); } void dfs() { for (int _=1;_<=tot;_++) if (vis[_].size()&1) vis[_].PB(n); } void fd(int a,int b) { rt[b] = T.new_node(rt[a]); for (int i=0;i<(int)vis[b].size();i+=2) { T.ll = vis[b][i]; T.rr = vis[b][i^1] ; T.v = dep[b] ; T.update(1,n,rt[a],rt[b]); } } void go() { T.build(1,n,rt[1]); for (int p=1;p<=tot;p++) for (int _=0;_<=1;_++) if (ch[p][_]) { dep[ ch[p][_] ] = dep[p]+1; fd(p,ch[p][_]); } for (int p=1;p<=tot;p++) for (int _=0;_<(int)que[p].size();_++) { Monster Q = que[p][_]; T.ll = Q.l , T.rr = Q.r , ans = id; T.query(1,n,rt[p]); o[ Q.t ] = ans.sum; }// for (int p=1;p<=tot;p++)// for (int i=0;i<(int)vis[p].size();i+=2)// printf("::debug %d %d %d/n",p,vis[p][i],vis[p][i^1]); }}trie;int main() { #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif n = read(); q = read(); trie.tot = 1; for (int _=1;_<=n;_++) { char cmd[10]; scanf("%s",cmd+1); int f = (cmd[1] == 'D'); scanf("%s",s+1) , len = strlen(s+1) , trie.add(_-f); } for (int _=1;_<=q;_++) { scanf("%s",s+1); len = strlen(s+1); trie.q((Monster){_,read(),read()}); } trie.vis[1].PB(1) , trie.vis[1].PB(n); trie.dfs(); trie.go(); for (int _=1;_<=q;_++) printf("%d/n",o[_]); return 0;}

上一篇：指针初始化注意事项

下一篇：从二叉树到八皇后问题