QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340509#4387. Static Query on Treecrsfaa#AC ✓82ms65752kbC++144.0kb2024-02-29 09:26:412024-02-29 09:26:41

Judging History

你现在查看的是最新测评结果

  • [2024-02-29 09:26:41]
  • 评测
  • 测评结果:AC
  • 用时:82ms
  • 内存:65752kb
  • [2024-02-29 09:26:41]
  • 提交

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
    int s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s;
}
const int mxn=6e5+5;
struct node
{
    int x,nxt;
}a[mxn*2];
int head[mxn];
int cnt;
void add(int x,int y)
{
    a[++cnt].x=y;
    a[cnt].nxt=head[x];
    head[x]=cnt;
}
int f[mxn];
int dcnt;
#define pr pair<int,int>
struct Word_RMQ
{
    #define w 32
    #define u unsigned
    #define be(x) ((x>>5)+1)
    #define l(x) ((x-1<<5)+(x==1))
    #define r(x) min(N,((x<<5)-1))
    #define bm mxn/w+5
    int N;
    pr *a;
    pr ST[int(log2(bm)+1)][bm];
    pr pre[mxn],nxt[mxn];
    struct node
    {
        u st[w+1];
        pr *p;
        inline pr ask(int l,int r)
        {
            return p[l+__builtin_ctz(st[r]>>l-1)];
        }
        void init(pr *p_,int len)
        {
            p=p_;
            int i,top=0;
            int stack[w+1];
            for(i=1;i<=len;i++)
            {
                st[i]=st[i-1];
                while(top&&p[i]<p[stack[top]])
                    st[i]-=1u<<stack[top--]-1;
                stack[++top]=i,st[i]+=1u<<i-1;
            }
        }
    }k[bm];
    void build(pr A[],int n)
    {
        a=A,N=n;
        int i,j,cnt=0;
        for(i=1;;i++)
        {
            k[i].init(a+l(i)-1,r(i)-l(i)+1);
            for(j=l(i)+1,pre[l(i)]=a[l(i)];j<=r(i);j++)
                pre[j]=min(pre[j-1],a[j]);
            for(j=r(i)-1,nxt[r(i)]=a[r(i)];j>=l(i);j--)
                nxt[j]=min(nxt[j+1],a[j]);
            ST[0][i]=pre[r(i)];
            cnt++;
            if(r(i)==n) break;
        }
        for(j=1;(1<<j)<=cnt;j++)
            for(i=1;i+(1<<j)-1<=cnt;i++)
                ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);
    }
    inline pr STask(int L,int R)
    {
        if(L>R) return make_pair(INT_MAX,INT_MAX);
        int k=__lg(R-L+1);
        return min(ST[k][L],ST[k][R-(1<<k)+1]);
    }
    inline pr ask(int L,int R)
    {
        if(L>R) return make_pair(INT_MAX,INT_MAX);
        if(be(L)==be(R)) return k[be(L)].ask(L-l(be(L))+1,R-l(be(L))+1);
        return min({STask(be(L)+1,be(R)-1),pre[R],nxt[L]});
    }
    #undef w
    #undef l
    #undef r
}ds;
pr st[mxn];
int dep[mxn];
void dfs(int d,int deep,int fa)
{
    st[dcnt]=make_pair(dep[d]=deep,fa),f[d]=++dcnt;
    for(int i=head[d];i;i=a[i].nxt)
        if(!f[a[i].x])
            dfs(a[i].x,deep+1,d);
}
int asklca(int l,int r)
{
	if(l==r) return l;
    l=f[l],r=f[r];
    if(l>r) swap(l,r);
    return ds.ask(l,r-1).second;
}
int ca[mxn],cb[mxn],cc[mxn];
int ht[mxn],fa[mxn];
vector<int> h[mxn];
int sum;
bool cmp(int x,int y)
{
	return f[x]<f[y];
}
void dfs(int d,int s)
{
	s+=cc[d];
	for(auto i:h[d])
		dfs(i,s),ca[d]+=ca[i],cb[d]+=cb[i];
	if(ca[d]&&cb[d])
		sum+=!!s+(dep[d]-dep[fa[d]]-1)*!!(s-cc[d]);
}
int main()
{
	int T=read();
	while(T--)
	{
		int n=read(),m=read(),x,i;
		cnt=dcnt=0;
		memset(head,0,n+1<<2);
	    for(i=2;i<=n;i++)
		    add(read(),i);
	    dfs(1,1,0);
	    ds.build(st,n);
	    while(m--)
	    {
	    	int sz1=read(),sz2=read(),sz3=read(),cnt=0;
	    	ht[++cnt]=1;
	    	while(sz1--)
	    		x=ht[++cnt]=read(),ca[x]=1;
	    	while(sz2--)
	    		x=ht[++cnt]=read(),cb[x]=1;
	    	while(sz3--)
	    		x=ht[++cnt]=read(),cc[x]=1;
	    	sort(ht+1,ht+1+cnt,cmp);
	    	cnt=unique(ht+1,ht+1+cnt)-ht-1;
	    	for(i=cnt;i>1;i--)
	    		ht[++cnt]=asklca(ht[i],ht[i-1]);
	    	sort(ht+1,ht+1+cnt,cmp);
	    	cnt=unique(ht+1,ht+1+cnt)-ht-1;
	    	for(i=2;i<=cnt;i++)
	    		h[fa[ht[i]]=asklca(ht[i],ht[i-1])].push_back(ht[i]);
	    	sum=0,dfs(1,0);
	    	printf("%d\n",sum);
	    	for(i=1;i<=cnt;i++)
	    		h[ht[i]].clear(),ca[ht[i]]=cb[ht[i]]=cc[ht[i]]=0;
		}
	} 
}
/*
2
7 3
1 1 2 2 3 3
2 1 1
1 2
4
1
4 4 3
4 5 6 7
4 5 6 7
2 4 6
2 1 1
4 5
6
1
7 3
1 1 2 2 3 3
2 1 1
1 2
4
1
4 4 3
4 5 6 7
4 5 6 7
2 4 6
2 1 1
4 5
6
1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 82ms
memory: 65752kb

input:

1
200000 18309
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

102147
62590
87270
88880
7654
61542
62953
85022
55135
54125
70500
64356
25824
88300
42278
15336
18132
28734
90282
42889
28099
31311
96842
19959
34366
60205
78358
91142
56048
74688
86091
51979
94750
11989
89544
86860
56720
29534
52343
90031
79002
90293
94554
48340
65015
9181
15016
19884
49445
14181
6...

result:

ok 18309 numbers