제출 #1243408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243408		Hanksburger	Tourism (JOI23_tourism)	C++17	100 / 100	1405 ms	179556 KiB

tourism

#include <bits/stdc++.h>
#define int long long
using namespace std;
int par[100005][20], depth[100005], a[100005], shared[100005], l[100005], r[100005], sum[100005], ans[100005];
vector<pair<int, int> > ranges[100005], vents[100005], vec;
vector<pair<pair<int, int>, pair<int, int> > > events;
vector<int> adj[100005], places[100005];
stack<int> s;
struct node1
{
    node1 *lc, *rc;
    int l, r, val;
    node1(int l, int r) : lc(0), rc(0), l(l), r(r), val(0) {}
};
struct node2
{
    node2 *lc, *rc;
    int l, r, val;
    node2(int l, int r) : lc(0), rc(0), l(l), r(r), val(1e18) {}
};
struct node3
{
    node3 *lc, *rc;
    int l, r, val;
    node3(int l, int r) : lc(0), rc(0), l(l), r(r), val(0) {}
};
struct node4
{
    node4 *lc, *rc;
    int l, r, val;
    node4(int l, int r) : lc(0), rc(0), l(l), r(r), val(0) {}
};
void dfs(int u)
{
    //cout << "dfs " << u << '\n';
    for (int i=1; i<20; i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for (int x:places[u])
        vec.push_back({u, x});
    for (int v:adj[u])
    {
        if (v==par[u][0])
            continue;
        par[v][0]=u;
        depth[v]=depth[u]+1;
        dfs(v);
    }
}
int lca(int u, int v)
{
    if (depth[u]<depth[v])
        swap(u, v);
    for (int i=0; i<20; i++)
        if ((depth[u]-depth[v])&(1<<i))
            u=par[u][i];
    if (u==v)
        return u;
    for (int i=19; i>=0; i--)
        if (par[u][i]!=par[v][i])
            u=par[u][i], v=par[v][i];
    return par[u][0];
}
bool cmp(pair<int, int> x, pair<int, int> y)
{
    if (x.second!=y.second)
        return x.second<y.second;
    return x.first>y.first;
}
void update1(node1 *i, int x, int y)
{
    if (i->l==i->r)
    {
        i->val=y;
        return;
    }
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        if (!i->lc)
            i->lc=new node1(i->l, mid);
        update1(i->lc, x, y);
    }
    else
    {
        if (!i->rc)
            i->rc=new node1(mid+1, i->r);
        update1(i->rc, x, y);
    }
    i->val=max(i->lc?i->lc->val:0, i->rc?i->rc->val:0);
}
int query1(node1 *i, int ql, int qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->val;
    int mid=(i->l+i->r)/2, res=0;
    if (i->lc && i->l<=qr && ql<=mid)
        res=max(res, query1(i->lc, ql, qr));
    if (i->rc && mid<qr && ql<=i->r)
        res=max(res, query1(i->rc, ql, qr));
    return res;
}
void update2(node2 *i, int x, int y)
{
    if (i->l==i->r)
    {
        i->val=y;
        return;
    }
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        if (!i->lc)
            i->lc=new node2(i->l, mid);
        update2(i->lc, x, y);
    }
    else
    {
        if (!i->rc)
            i->rc=new node2(mid+1, i->r);
        update2(i->rc, x, y);
    }
    i->val=min(i->lc?i->lc->val:1e18, i->rc?i->rc->val:1e18);
}
int query2(node2 *i, int ql, int qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->val;
    int mid=(i->l+i->r)/2, res=1e18;
    if (i->lc && i->l<=qr && ql<=mid)
        res=min(res, query2(i->lc, ql, qr));
    if (i->rc && mid<qr && ql<=i->r)
        res=min(res, query2(i->rc, ql, qr));
    return res;
}
void build3(node3 *i)
{
    if (i->l==i->r)
    {
        i->val=a[i->l];
        return;
    }
    int mid=(i->l+i->r)/2;
    build3(i->lc=new node3(i->l, mid));
    build3(i->rc=new node3(mid+1, i->r));
    i->val=lca(i->lc->val, i->rc->val);
}
int query3(node3 *i, int ql, int qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->val;
    int mid=(i->l+i->r)/2;
    if (i->l<=qr && ql<=mid)
    {
        if (mid<qr && ql<=i->r)
            return lca(query3(i->lc, ql, qr), query3(i->rc, ql, qr));
        else
            return query3(i->lc, ql, qr);
    }
    else
        return query3(i->rc, ql, qr);
}
void update4(node4 *i, int x, int y)
{
    if (i->l==i->r)
    {
        i->val+=y;
        return;
    }
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        if (!i->lc)
            i->lc=new node4(i->l, mid);
        update4(i->lc, x, y);
    }
    else
    {
        if (!i->rc)
            i->rc=new node4(mid+1, i->r);
        update4(i->rc, x, y);
    }
    i->val=(i->lc?i->lc->val:0)+(i->rc?i->rc->val:0);
}
int query4(node4 *i, int ql, int qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->val;
    int mid=(i->l+i->r)/2, res=0;
    if (i->lc && i->l<=qr && ql<=mid)
        res+=query4(i->lc, ql, qr);
    if (i->rc && mid<qr && ql<=i->r)
        res+=query4(i->rc, ql, qr);
    return res;
}
signed main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1; i<=m; i++)
    {
        cin >> a[i];
        places[a[i]].push_back(i);
        //cout << "places " << a[i] << ' ' << i << '\n';
    }
    if (m==1)
    {
        for (int i=1; i<=q; i++)
            cout << 1 << '\n';
        return 0;
    }
    par[1][0]=1;
    dfs(1);
    node3 *root3=new node3(1, m);
    build3(root3);
    for (int i=1; i<=m; i++)
        sum[i]=sum[i-1]+depth[a[i]]+1;
    // remember to take care of vec.size() = 1 and queries where L = R
    //cout << "vec size " << vec.size() << '\n';
    for (int i=0; i+1<vec.size(); i++)
        shared[i]=depth[lca(vec[i].first, vec[i+1].first)]+1;
    s.push(0);
    for (int i=1; i+1<vec.size(); i++)
    {
        while (s.size() && shared[s.top()]>shared[i])
            s.pop();
        l[i]=s.size()?s.top()+1:0;
        s.push(i);
    }
    while (s.size())
        s.pop();
    s.push((int)vec.size()-2);
    r[(int)vec.size()-2]=(int)vec.size()-2;
    for (int i=(int)vec.size()-3; i>=0; i--)
    {
        while (s.size() && shared[s.top()]>=shared[i])
            s.pop();
        r[i]=s.size()?s.top()-1:(int)vec.size()-2;
        s.push(i);
    }
    //cout << "HI\n";
    for (int i=0; i+1<vec.size(); i++)
    {
        if (i-l[i]<r[i]-i)
            for (int j=l[i]; j<=i; j++)
                events.push_back({{vec[j].second, i}, {i+1, r[i]+1}});
        else
            for (int j=i+1; j<=r[i]+1; j++)
                events.push_back({{vec[j].second, i}, {l[i], i}});
        //cout << "i l r " << i << ' ' << l[i] << ' ' << r[i] << ' ' << events.size() << '\n';
    }
    for (int i=0; i<vec.size(); i++)
        events.push_back({{vec[i].second, -1}, {i, i}});
    sort(events.begin(), events.end());
    node1 *root1=new node1(0, (int)vec.size()-1);
    for (auto x:events)
    {
        if (x.first.second==-1)
            update1(root1, x.second.first, x.first.first);
        else
        {
            int res=query1(root1, x.second.first, x.second.second);
            //cout << "query " << x.second.first << ' ' << x.second.second << ' ' << res << '\n';
            if (res)
            {
                ranges[x.first.second].push_back({res, x.first.first});
                //cout << "push into range " << x.first.second << ' ' << ranges[x.first.second].size() << '\n';
            }
        }
    }
    reverse(events.begin(), events.end());
    node2 *root2=new node2(0, (int)vec.size()-1);
    for (auto x:events)
    {
        if (x.first.second==-1)
            update2(root2, x.second.first, x.first.first);
        else
        {
            int res=query2(root2, x.second.first, x.second.second);
            //cout << "query " << x.second.first << ' ' << x.second.second << ' ' << res << '\n';
            if (res<1e18)
            {
                ranges[x.first.second].push_back({x.first.first, res});
                //cout << "push into range " << x.first.second << ' ' << ranges[x.first.second].size() << '\n';
            }
        }
    }
    for (int i=0; i+1<vec.size(); i++)
    {
        //cout << "i=" << i << ' ' << ranges[i].size() << '\n';
        sort(ranges[i].begin(), ranges[i].end(), cmp);
        vector<pair<int, int> > tmp;
        for (int j=0; j<ranges[i].size(); j++)
        {
            if (!j || ranges[i][j-1].second<ranges[i][j].second)
                tmp.push_back({ranges[i][j].first, ranges[i][j].second});
            //cout << ranges[i][j].first << ' ' << ranges[i][j].second << '\n';
        }
        for (int j=0; j<tmp.size(); j++)
        {
            vents[tmp[j].second].push_back({tmp[j].first, shared[i]});
            if (j)
                vents[tmp[j].second].push_back({tmp[j-1].first, -shared[i]});
        }
    }
    for (int i=1; i<=q; i++)
    {
        int L, R;
        cin >> L >> R;
        vents[R].push_back({-L, i});
        ans[i]=sum[R]-sum[L-1]-depth[query3(root3, L, R)];
        //cout << "ans " << i << ' ' << ans[i] << '\n';
    }
    node4 *root4=new node4(1, m);
    for (int i=1; i<=m; i++)
    {
        sort(vents[i].begin(), vents[i].end(), greater<pair<int, int> >());
        for (auto x:vents[i])
        {
            if (x.first>0)
                update4(root4, x.first, x.second);
            else
                ans[x.second]-=query4(root4, -x.first, i);
        }
    }
    for (int i=1; i<=q; i++)
        cout << ans[i] << '\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