結果

問題 No.1030 だんしんぐぱーりない
コンテスト
ユーザー ngtkana
提出日時 2020-04-18 00:27:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,454 bytes
コンパイル時間 2,865 ms
コンパイル使用メモリ 208,192 KB
最終ジャッジ日時 2025-01-09 20:57:05
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 1 WA * 25 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
using lint=long long;
using ld=long double;
template<class T>using numr=std::numeric_limits<T>;
void cmn(lint&x,lint y){if(x>y)x=y;}
void cmx(lint&x,lint y){if(x<y)x=y;}
template<class Value,class BinaryOp>struct segtree{ // {{{
    // member variables
    lint n,N;
    BinaryOp op;
    Value id;
    std::vector<Value>table;

    // constructors
    segtree()=default;
    segtree(lint n_, BinaryOp const& op_, Value id_):
        n(n_),
        N(1ll<<(std::numeric_limits<lint>::digits-__builtin_clzll(n)+1)),
        op(op_),
        id(id_),
        table(2*N,id){}

    // other member functions
    void update(lint i){table.at(i)=op(table.at(2*i),table.at(2*i+1));}
    void set(lint i, Value const& x){i+=N;table.at(i)=x;for(i>>=1;i;i>>=1)update(i);}
    void lazy_set(lint i, Value const& x){table.at(i+N)=x;}
    void build(){for(lint i=N-1;i;i--)update(i);}

    Value get(lint i)const{return table.at(i+N);}
    Value query(lint l, lint r)const{
        Value ans=id;
        std::vector<lint>right;
        for(l+=N,r+=N;l<r;l>>=1,r>>=1){
            if(l&1)ans=op(ans,table.at(l++));
            if(r&1)right.push_back(--r);
        }
        std::reverse(ALL(right));
        for(lint x:right)ans=op(ans,table.at(x));
        return ans;
    }
    std::vector<Value>to_vec()const{
        std::vector<Value>ans(n);
        for(lint i=0;i<n;i++)ans.at(i)=table.at(N+i);
        return ans;
    }
}; // }}}
auto min_fn=[](auto&&x,auto&&y){return std::min(x,y);};
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint n,k,q;std::cin>>n>>k>>q;
    std::vector<lint>c(n),a(k);
    for(lint&x:c)std::cin>>x;
    for(lint&x:a){std::cin>>x;x--;}
    std::vector<std::vector<lint>>g(n);
    for(lint i=0;i<n-1;i++){
        lint u,v;std::cin>>u>>v;u--,v--;
        g.at(v).push_back(u);
    }
    lint N=4*n-2;
    auto eular=segtree(N,min_fn,std::pair(n,0));
    std::vector<std::pair<lint,lint>>pos(n);
    lint eular_sz=0;
    auto dfs=[&](auto&&f,lint x,lint d)->void{
        pos.at(x).first=eular_sz;
        eular.set(eular_sz++,std::pair(d,x));
        for(lint y:g.at(x)){
            eular.set(eular_sz++,std::pair(d,x));
            cmx(c.at(y),c.at(x));
            f(f,y,d+1);
            eular.set(eular_sz++,std::pair(d,x));
        }
        pos.at(x).second=eular_sz;
        eular.set(eular_sz++,std::pair(d,x));
    };
    dfs(dfs,0,0);
    auto lca=segtree(n,[&](lint x,lint y){return x==-1?y:y==-1?x:eular.query(pos.at(x).first,pos.at(y).second).second;},-1);
    for(lint i=0;i<k;i++)lca.lazy_set(i,a.at(i));
    lca.build();
    for(lint i=0;i<q;i++){
        lint com;std::cin>>com;
        if(com==1){
            lint x,y;std::cin>>x>>y;x--,y--;
            lca.set(x,y);
        }
        if(com==2){
            lint l,r;std::cin>>l>>r;l--;
            std::cout<<lca.query(l,r)+1<<'\n';
        }
    }
}
/*
 * 各頂点から根までのパスの最大値を DFS で前計算です。
 * あとは LCA をオイラーツアーで求めます。
 * クエリ平方分割です。
 * クエリ区間で変わらないようなもの全てについて、
 * オイラーツアー順を min / max セグ木に入れます。
 * すると、取得クエリはクエリ区間でのセグ木の結果に、追加のものも union すればよいです。
 */
0