結果

問題 No.1030 だんしんぐぱーりない
コンテスト
ユーザー ngtkana
提出日時 2020-04-17 23:59:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 788 ms / 2,000 ms
コード長 4,776 bytes
コンパイル時間 3,469 ms
コンパイル使用メモリ 217,552 KB
最終ジャッジ日時 2025-01-09 20:54:41
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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);
    std::vector<std::tuple<lint,lint,lint>>queries(q);
    for(lint i=0;i<q;i++){
        lint com;std::cin>>com;
        if(com==1){
            lint x,y;std::cin>>x>>y;x--,y--;
            queries.at(i)={1,x,y};
        }
        if(com==2){
            lint l,r;std::cin>>l>>r;l--;
            queries.at(i)={2,l,r};
        }
    }
    lint sq=std::sqrt(q);
    std::vector<std::vector<lint>>move(q/sq+1,std::vector<lint>(k));
    for(lint i=0;i<q;i++){
        if(std::get<0>(queries.at(i))==1){
            lint x,y;std::tie(std::ignore,x,y)=queries.at(i);
            move.at(i/sq).at(x)=true;
        }
    }
    for(lint i=0;i<=q/sq;i++){
        auto seg=segtree(
                k,
                [](auto&&p0,auto&&p1){return std::pair(std::min(p0.first,p1.first),std::max(p0.second,p1.second));},
                std::pair(N,0));
        for(lint j=0;j<k;j++){
            if(move.at(i).at(j))continue;
            seg.lazy_set(j,pos.at(a.at(j)));
        }
        seg.build();
        std::vector<lint>moving;
        for(lint j=0;j<k;j++){
            if(move.at(i).at(j))moving.push_back(j);
        }
        for(lint j=i*sq;j<std::min((i+1)*sq,q);j++){
            auto&&query=queries.at(j);
            if(std::get<0>(query)==1){
                lint x,y;std::tie(std::ignore,x,y)=query;
                a.at(x)=y;
            }
            if(std::get<0>(query)==2){
                lint l,r;std::tie(std::ignore,l,r)=query;
                lint L,R;std::tie(L,R)=seg.query(l,r);
                for(lint k_:moving){
                    if(k_<l||r<=k_)continue;
                    cmn(L,pos.at(a.at(k_)).first);
                    cmx(R,pos.at(a.at(k_)).second);
                }
                std::cout<<c.at(eular.query(L,R).second)<<'\n';
            }
        }
    }
}
/*
 * 各頂点から根までのパスの最大値を DFS で前計算です。
 * あとは LCA をオイラーツアーで求めます。
 * クエリ平方分割です。
 * クエリ区間で変わらないようなもの全てについて、
 * オイラーツアー順を min / max セグ木に入れます。
 * すると、取得クエリはクエリ区間でのセグ木の結果に、追加のものも union すればよいです。
 */
0