結果

問題 No.1030 だんしんぐぱーりない
コンテスト
ユーザー carrot46
提出日時 2020-04-17 23:14:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 492 ms / 2,000 ms
コード長 3,635 bytes
コンパイル時間 1,870 ms
コンパイル使用メモリ 175,724 KB
実行使用メモリ 27,072 KB
最終ジャッジ日時 2024-10-03 15:15:40
合計ジャッジ時間 15,344 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

template<class T> bool chmin(T &a, const T &b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T &b){
    if(a < b) {a = b; return true;}
    else return false;
}

vec c(1e+5 + 10), a(1e+5 + 10, -1), ran(1e+5 + 10);
mat G(1e+5 + 10, vec(0)), dbl(18, vec(1e+5 + 10, -1));
void dfs(int v, int p, ll pc, int r){
    dbl[0][v] = p;
    ran[v] = r;
    chmax(c[v], pc);
    for(int to : G[v]){
        if(to != p) dfs(to, v, c[v], r + 1);
    }
}

ll LCA(int p, int q){
    if(p == -1 || q == -1) return max(p, q);
    if(ran[p] > ran[q]) swap(p, q);
    int dif = ran[q] - ran[p];
    Rrep(i, 18) if((dif>>i)&1) q = dbl[i][q];
    if(p == q) return p;
    Rrep(i,18) {
        if(dbl[i][p] != dbl[i][q]){
            p = dbl[i][p];
            q = dbl[i][q];
        }
    }
    return dbl[0][p];
}

int main() {
    class SEGTREE{
                ll n, dflt;
          		vector<ll> dat;
            public:
            	SEGTREE(unsigned long _n, ll _a) : dat(_n * 4, _a){
            	    n = 1;
            	    dflt = _a;
            	    while(n < _n) n *= 2;
                }
                void update(ll k, ll a){
                    k += n;
                    dat[k] = a;
                    while(k > 0){
                        k /= 2;
                        dat[k] = LCA(dat[k * 2], dat[k * 2 + 1]);
                    }
                }
                void init(vector<ll> &v){
            	    for(int i = 0; i < K; ++i) dat[i + n] = v[i];
            	    for(int i = n - 1; i >= 1; --i) {
            	        dat[i] = LCA(dat[i * 2], dat[i * 2 + 1]);
            	    }
            	}
                ll Q(ll a, ll b){
            	    return query(a, b, 1, 0, n);
            	}
                ll query(ll a, ll b, ll k, ll l, ll r){
                    if(r <= a || b <= l) return dflt;
                    if(a <= l && r <= b) return dat[k];
                    ll vl = query(a, b, k * 2, l, (l + r) / 2);
                    ll vr = query(a, b, k * 2 + 1, (l + r) / 2, r);
                    return LCA(vl, vr);
                }
                //単項にアクセスする[]だが、書き換え厳禁
                //一応後でinitすれば書き換えてもよさそうだが…
                ll & operator [](int k) {return dat[k + n];}
        };
    cin>>N>>K>>Q;
    rep(i,N) cin>>c[i];
    rep(i,K){
        cin>>a[i];
        --a[i];
    }
    rep(i,N - 1){
        int s, t;
        cin>>s>>t;
        --s;
        --t;
        G[t].push_back(s);
    }
    dfs(0, 0, 0, 0);
    reps(i,1,18){
        rep(j,N){
            //if(dbl[i-1][j] < 0 || dbl[i-1][j] >= N) cout<<i<<' '<<j<<' '<<dbl[i-1][j]<<endl;
            dbl[i][j] = dbl[i-1][dbl[i-1][j]];
        }
    }
    //cout<<'a'<<endl;
    SEGTREE seg(K + 10, -1);
    //a.resize(K);
    seg.init(a);
    rep(i,Q){
        cin>>M;
        if(M == 1){
            int x, y;
            cin>>x>>y;
            --x;
            --y;
            seg.update(x, y);
        }else{
            int l, r;
            cin>>l>>r;
            cout<<c[seg.Q(l - 1, r)]<<endl;
        }
    }
}
0