제출 #1155404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155404		12345678	Tourism (JOI23_tourism)	C++17	100 / 100	901 ms	30272 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=17;

int n, m, q, u, v, lvl[nx], pa[nx][kx], hd[nx], sz[nx], id[nx], t, res[nx], c[nx], l, r;
vector<int> d[nx];
vector<pair<int, int>> qrs[nx];

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    sz[u]=1;
    for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v];
}

void hld(int u, int p, int h)
{
    id[u]=++t;
    hd[u]=h;
    pair<int, int> hv;
    for (auto v:d[u]) if (v!=p) hv=max(hv, {sz[v], v});
    if (hv.first) hld(hv.second, u, h);
    for (auto v:d[u]) if (v!=p&&v!=hv.second) hld(v, u, v); 
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

struct segtree
{
    int mn[4*nx], lz[4*nx], mono[4*nx];\
    void show(int l ,int r, int i)
    {
        pushlz(l, r, i);
        if (l==r) return cout<<mn[i]<<' ', void();
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
    void build(int l, int r, int i)
    {
        mn[i]=0, lz[i]=-1, mono[i]=1;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void pushlz(int l, int r, int i)
    {
        if (lz[i]==-1) return;
        mn[i]=lz[i];
        mono[i]=1;
        if (l!=r) lz[2*i]=lz[i], lz[2*i+1]=lz[i];
        lz[i]=-1;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        mn[i]=min(mn[2*i], mn[2*i+1]);
        mono[i]=mono[2*i]&mono[2*i+1]&&mn[2*i]==mn[2*i+1];
    }
    int query(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (idx<l||r<idx) return 1e9;
        if (l==r) return mn[i];
        int md=(l+r)/2;
        return min(query(l, md, 2*i, idx), query(md+1, r, 2*i+1, idx));
    }
    int walkonseg(int l, int r, int i, int idx, int vl)
    {
        pushlz(l, r, i);
        if (mono[i]&&mn[i]==vl) return r;
        if (l==r) return -1;
        int md=(l+r)/2;
        if (idx>md) return walkonseg(md+1, r, 2*i+1, idx, vl);
        int resl=walkonseg(l, md, 2*i, idx, vl);
        if (resl<md) return resl;
        int resr=walkonseg(md+1, r, 2*i+1, idx, vl);
        if (resr==-1) return resl;
        return resr;
    }
} s;

struct sumsegtree
{
    int d[4*nx];
    void show(int l, int r, int i)
    {
        if (l==r) return cout<<d[i]<<' ', void();
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r ,2*i+1);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]+=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r ,2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} sm;

void updateseg(int l, int r, int vl)
{
    int idx=l;
    while (idx<=r)
    {
        int cur=s.query(1, n, 1, idx);
        int tmp=min(s.walkonseg(1, n, 1, idx, cur), r);
        if (cur) sm.update(1, m, 1, cur, -(tmp-idx+1));
        idx=tmp+1;
    }
    sm.update(1, m, 1, vl, r-l+1);
    s.update(1, n, 1, l, r, vl);
}

void update(int u, int v, int vl)
{
    int l=lca(u, v);
    while (lvl[hd[u]]>lvl[l])
    {
        updateseg(id[hd[u]], id[u], vl);
        u=pa[hd[u]][0];
    }
    if (u!=l) updateseg(id[l]+1, id[u], vl);
    while (lvl[hd[v]]>lvl[l])
    {
        updateseg(id[hd[v]], id[v], vl);
        v=pa[hd[v]][0];
    }
    if (v!=l) updateseg(id[l]+1, id[v], vl);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<=m; i++) cin>>c[i];
    for (int i=1; i<=q; i++) cin>>l>>r, qrs[r].push_back({l, i});
    dfs(1, 1);
    hld(1, 1, 1);
    s.build(1, n, 1);
    for (int i=1; i<=m; i++)
    {
        if (i>1) update(c[i], c[i-1], i);
        for (auto [l, idx]:qrs[i]) res[idx]=sm.query(1, m, 1, l+1, m);
    }
    for (int i=1; i<=q; i++) cout<<res[i]+1<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41