QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243391 | #5403. 树数术 | hhhgjy | 30 | 97ms | 61448kb | C++14 | 2.8kb | 2023-11-08 09:53:45 | 2023-11-08 09:53:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,Q,Log[700005],A[700005],in[700005],out[700005],tot1,lef[700005],q[700005],tail;
int mn[20][700005],mx[20][700005];
int getmin(int l,int r){
int len=Log[r-l+1];
return min(mn[len][l],mn[len][r-(1<<len)+1]);
}
int getmax(int l,int r){
int len=Log[r-l+1];
return max(mx[len][l],mx[len][r-(1<<len)+1]);
}
int getpos1(int l,int r,int v){
if(getmin(l,r)>v)return 0;
int pl=l,pr=r,ans=0;
while(pl<=pr){
int mid=pl+pr>>1;
if(getmin(l,mid)<=v)ans=mid,pr=mid-1;
else pl=mid+1;
} return ans;
}
int getpos2(int l,int r,int v){
if(getmax(l,r)<v)return 0;
int pl=l,pr=r,ans=0;
while(pl<=pr){
int mid=pl+pr>>1;
if(getmax(l,mid)>=v)ans=mid,pr=mid-1;
else pl=mid+1;
} return ans;
}
vector<int>road[700005];
void dfs(int u,int fa){
in[u]=out[u]=++tot1;
for(int v:road[u]){
if(v==fa)continue;
dfs(v,u);out[u]=out[v];
}
}
int rt[700005],tot,son[14000005][2],cnt[14000005];
void ins(int &p,int q,int l,int r,int pos){
p=++tot;son[p][0]=son[q][0],son[p][1]=son[q][1],cnt[p]=cnt[q]+1;
if(l==r)return;int mid=l+r>>1;
if(pos<=mid)ins(son[p][0],son[q][0],l,mid,pos);
else ins(son[p][1],son[q][1],mid+1,r,pos);
}
int query(int p,int q,int l,int r,int a,int b){
if(a<=l&&r<=b)return cnt[p]-cnt[q];int mid=l+r>>1,res=0;
if(a<=mid)res+=query(son[p][0],son[q][0],l,mid,a,b);
if(b>mid)res+=query(son[p][1],son[q][1],mid+1,r,a,b);
return res;
}
int tot2,L[7000005],R[7000005];
int main(){
scanf("%d%d%d",&N,&M,&Q);
for(int i=1;i<N;++i){
int u,v;scanf("%d%d",&u,&v);
road[u].push_back(v);road[v].push_back(u);
} dfs(1,-1);
for(int i=2;i<=M;++i)Log[i]=Log[i>>1]+1;
for(int i=1;i<=M;++i){
scanf("%d",&A[i]);
while(tail&&in[A[q[tail]]]>=in[A[i]])--tail;
lef[i]=q[tail];q[++tail]=i;
}tail=0;
for(int i=1;i<=M;++i){
while(tail&&out[A[q[tail]]]<=out[A[i]])--tail;
lef[i]=max(lef[i],q[tail]);q[++tail]=i;++lef[i];
}
for(int i=1;i<=M;++i)ins(rt[i],rt[i-1],1,M,lef[i]),mn[0][i]=in[A[i]],mx[0][i]=out[A[i]];
for(int j=1;(1<<j)<=M;++j)for(int i=1;i+(1<<j)-1<=M;++i)mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<j-1)]),mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<j-1)]);
while(Q--){
scanf("%d",&tot2);
for(int i=1;i<=tot2;++i)scanf("%d%d",&L[i],&R[i]);
int Mn=1e9,Mx=0;ll res=0;
for(int i=1;i<=tot2;++i){
if(i==1){
res+=1ll*query(rt[R[i]],rt[L[i]-1],1,M,1,L[i]);
Mn=getmin(L[i],R[i]);Mx=getmax(L[i],R[i]);
continue;
}
int pos1=getpos1(L[i],R[i],Mn);
int pos2=getpos2(L[i],R[i],Mx);
if(!pos1||!pos2){
Mn=min(Mn,getmin(L[i],R[i]));
Mx=max(Mx,getmax(L[i],R[i]));
continue;
} pos1=max(pos1,pos2);
res+=1ll*query(rt[R[i]],rt[pos1-1],1,M,1,L[i]);
Mn=min(Mn,getmin(L[i],R[i])),Mx=max(Mx,getmax(L[i],R[i]));
} printf("%lld\n",res);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
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:
448495 -520897 451773 -58083 -65613 -18280 506298 686256 -378308 344972 35658 -59626 -38219 1598010 785173 313664 850355 448075 407812 -458769 -52713 -9250 6480 -553904 7130 -452731 545802 179812 35432 -148412 79310 -144620 -552187 -965030 -242092 462420 -74593 665726 382058 -608642 475440 -441833 -...
result:
Subtask #2:
score: 0
Runtime Error
Test #2:
score: 0
Runtime Error
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:
0 12051 38 7773 22599 -8507 -1 -225 3134 -7201 1678 -210881 7 -1427 -7 -12070 52535 -88650 -396 29391 -235715 15124 5342 -2966 -2972 2059 223645 -1746 12269 342364 -85 -208690 8389 -22060 -3367 13156 50081 -256495 5541 -67206 -5014 57 -69 235447 -74025 -29811 251496 23866 -1219 -222792 -843 36 -3117...
result:
Subtask #3:
score: 30
Accepted
Test #3:
score: 30
Accepted
time: 97ms
memory: 61448kb
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:
9733 11330 8403 5136 22207 23231 12686 27288 23739 20937 18153 16379 8991 14036 11669 14685 20272 18955 21680 7927 21383 23576 14834 5714 15707 10013 7905 13254 13883 10446 16140 16796 11009 11912 15761 20419 11157 12192 14327 18260 19095 5239 4114 16522 7412 5005 16844 8747 19377 22600 12023 9161 9...
result:
ok 33333 lines
Subtask #4:
score: 0
Skipped
Dependency #1:
0%