ToB企服应用市场:ToB评测及商务社交产业平台

标题: 动态开点线段树 [打印本页]

---

作者: 数据人与超自然意识    时间: 2024-7-28 12:30
标题: 动态开点线段树
标题链接
思路
        对于树的线路题目可以用树剖来分别成一段一段的一连区间，但由于只记录这些区间某个信仰的权值，而且只有单点修改，所以我们思量给每个信仰都开一个线段树，也就是开1e5个线段树（类似主席树的写法，开个root数组来记录每个线段树的根，然后布局体来存那些点和他们的信息，左右儿子），用每个线段树来维护各个信仰的区间和与区间最大值。

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. typedef long long ll;
5. typedef pair<int,int> pii;
6. const int inf=0x3f3f3f3f;
7. const int N=1e5+10;
8. const int mod=1e9+7;
9. #define fi first
10. #define se second
12. int n,q;
13. int w[N],c[N];
14. vector<int> e[N];
16. //树剖
17. int siz[N],dep[N],newid[N],newc[N],neww[N];
18. int treecut,son[N],fa[N],top[N];
20. void dfs(int x,int f){
21.         siz[x]=1;
22.         fa[x]=f;
23.         dep[x]=dep[f]+1;
24.         for(auto y:e[x]){
25.                 if(y==f)
26.                         continue;
27.                 dfs(y,x);
28.                 siz[x]+=siz[y];
29.                 if(siz[y]>siz[son[x]])
30.                         son[x]=y;
31.         }
32. }
34. void dfs(int x,int f,int id){
35.         newid[x]=++treecut;
36.         top[x]=id;//是用原节点x来记录top，因为top是在树在lca的，树上的信息都记录的x，treecut已经转化成链了
37.         newc[treecut]=c[x];//这些都是维护新下标的信息
38.         neww[treecut]=w[x];
39.         if(son[x]){
40.                 dfs(son[x],x,id);//仍然是id，表示这条重链的头都是id
41.         }
42.         for(auto y:e[x]){
43.                 if(y==f||y==son[x]) //重儿子不要再进
44.                         continue;
45.                 dfs(y,x,y);
46.         }
47. }
49. //线段树
50. int root[N],treecnt;
51. struct node{
52.         int l,r,maxx,sum;
53. }tree[N*20];
55. void pushup(int l,int r,int &k){
56.         int ls=tree[k].l,rs=tree[k].r;
57.         tree[k].maxx=max(tree[ls].maxx,tree[rs].maxx);
58.         tree[k].sum=tree[ls].sum+tree[rs].sum;
59. }
61. void modify(int l,int r,int &k,int x,int value){
62.         if(!k) k=++treecnt;//k是引用，为0表示为NULL，要创节点
63.         if(l==r){
64.                 tree[k].maxx=tree[k].sum=value;
65.                 return;
66.         }
67.         int mid=(l+r)>>1;
68.         if(x<=mid) modify(l,mid,tree[k].l,x,value);
69.         else modify(mid+1,r,tree[k].r,x,value);
70.         pushup(l,r,k);
71. }
73. int querysum(int l,int r,int &k,int x,int y){
74.         if(x<=l&&y>=r)
75.                 return tree[k].sum;
76.         int mid=(l+r)>>1;
77.         int res=0;
78.         if(x<=mid) res+=querysum(l,mid,tree[k].l,x,y);
79.         if(y>mid) res+=querysum(mid+1,r,tree[k].r,x,y);
80.         return res;
81. }
83. int querymax(int l,int r,int &k,int x,int y){
84.         if(x<=l&&y>=r)
85.                 return tree[k].maxx;
86.         int mid=(l+r)>>1;
87.         int res=0;
88.         if(x<=mid) res=max(res,querymax(l,mid,tree[k].l,x,y));
89.         if(y>mid) res=max(res,querymax(mid+1,r,tree[k].r,x,y));
90.         return res;
91. }
93. //lca
94. int cc;//表示lca的子树是哪个信仰子树
95. int lcasum(int a,int b){
96.         int res=0;
97.         while(top[a]!=top[b]){//不在同一重链
98.                 if(dep[top[a]]<dep[top[b]])//保证a所在链的dep要大
99.                         swap(a,b);
100.                 res+=querysum(1,n,root[cc],newid[top[a]],newid[a]);
101.                 a=fa[top[a]];//要fa来跳出这条链
102.         }
103.         if(newid[a]>newid[b])
104.                 swap(a,b);
105.         res+=querysum(1,n,root[cc],newid[a],newid[b]);
106.         return res;
107. }
109. int lcamax(int a,int b){
110.         int res=0;
111.         while(top[a]!=top[b]){
112.                 if(dep[top[a]]<dep[top[b]])
113.                         swap(a,b);
114.                 res=max(res,querymax(1,n,root[cc],newid[top[a]],newid[a]));
115.                 a=fa[top[a]];
116.         }
117.         if(newid[a]>newid[b])
118.                 swap(a,b);
119.         res=max(res,querymax(1,n,root[cc],newid[a],newid[b]));
120.         return res;
121. }
123. void solve(){
124.         cin>>n>>q;
125.         for(int i=1;i<=n;i++){
126.                 cin>>w[i]>>c[i];
127.         }
128.         for(int i=1;i<n;i++){
129.                 int a,b;cin>>a>>b;
130.                 e[a].push_back(b);
131.                 e[b].push_back(a);
132.         }
133.        
134.         dfs(1,0);
135.         dfs(1,0,1);
136.         for(int i=1;i<=n;i++){//全用新的了...
137.                 modify(1,n,root[newc[newid[i]]],newid[i],neww[newid[i]]);
138.         }
139.         while(q--){       
140.                 string s;
141.                 cin>>s;
142.                 int x,y;
143.                 cin>>x>>y;
144.                 cc=newc[newid[x]];//信仰
145.                 if(s=="CC"){
146.                         int t=querysum(1,n,root[newc[newid[x]]],newid[x],newid[x]);
147.                         modify(1,n,root[newc[newid[x]]],newid[x],0);
148.                         modify(1,n,root[y],newid[x],t);
149.                         newc[newid[x]]=y;//记得修改信仰
150.                 }
151.                 else if(s=="CW"){
152.                         modify(1,n,root[newc[newid[x]]],newid[x],y);
153.                         neww[newid[x]]=y;
154.                 }
155.                 else if(s=="QS"){
156.                         cout<<lcasum(x,y)<<endl;
157.                 }
158.                 else{
159.                         cout<<lcamax(x,y)<<endl;
160.                 }
161.         }
162. }
163. signed  main(){
164.         ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
165.         int t=1;
166.         //cin>>t;
167.         while(t--){
168.                 solve();
169.         }
170.         return 0;
171. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4