E - Problem E. Split The Tree HDU - 6504 （树状数组 | 莫队 查询区间内不同的数的个数）
题目链接：
E - Problem E. Split The Tree
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。题目大意：给你一个树，以及这棵树构成的边，允许你删除一条边，然后问你形成的两颗子树中不同的数的总和。
具体思路：首先对于莫队的话，我们将这棵树转换成dfs序。1 2 3 4 ，当前是有四个节点，然后我们保存每个节点为根时子树的dfs序范围，每一次删除一条边，当前分成了两棵子树，然后第一棵子树的范围是2~3，第二棵子树是1 4，我们具体计算的时候，先统一算出1 2 3 4 所有的不同的数的总的个数。然后查询2 3 区间的时候，总的区间减去2 3 这段区间里面的不同的数的个数，然后剩下的就变成1 4 的不同的数的个数，然后我们再开一个区间保存2 3 这段区间里面不同的数的个数。两个加起来就是去除当前边的总的子树中不同的数的总和。
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 const int maxn = 1e5 +100; 5 int n,tmp; 6 int val[maxn]; 7 int vistot[maxn],vispart[maxn]; 8 vector<int>Edge[maxn]; 9 int lt[maxn],rt[maxn],Hash[maxn]; 10 int dfsnum; 11 void init(int n){ 12 dfsnum=0; 13 for(int i=0;i<=n;i++){Edge[i].clear();} 14 memset(vistot,0,sizeof(vistot)); 15 memset(vispart,0,sizeof(vispart)); 16 } 17 void dfs(int u,int fa){ 18 lt[u]=++dfsnum; 19 Hash[dfsnum]=u; 20 for(int i=0;i<Edge[u].size();i++){ 21 int to=Edge[u][i]; 22 if(to==fa)continue; 23 dfs(to,u); 24 } 25 rt[u]=dfsnum; 26 } 27 struct node{ 28 int lt,rt,pos; 29 node(){} 30 node(int xx,int yy,int zz){lt=xx,rt=yy,pos=zz;} 31 bool friend operator < (node t1,node t2){ 32 if(t1.pos==t2.pos)return t1.rt<t2.rt; 33 return t1.pos<t2.pos; 34 } 35 }q[maxn]; 36 void update(int pos,int type,int &tot,int &part){ 37 int tmp=val[Hash[pos]]; 38 vispart[tmp]+=type; 39 if(vispart[tmp]==1&&type==1){part++;} 40 if(vispart[tmp]==0&&type==-1){part--;} 41 type*=-1; 42 vistot[tmp]+=type; 43 if(vistot[tmp]==1&&type==1){tot++;} 44 if(vistot[tmp]==0&&type==-1){tot--;} 45 } 46 int main(){ 47 while(~scanf("%d",&n)){ 48 init(n); 49 for(int i=2;i<=n;i++){ 50 scanf("%d",&tmp); 51 Edge[tmp].push_back(i); 52 } 53 int num=0; 54 for(int i=1;i<=n;i++){ 55 scanf("%d",&val[i]); 56 vistot[val[i]]++; 57 if(vistot[val[i]]==1)num++; 58 } 59 dfs(1,-1); 60 int block=(int)sqrt(n); 61 for(int i=1;i<=n;i++){ 62 q[i]=node(lt[i],rt[i],(lt[i]-1)/block+1); 63 } 64 sort(q+1,q+n+1); 65 int l=1,r=0,tot=num,part=0; 66 int maxx=0; 67 for(int i=1;i<=n;i++){ 68 while(l<q[i].lt)update(l,-1,tot,part),l++; 69 while(l>q[i].lt)l--,update(l,1,tot,part); 70 while(r<q[i].rt)r++,update(r,1,tot,part); 71 while(r>q[i].rt)update(r,-1,tot,part),r--; 72 maxx=max(maxx,tot+part); 73 } 74 printf("%d\n",maxx); 75 } 76 }
莫队
对于树状数组：我们将这个区间扩大一倍，1 2 3 4 5 6 7 8，这里的5 6 7 8 保存的值还是1 2 3 4 所对应的。不过就是在查询2 3 区间的时候，我们再查询4 5 这个区间就能够求出当前的答案了。
这样就能保证所求的区间是连续的了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 const int maxn = 2e5 +100; 5 int n,tmp; 6 vector<int>Edge[maxn]; 7 int val[maxn]; 8 int lt[maxn],rt[maxn]; 9 int dfsnum; 10 int Hash[maxn]; 11 int vis[maxn],ans[maxn]; 12 int tree[maxn]; 13 void init() 14 { 15 dfsnum=0; 16 for(int i=0;i<=n;i++){Edge[i].clear();} 17 } 18 void dfs(int u) 19 { 20 lt[u]=++dfsnum; 21 Hash[dfsnum]=Hash[dfsnum+n]=u; 22 for(int i=0; i<Edge[u].size(); i++) 23 { 24 int to=Edge[u][i]; 25 dfs(to); 26 } 27 rt[u]=dfsnum; 28 } 29 struct node 30 { 31 int lt,rt,id; 32 node() {} 33 node(int xx,int yy,int zz) 34 { 35 lt=xx,rt=yy,id=zz; 36 } 37 bool friend operator < (node t1,node t2) 38 { 39 if(t1.rt!=t2.rt) 40 return t1.rt<t2.rt; 41 return t1.lt<t2.lt; 42 } 43 } q[maxn]; 44 int lowbit(int t){ 45 return t&-t; 46 } 47 void add(int pos,int type) 48 { 49 while(pos<=2*n) 50 { 51 tree[pos]+=type; 52 pos+=lowbit(pos); 53 } 54 } 55 int ask(int pos) 56 { 57 int ans=0; 58 while(pos) 59 { 60 ans+=tree[pos]; 61 pos-=lowbit(pos); 62 } 63 return ans; 64 } 65 int main() 66 { 67 while(~scanf("%d",&n)) 68 { 69 int tmp; 70 init(); 71 for(int i=2; i<=n; i++) 72 { 73 scanf("%d",&tmp); 74 Edge[tmp].push_back(i); 75 } 76 for(int i=1; i<=n; i++) 77 { 78 scanf("%d",&val[i]); 79 val[i+n]=val[i]; 80 } 81 dfs(1); 82 for(int i=1; i<=2*n; i++) 83 { 84 vis[i]=0; 85 ans[i]=0; 86 tree[i]=0; 87 } 88 int tot=0; 89 for(int i=1; i<=n; i++) 90 { 91 if(lt[i]==1) 92 continue; 93 q[++tot]=node(lt[i],rt[i],i); 94 q[++tot]=node(rt[i]+1,lt[i]+n-1,i); 95 } 96 sort(q+1,q+tot+1); 97 int maxx=0,pre=1; 98 for(int i=1; i<=tot; i++) 99 { 100 for(int j=pre; j<=q[i].rt; j++) 101 { 102 int tmp=val[Hash[j]]; 103 if(vis[tmp]) 104 add(vis[tmp],-1); 105 vis[tmp]=j; 106 add(vis[tmp],1); 107 } 108 pre=q[i].rt+1; 109 ans[q[i].id]+=ask(q[i].rt)-ask(q[i].lt-1); 110 maxx=max(maxx,ans[q[i].id]); 111 } 112 printf("%d\n",maxx); 113 } 114 return 0; 115 }
树状数组
更多精彩
