网站开发语言汇总,郑州百度搜索优化,广点通,做图题目大意#xff1a; 给一棵树#xff0c;每次激活或熄灭一个点#xff0c;每次问这些点都联通起来所需的最小总边权 分析#xff1a; 若根据dfs序给所有点排序#xff0c;为$v1,v2,v3....vk$#xff0c;那么答案就是$(dis(v1,v2)dis(v2,v3)...dis(vk-1,vk)dis(vk,v1))/2…题目大意 给一棵树每次激活或熄灭一个点每次问这些点都联通起来所需的最小总边权 分析 若根据dfs序给所有点排序为$v1,v2,v3....vk$那么答案就是$(dis(v1,v2)dis(v2,v3)...dis(vk-1,vk)dis(vk,v1))/2$ 只需要动态的维护这个序列每次拿出前后两个点后用lca修改答案即可 这道题主要是想学习一下set在这方面的使用 毕竟现在开O2的题比比皆是要是能少写个平衡树岂不美哉我也不会写233 我们就默认使用的是c11的标准吧 如何为set重载运算符 首先你要有一个结构体并在里面重载一个bool类型的函数先这样这里以将数字按d数组的大小排序为例 struct cmp{bool operator () (const int a,const int b){return d[a]d[b];}}; 接下来这样声明set setint,cmpS; 如何查找一个元素的前驱后继等 我们这里声明迭代器时使用c11特有的auto用法看起来方便不少setint::iterator) 这里以查找x的前驱后继为例循环式的即若x为最后一个数后继就是第一个数反过来同理 auto itS.lower_bound(x),ait,bit;
int l(itS.begin()?*--S.end():*--a);
int r(it--S.end()?*S.begin():*b); 注意这里end()函数返回的是个超尾所以要-- 这里我们看到迭代器的移动用加减即可取值时用*即可 插入删除 insert和erase千万别记错了 S.insert(x);
S.erase(x); 接下来放上这道题的代码 1 #includebits/stdc.h2 #define N 1000053 #define ll long long4 using namespace std;5 int n,q;6 int h[N],to[2*N],nxt[2*N],w[2*N],etop;7 void add(int a,int b,int c){to[etop]b,nxt[etop]h[a],w[etop]c,h[a]etop;}8 int fa[N][20],d[N],tot,dep[N];9 ll len[N][20];
10 void dfs(int u){
11 d[u]tot;
12 for(int i1;i17;i){
13 fa[u][i]fa[fa[u][i-1]][i-1];
14 len[u][i]len[u][i-1]len[fa[u][i-1]][i-1];
15 if(fa[u][i]0)break;
16 }
17 for(int kh[u],vto[k];k;knxt[k],vto[k])
18 if(v!fa[u][0]){
19 fa[v][0]u;len[v][0]w[k];
20 dep[v]dep[u]1;
21 dfs(v);
22 }
23 }
24 ll LCA(int x,int y){
25 ll ans0;
26 if(dep[x]dep[y])swap(x,y);
27 for(int i17;i0;i--)
28 if(fa[x][i]dep[fa[x][i]]dep[y]){
29 anslen[x][i];
30 xfa[x][i];
31 }
32 if(xy)return ans;
33 for(int i17;i0;i--)
34 if(fa[x][i]!fa[y][i]){
35 anslen[x][i];
36 anslen[y][i];
37 xfa[x][i];
38 yfa[y][i];
39 }
40 anslen[x][0];
41 anslen[y][0];
42 return ans;
43 }
44 struct cmp{bool operator () (const int a,const int b){return d[a]d[b];}};
45 setint,cmpS;
46 ll ans;
47 void ins(int x){
48 S.insert(x);
49 auto itS.lower_bound(x),ait,bit;
50 int l(itS.begin()?*--S.end():*--a);
51 int r(it--S.end()?*S.begin():*b);
52 ans-LCA(l,r);
53 ansLCA(l,x);
54 ansLCA(x,r);
55 }
56 void del(int x){
57 auto itS.lower_bound(x),ait,bit;
58 int l(itS.begin()?*--S.end():*--a);
59 int r(it--S.end()?*S.begin():*b);
60 ansLCA(l,r);
61 ans-LCA(l,x);
62 ans-LCA(x,r);
63 S.erase(x);
64 }
65 char o[2];
66 int main(){
67 scanf(%d,n);
68 for(int i1,a,b,c;in;i){
69 scanf(%d%d%d,a,b,c);
70 add(a,b,c),add(b,a,c);
71 }
72 dfs(1);
73 scanf(%d,q);
74 while(q--){
75 scanf(%s,o);
76 if(o[0]?)coutans/2endl;
77 else{
78 int x;scanf(%d,x);
79 if(o[0])ins(x);
80 else del(x);
81 }
82 }
83 return 0;
84 } View Code 2019.6.18 update 今天在写一个扫描线题时使用上面的方法重置set的比较符出现了问题使用lower_bound会在大数据下WA掉但upper_bound则没问题 如果使用常规的重载运算符的话则两种方式都没问题……蒙圈ing 这里给个当时的两种比较函数吧 这是出了问题的 struct cmp{bool operator () (const hu A,const hu B){double asA.ysqrt(A.r*A.r-(A.x-X)*(A.x-X))*(1.0*A.u);double bsB.ysqrt(B.r*B.r-(B.x-X)*(B.x-X))*(1.0*B.u);if(asepsbsbsepsas)return A.uB.u;else return asbs;}
}; 这个是改成重载运算符的 bool operator (const hu A,const hu B){double asA.ysqrt(A.r*A.r-(A.x-X)*(A.x-X))*(1.0*A.u);double bsB.ysqrt(B.r*B.r-(B.x-X)*(B.x-X))*(1.0*B.u);if(asepsbsbsepsas)return A.uB.u;else return asbs;
} 如果哪位大神路过希望能指点一下555´дゞ 还有NOI没有C11 所以跟我一起拼一遍 iterator 再来3遍 iterator iterator iterator ojbk! 转载于:https://www.cnblogs.com/2017SSY/p/10948482.html
