QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#420815 | #5403. 树数术 | Crying | 0 | 0ms | 0kb | C++14 | 3.5kb | 2024-05-24 22:22:56 | 2024-05-24 22:22:57 |
answer
#include<bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;
typedef long long ll;
typedef array<int,2> pr; typedef array<int,3> tr;
const int MAXN = 7e5+10,INF = 1e9;
void tomin(int& x,int y){x = min(x,y);}
void tomax(int& x,int y){x = max(x,y);}
//
int n,m,q,k,a[MAXN]; ll ans[MAXN];
int L[MAXN],R[MAXN],f[MAXN];
vector<int> e[MAXN];
struct ST{
int st[21][MAXN*2]; int key[MAXN*2],id[MAXN*2];
int cmp(int x,int y){return key[x] < key[y] ? x : y;}
void build(int n,int* a,int* b){
for(int i=1;i<=n;i++)key[i] = a[i],id[i] = b[i],st[0][i] = i;
for(int j=1;j<=20;j++)for(int i=1;i<=n-(1<<j)+1;i++)st[j][i] = cmp(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
int qry(int l,int r){
int len = __lg(r-l+1);
return id[cmp(st[len][l],st[len][r-(1<<len)+1])];
}
};
namespace _{ //lca
int dfn[MAXN*2],ord[MAXN],dep[MAXN],dtot;
int a[MAXN*2],b[MAXN*2]; ST st;
void dfs(int u,int fa){
dfn[++dtot] = u,ord[u] = dtot;
for(auto v : e[u])if(v != fa){
dep[v] = dep[u]+1;
dfs(v,u);
dfn[++dtot] = u;
}
}
void solve(){
dfs(1,0);
for(int i=1;i<=dtot;i++)a[i] = dep[dfn[i]],b[i] = dfn[i];
st.build(dtot,a,b);
}
int lca(int x,int y){
x = ord[x],y = ord[y]; if(x>y)swap(x,y);
return st.qry(x,y);
}
}; using _::lca;
int dfn[MAXN],sz[MAXN],dtot; int b[MAXN*2],c[MAXN*2]; ST st;
void dfs(int u,int fa){
dfn[u] = ++dtot; sz[u] = 1;
for(auto v : e[u])if(v != fa){
dfs(v,u); sz[u] += sz[v];
}
}
int chk(int x,int y){return dfn[x] <= dfn[y] && dfn[x]+sz[x] > dfn[y];}
int qry(int l,int r){
assert(l<=r);
int x = st.qry(l,r),y = st.qry(l+m,r+m);
return lca(x,y);
}
struct BIT{
int t[MAXN];
void mdf(int x){ for(;x<=m;x+=lowbit(x))t[x]++;}
int qry(int x,int S=0){for(;x;x-=lowbit(x))S += t[x];return S;}
}bit;
vector<tr> o[MAXN];
int main(){
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m>>q;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
e[u].push_back(v); e[v].push_back(u);
}
_::solve();
for(int i=1;i<=m;i++)cin>>a[i];
dfs(1,0);
for(int i=1;i<=m;i++)b[i] = dfn[a[i]],b[i+m] = -dfn[a[i]],c[i] = c[i+m] = a[i];
st.build(2*m,b,c);
for(int i=1;i<=m;i++){
int L = 1,R = i-1; f[i] = i;
while(L<=R){
int mid = (L+R)>>1;
if(chk(a[i],qry(mid,i)))f[i] = mid,R = mid-1;
else L = mid+1;
}
}
//
for(int id=1;id<=q;id++){
cin>>k;
for(int i=1;i<=k;i++)cin>>L[i]>>R[i];
auto opt = [&](int l,int r,int lim){
if(l>r)return;
o[r].push_back({lim,1,id});
o[l-1].push_back({lim,-1,id});
};
opt(L[1],R[1],L[1]); int p = qry(L[1],R[1]);
for(int i=2;i<=k;i++){
int l = L[i],r = R[i],ret = R[i]+1;
while(l<=r){
int mid = (l+r)>>1;
int q = qry(L[i],mid);
if(chk(q,p))ret = mid,r = mid-1;
else l = mid+1;
}
opt(ret,R[i],L[i]);
p = lca(p,qry(L[i],R[i]));
}
}
//
for(int i=1;i<=m;i++){
bit.mdf(f[i]);
for(auto [lim,v,id] : o[i]){
ans[id] += v * bit.qry(lim);
}
}
for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
699990 699995 233333 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #2:
score: 0
Dangerous Syscalls
input:
699992 699994 699992 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 40 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
result:
Subtask #3:
score: 0
Dangerous Syscalls
Test #3:
score: 0
Dangerous Syscalls
input:
99998 99993 33333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 24 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 49 ...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%