結果

問題 No.1030 だんしんぐぱーりない
ユーザー ngtkanangtkana
提出日時 2020-04-17 23:59:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 837 ms / 2,000 ms
コード長 4,776 bytes
コンパイル時間 2,696 ms
コンパイル使用メモリ 220,232 KB
実行使用メモリ 282,008 KB
最終ジャッジ日時 2024-04-14 16:17:21
合計ジャッジ時間 20,221 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 445 ms
143,480 KB
testcase_06 AC 532 ms
186,456 KB
testcase_07 AC 313 ms
129,428 KB
testcase_08 AC 390 ms
138,068 KB
testcase_09 AC 468 ms
149,200 KB
testcase_10 AC 161 ms
62,552 KB
testcase_11 AC 623 ms
228,812 KB
testcase_12 AC 196 ms
44,388 KB
testcase_13 AC 321 ms
102,984 KB
testcase_14 AC 628 ms
204,780 KB
testcase_15 AC 415 ms
161,436 KB
testcase_16 AC 264 ms
62,088 KB
testcase_17 AC 326 ms
90,404 KB
testcase_18 AC 660 ms
214,460 KB
testcase_19 AC 201 ms
56,976 KB
testcase_20 AC 187 ms
49,444 KB
testcase_21 AC 352 ms
122,628 KB
testcase_22 AC 182 ms
45,224 KB
testcase_23 AC 377 ms
117,180 KB
testcase_24 AC 485 ms
175,076 KB
testcase_25 AC 511 ms
170,576 KB
testcase_26 AC 212 ms
78,516 KB
testcase_27 AC 334 ms
131,452 KB
testcase_28 AC 460 ms
156,236 KB
testcase_29 AC 180 ms
47,500 KB
testcase_30 AC 144 ms
31,024 KB
testcase_31 AC 219 ms
53,432 KB
testcase_32 AC 587 ms
205,828 KB
testcase_33 AC 405 ms
134,240 KB
testcase_34 AC 209 ms
69,892 KB
testcase_35 AC 830 ms
281,876 KB
testcase_36 AC 825 ms
281,984 KB
testcase_37 AC 823 ms
282,008 KB
testcase_38 AC 828 ms
281,880 KB
testcase_39 AC 837 ms
282,004 KB
testcase_40 AC 2 ms
6,944 KB
testcase_41 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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