CF176E Archaeology（set用法提示）

題目大意：

給一棵樹，每次激活或熄滅一個點，每次問這些點都聯通起來所需的最小總邊權

分析：

若根據dfs序給所有點排序，為$v1,v2,v3....vk$，那么答案就是$(dis(v1,v2)+dis(v2,v3)+...+dis(vk-1,vk)+dis(vk,v1))/2$

只需要動態的維護這個序列，每次拿出前后兩個點后用lca修改答案即可

這道題主要是想學習一下set在這方面的使用

畢竟現在開O2的題比比皆是，要是能少寫個平衡樹豈不美哉（我也不會寫233

我們就默認使用的是c++11的標準吧

---

如何為set重載運算符

首先你要有一個結構體，并在里面重載一個bool類型的（）函數，先這樣（這里以將數字按d數組的大小排序為例）：

struct cmp{bool operator () (const int &a,const int &b){return d[a]<d[b];}};

接下來這樣聲明set：

set<int,cmp>S;

如何查找一個元素的前驅后繼等

我們這里聲明迭代器時使用c++11特有的auto用法，看起來方便不少（set<int>::iterator)

這里以查找x的前驅后繼為例（循環式的，即若x為最后一個數，后繼就是第一個數，反過來同理

auto it=S.lower_bound(x),a=it,b=it;
int l=(it==S.begin()?*--S.end():*--a);
int r=(it==--S.end()?*S.begin():*++b);

注意這里end()函數返回的是個超尾，所以要--

這里我們看到迭代器的移動用加減即可，取值時用*即可

插入刪除

insert和erase，千萬別記錯了

S.insert(x);
S.erase(x);

---

接下來放上這道題的代碼

#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
int n,q;
int h[N],to[2*N],nxt[2*N],w[2*N],etop;
void add(int a,int b,int c){to[++etop]=b,nxt[etop]=h[a],w[etop]=c,h[a]=etop;}
int fa[N][20],d[N],tot,dep[N];
ll len[N][20];
void dfs(int u){
    d[u]=++tot;
    for(int i=1;i<=17;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        len[u][i]=len[u][i-1]+len[fa[u][i-1]][i-1];
        if(fa[u][i]==0)break;
    }
    for(int k=h[u],v=to[k];k;k=nxt[k],v=to[k])
    if(v!=fa[u][0]){
        fa[v][0]=u;len[v][0]=w[k];
        dep[v]=dep[u]+1;
        dfs(v);
    }
}
ll LCA(int x,int y){
    ll ans=0;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=17;i>=0;i--)
    if(fa[x][i]&&dep[fa[x][i]]>=dep[y]){
        ans+=len[x][i];
        x=fa[x][i];
    }
    if(x==y)return ans;
    for(int i=17;i>=0;i--)
    if(fa[x][i]!=fa[y][i]){
        ans+=len[x][i];
        ans+=len[y][i];
        x=fa[x][i];
        y=fa[y][i];
    }
    ans+=len[x][0];
    ans+=len[y][0];
    return ans;
}
struct cmp{bool operator () (const int &a,const int &b){return d[a]<d[b];}};
set<int,cmp>S;
ll ans;
void ins(int x){
    S.insert(x);
    auto it=S.lower_bound(x),a=it,b=it;
    int l=(it==S.begin()?*--S.end():*--a);
    int r=(it==--S.end()?*S.begin():*++b);
    ans-=LCA(l,r);
    ans+=LCA(l,x);
    ans+=LCA(x,r);
}
void del(int x){
    auto it=S.lower_bound(x),a=it,b=it;
    int l=(it==S.begin()?*--S.end():*--a);
    int r=(it==--S.end()?*S.begin():*++b);
    ans+=LCA(l,r);
    ans-=LCA(l,x);
    ans-=LCA(x,r);
    S.erase(x);
}
char o[2];
int main(){
    scanf("%d",&n);
    for(int i=1,a,b,c;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(1);
    scanf("%d",&q);
    while(q--){
        scanf("%s",o);
        if(o[0]=='?')cout<<ans/2<<endl;
        else{
            int x;scanf("%d",&x);
            if(o[0]=='+')ins(x);
            else del(x);
        }
    }
    return 0;
}

?

---

2019.6.18 update

今天在寫一個掃描線題時使用上面的方法重置set的比較符出現了問題，使用lower_bound會在大數據下WA掉，但upper_bound則沒問題

如果使用常規的重載運算符的話則兩種方式都沒問題……（蒙圈ing

這里給個當時的兩種比較函數吧

這是出了問題的：

struct cmp{bool operator () (const hu &A,const hu &B){double as=A.y+sqrt(A.r*A.r-(A.x-X)*(A.x-X))*(1.0*A.u);double bs=B.y+sqrt(B.r*B.r-(B.x-X)*(B.x-X))*(1.0*B.u);if(as+eps>bs&&bs+eps>as)return A.u<B.u;else return as<bs;}
};

這個是改成重載運算符的：

bool operator < (const hu &A,const hu &B){double as=A.y+sqrt(A.r*A.r-(A.x-X)*(A.x-X))*(1.0*A.u);double bs=B.y+sqrt(B.r*B.r-(B.x-X)*(B.x-X))*(1.0*B.u);if(as+eps>bs&&bs+eps>as)return A.u<B.u;else return as<bs;
}

如果哪位大神路過希望能指點一下555（；′д｀）ゞ

?

還有NOI沒有C++11

所以跟我一起拼一遍

iterator

再來3遍

iterator

iterator

iterator

ojbk!

?