結果

問題 No.1030 だんしんぐぱーりない
ユーザー ngtkanangtkana
提出日時 2020-04-17 23:51:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,015 bytes
コンパイル時間 2,252 ms
コンパイル使用メモリ 227,048 KB
実行使用メモリ 281,968 KB
最終ジャッジ日時 2024-10-03 16:15:25
合計ジャッジ時間 42,193 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 1,082 ms
143,488 KB
testcase_06 AC 1,488 ms
186,360 KB
testcase_07 AC 904 ms
129,440 KB
testcase_08 AC 1,005 ms
137,868 KB
testcase_09 AC 1,148 ms
149,048 KB
testcase_10 AC 394 ms
62,556 KB
testcase_11 AC 1,768 ms
228,888 KB
testcase_12 AC 225 ms
44,264 KB
testcase_13 AC 703 ms
102,984 KB
testcase_14 AC 1,685 ms
204,844 KB
testcase_15 AC 1,151 ms
161,560 KB
testcase_16 AC 446 ms
62,228 KB
testcase_17 AC 626 ms
90,280 KB
testcase_18 AC 1,657 ms
214,400 KB
testcase_19 AC 384 ms
56,856 KB
testcase_20 AC 312 ms
49,444 KB
testcase_21 AC 901 ms
122,636 KB
testcase_22 AC 286 ms
45,236 KB
testcase_23 AC 867 ms
117,180 KB
testcase_24 AC 1,274 ms
175,204 KB
testcase_25 AC 1,307 ms
170,436 KB
testcase_26 AC 518 ms
78,656 KB
testcase_27 AC 905 ms
131,456 KB
testcase_28 AC 1,178 ms
156,244 KB
testcase_29 AC 255 ms
47,508 KB
testcase_30 AC 170 ms
31,032 KB
testcase_31 AC 378 ms
53,564 KB
testcase_32 AC 1,633 ms
205,784 KB
testcase_33 AC 976 ms
134,240 KB
testcase_34 AC 484 ms
69,772 KB
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 AC 2 ms
6,816 KB
testcase_41 AC 2 ms
6,820 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;
    }
}; // }}}
#define ENABLE_DEBUG 0
#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
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);
    DEBUG(eular.to_vec(),pos);
    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;
        }
    }
    DEBUG(sq,queries,move);
    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.set(j,pos.at(a.at(j)));
        }
        std::vector<lint>moving;
        for(lint j=0;j<k;j++){
            if(move.at(i).at(j))moving.push_back(j);
        }
        DEBUG(i,a,seg.to_vec(),eular.to_vec(),moving);
        for(lint j=i*sq;j<std::min((i+1)*sq,q);j++){
            auto&&query=queries.at(j);
            DEBUG(query);
            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);
                }
                DEBUG(L,R);
                std::cout<<c.at(eular.query(L,R).second)<<'\n';
            }
        }
    }
}
/*
 * 各頂点から根までのパスの最大値を DFS で前計算です。
 * あとは LCA をオイラーツアーで求めます。
 * クエリ平方分割です。
 * クエリ区間で変わらないようなもの全てについて、
 * オイラーツアー順を min / max セグ木に入れます。
 * すると、取得クエリはクエリ区間でのセグ木の結果に、追加のものも union すればよいです。
 */
0