#1174633 (C++17) No.3608 Golden Steiner Tree

• 問題: No.3608 Golden Steiner Tree
• ユーザー: GOTKAKO
• 提出日時: 2026-08-01 01:53:36
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 330 ms / 3,000 ms
• コード長: 5,513 bytes
• コンパイル時間: 1,571 ms
• コンパイル使用メモリ: 236,060 KB
• 実行使用メモリ: 73,048 KB
• 最終ジャッジ日時: 2026-08-01 01:53:42
• 合計ジャッジ時間: 6,315 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 20

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct ST{int d,t;};
class SegmentTreeEuler{ //邪魔なので畳め.
    public:
    int siz = 1;
    vector<ST> dat;
 
    ST op(ST a, ST b){
        if(a.d < b.d) return a;
        else return b;
    }
    ST e(){return ST{1001001001,1001001001};}
    void renew (ST &a,ST x){a = x;}
 
    void make(int N){
        while(siz < N) siz *= 2;
        dat.resize(siz*2,e());
    }
 
    void make2(int N,vector<ST> &A){
        make(N);
        for(int i=0; i<N; i++){
            int pos = i+siz;
            dat.at(pos) = A.at(i);
        }
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
    }
 
    void update(int pos,ST x){
        pos = pos+siz;
        renew(dat.at(pos),x);
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
    }
 
    ST findans(int l, int r){
        ST retl = e(),retr = e();
        l += siz,r += siz;
        while(l < r){
            if(l&1) retl = op(retl,dat.at(l++));
            if(r&1) retr = op(dat.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
 
    ST get(int pos){return dat.at(pos+siz);}
    ST rangeans(int l, int r){return findans(l,r);}
    ST allrange(){return dat.at(1);}
};
using ET = long long;
class EulerTour{
    public:
    int siz = 0;
    vector<int> in,out,vert,edge;
    vector<ET> sumv,sume,A,dis;
    vector<ST> depth;
    SegmentTreeEuler DT;
    //SegmentTree Es,Vs;
 
    int tim = -1,dep = -1;
    ET nowd = 0;
 
    void make(int N,vector<vector<pair<int,long long>>> &G){
        siz = N;
        in.resize(N),out.resize(N),dis.resize(N);
        //A = B;
        dfs(0,-1,G);
        DT.make2(tim,depth);
        //Es.make2(tim,sume);
        //Vs.make2(tim,sumv);
    }
 
    void dfs(int pos,int back,vector<vector<pair<int,long long>>> &G){
        tim++; dep++;
        in.at(pos) = tim; dis.at(pos) = nowd;
        depth.push_back({dep,pos});
        //vert.push_back(pos); edge.push_back(pos);
 
        for(auto [to,w] : G.at(pos)){
            if(to == back) continue;
            //sume.push_back(w);
            nowd += w;  //sumv.push_back(A.at(to));
            dfs(to,pos,G);
            nowd -= w;  //sumv.push_back(-A.at(to));
            //sume.push_back(-w);
            //vert.push_back(pos); edge.push_back(-to);
            depth.push_back({dep,pos});
        }
 
        tim++; dep--;
        out.at(pos) = tim;
    }
 
    int LCA(int u,int v){
        int tu = in.at(u),tv = in.at(v);
        if(tu > tv) swap(tu,tv);
        auto[mind,ret] = DT.rangeans(tu,tv+1);
        return ret;
    }
 
    ET dist(int u,int v){
        int lca = LCA(u,v);
        return dis.at(u)+dis.at(v)-2*dis.at(lca);
    }
    //未完成 LCMと二点間距離のみ
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,R,B; cin >> N >> R >> B;
    vector<vector<pair<int,long long>>> Graph(N),Graph2(N);
    for(int i=1; i<=N; i++){
        double w = (1+sqrt(5))/2;
        int k = floor(i*w);
        if(i < k && k <= N){
            i--,k--;
            Graph.at(i).push_back({k,1});
            Graph.at(k).push_back({i,1});
            Graph2.at(i).push_back({k,0});
            Graph2.at(k).push_back({i,0});
            i++,k++;
        }
        w = pow(w,2);
        k = floor(i*w);
        if(i < k && k <= N){
            i--,k--;
            Graph.at(i).push_back({k,0});
            Graph.at(k).push_back({i,0});
            Graph2.at(i).push_back({k,1});
            Graph2.at(k).push_back({i,1});
            i++,k++;
        }
    }

    EulerTour Z1,Z2;
    Z1.make(N,Graph),Z2.make(N,Graph2);

    auto in = Z1.in;
    set<pair<int,int>> T;
    long long Rs = 0,Bs = 0;
    auto add = [&](int pos) -> void {
        int t = in.at(pos);
        if(T.size() > 1){
            auto itr = T.lower_bound({t,pos});
            auto itr2 = itr,itr3 = itr;
            if(itr != T.end()) itr3 = itr;
            else itr3 = T.begin();
            if(itr != T.begin()) itr2 = --itr;
            else itr2 = --T.end();
            
            auto [ign,pos2] = *itr2;
            auto [IGN,pos3] = *itr3;
            Rs += Z1.dist(pos,pos2)+Z1.dist(pos,pos3);
            Bs += Z2.dist(pos,pos2)+Z2.dist(pos,pos3);
            Rs -= Z1.dist(pos2,pos3),Bs -= Z2.dist(pos2,pos3);
        }
        else if(T.size() == 1){
            auto [ign,pos2] = *T.begin();
            Rs += Z1.dist(pos,pos2)*2,Bs += Z2.dist(pos,pos2)*2; 
        }
        T.insert({t,pos});
    };
    auto del = [&](int pos) -> void {
        int t = in.at(pos);
        T.erase({t,pos});
        if(T.size() <= 1){Rs = 0,Bs = 0; return;}
        auto itr = T.lower_bound({t,pos});
        auto itr2 = itr,itr3 = itr;
        if(itr != T.end()) itr3 = itr;
        else itr3 = T.begin();

        if(itr != T.begin()) itr2 = --itr;
        else itr2 = --T.end();

        auto [ign,pos2] = *itr2;
        auto [IGN,pos3] = *itr3;
        Rs -= Z1.dist(pos,pos2)+Z1.dist(pos,pos3);
        Bs -= Z2.dist(pos,pos2)+Z2.dist(pos,pos3);
        Rs += Z1.dist(pos2,pos3),Bs += Z2.dist(pos2,pos3);
    };
    
    int Q; cin >> Q;

    vector<bool> W(N);
    while(Q--){
        int t,x; cin >> t >> x;
        if(t == 1){
            x--;
            if(W.at(x)) W.at(x) = false,del(x);
            else W.at(x) = true,add(x);   
        }
        else if(t == 2) R = x;
        else B = x;
        cout << (Rs*R+Bs*B)/2 << "\n";
    }
}