제출 #1242152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242152		Dedibeat	Birthday gift (IZhO18_treearray)	C++20	0 / 100	0 ms	328 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first 
#define S second 
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T> 
void print(const T &v, int lim = 1e9)
{
    for(auto x : v)
        if(lim-- > 0) cout << x << " ";
    cout << endl;
}
template<typename T>
void print(T *begin, const T *end)
{
    for(T *it = begin; it < end; it++)
        cout << *it << " ";
    cout << endl;
}
int n, l, m, q;
vector<vector<int>> adj;

int timer;
vector<int> tin, tout;
vector<vector<int>> up;

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}



struct container{
    vector<multiset<int>> con;
    vector<int> v;
    container(vector<int> v, int mx) : v(v)
    {
        con.assign(mx + 10, multiset<int>());
        for(int i = 0; i < n; i++)
            con[v[i]].insert(i);
    }

    void upd(int pos, int x)
    {
        int prev = v[pos];
        con[prev].erase(con[prev].lower_bound(pos));
        con[x].insert(pos);
        v[pos] = x;
    }

    int get(int l, int r, int x)
    {
        auto it = con[x].lower_bound(l);
        if(it != con[x].end() && *it <= r) 
            return *it;
        else return -1;
    }
};


int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL);
    cin >> n >> m >> q;
    adj.assign(n, vector<int>());
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    preprocess(0);
    vector<int> a(m);
    for(int i = 0; i < m; i++)
        cin >> a[i], a[i]--;

    vector<int> b(m);
    for(int i = 1; i < m; i++)
        b[i] = lca(a[i - 1], a[i]);

    container conA(a, n), conB(b, n);
    while(q--)
    {
        int type;
        cin >> type;
        //cout << "q " <<  type << ": \n";
        if(type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            pos--, val--;
            a[pos] = val;
            conA.upd(pos, val);
            if(pos > 0) conB.upd(pos, lca(a[pos - 1], a[pos]));
            if(pos < n - 1) conB.upd(pos + 1, lca(a[pos], a[pos + 1]));
        }
        else 
        {
            int l, r, v;
            cin >> l >> r >> v;
            l--, r--, v--;
            
            int x1 = conA.get(l, r, v), x2 = conB.get(l + 1, r, v);
            if(x1 != -1) cout << x1 + 1 << ' ' << x1 + 1 << "\n";
            else if(x2 != -1) cout << x2 << " " << x2 + 1 << "\n";
            else cout << "-1 -1\n";
        }
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44