제출 #1325881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325881		animal_migration	Tourism (JOI23_tourism)	C++17	52 / 100	5095 ms	20520 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define rep(x,y,z) for (int x=y;x<z;x++)
const int bz=500;

struct F{
  vector<int> bit;
  vector<int> bit2;
  int n;
  void init(int x){
    n=x+1;
    bit.resize(n,0);
    bit2.resize(n,0);
  }
  void reset(){
    fill(all(bit),0);
  }
  int low(int x){
    return (x&(-x));
  }
  void add(int x, int v){
    for (int i=x+1;i<n;i+=low(i)){
      bit[i]+=v;
    }
  }
  int pre(int x){
    int res=0;
    for (int i=x+1;i>0;i-=low(i)){
      res+=bit[i];
    }
    return res;
  }
  int qry(int l, int r){
    return pre(r)-pre(l-1);
  }
};

signed main(){
  cin.tie(nullptr)->ios::sync_with_stdio(0);
  //euler tour subtree query, bit -> point add range query
  int n,m,q;
  cin>>n>>m>>q;
  vector<vector<int>> adj(n);
  rep(i,1,n){
    int ca,cb;
    cin>>ca>>cb;
    ca--; cb--;
    adj[ca].eb(cb);
    adj[cb].eb(ca);
  }
  vector<int> st(n), en(n);
  vector<int> ff(n),lf(n),dep(n);
  int tim=-1;
  function<void(int,int)> cal=[&](int u, int f){
    st[u]=++tim;
    ff[u]=f;
    int p=lf[ff[u]],q=lf[p];
    if (u!=f&&dep[q]-dep[p]==dep[p]-dep[ff[u]]) lf[u]=q;
    else lf[u]=ff[u];
    for (int v:adj[u]){
      if (v==f) continue;
      dep[v]=dep[u]+1;
      cal(v,u);
    }
    en[u]=tim;
  };
  dep[0]=0;
  cal(0,0);
  function<int(int,int)> lca=[&](int u, int v){
    if (dep[u]<dep[v]) swap(u,v);
    while (dep[u]>dep[v]){
      if (dep[lf[u]]>=dep[v]){
        u=lf[u];
      }else{
        u=ff[u];
      }
    }
    while (u!=v){
      if (lf[u]!=lf[v]){
        u=lf[u];
        v=lf[v];
      }else{
        u=ff[u];
        v=ff[v];
      }
    }
    return u;
  };
  F bit;
  bit.init(n);
  function<int(int)> sub=[&](int x){
    return bit.qry(st[x],en[x]);
  };
  function<void(int,int)> upd=[&](int x, int v){
    bit.add(st[x],v);
  };
  //precom adj lca
  vector<int> a(m);
  rep(i,0,m){
    cin>>a[i];
    a[i]--;
  }
  //sqrt decom, add, row back function
  int cr=-1, cs=0;
  stack<tuple<int,int,int>> row;
  function<void(int,bool)> add=[&](int x, bool o){
    // cout<<x+1<<"+\n";
    if (o) row.push({cs,cr,x});
    if (cr==-1){ cs=1; cr=x; upd(x,1); return; }
    int nr=lca(x,cr);
    // cout<<x+1<<"l: "<<nr<<'\n';
    if (dep[nr]<dep[cr]){
      upd(nr,1);
      if (o) row.push({cs,cr,nr});
      cs+=dep[cr]+dep[x]-dep[nr]*2;
    }else{
      int ins=x;
      while (!sub(ins)){
        // if (ins==0) break;
        if (!sub(lf[ins])) ins=lf[ins];
        else ins=ff[ins];
      }
      cs+=dep[x]-dep[ins];
      // cout<<x+1<<": "<<ins+1<<'\n';
    }
    cr=nr;
    upd(x,1);
  };
  vector<int> ans(q);
  int bn=(m+bz-1)/bz;
  struct Q{ int l; int r; int id; };
  auto com=[&](Q &a, Q &b){ return a.r<b.r; };
  vector<vector<Q>> qry(bn);
  rep(i,0,q){
    int l,r;
    cin>>l>>r;
    l--; r--;
    qry[l/bz].pb({l,r,i});
  }
  rep(i,0,bn){
    bit.reset(); cr=-1; cs=0;
    sort(all(qry[i]),com);
    int ql=min(m,i*bz+bz), qr=min(m-1,i*bz+bz-1);
    for (auto [l,r,id]:qry[i]){
      if (r<i*bz+bz){
        for (int j=l;j<=r;j++){
          add(a[j],1);
        }
        ans[id]=cs;
        while (!row.empty()){
          auto [ss,rr,xx]=row.top();
          row.pop();
          cs=ss; cr=rr;
          upd(xx,-1);
        }
        continue;
      }
      while (qr<r){
        qr++;
        add(a[qr],0);
      }
      while (ql>l){
        ql--;
        add(a[ql],1);
      }
      ans[id]=cs;
      while (!row.empty()){
        auto [ss,rr,xx]=row.top();
        row.pop();
        cs=ss; cr=rr;
        upd(xx,-1);
      }
      ql=min(m,i*bz+bz);
    }
  }
  rep(i,0,q){
    cout<<ans[i]<<'\n';
  }
  return 0;
}

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