QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762060#7767. 数据结构Nesraychan0 1837ms315848kbC++145.8kb2024-11-19 13:11:112024-11-19 13:11:11

Judging History

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

  • [2024-11-19 13:11:11]
  • 评测
  • 测评结果:0
  • 用时:1837ms
  • 内存:315848kb
  • [2024-11-19 13:11:11]
  • 提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 200200
#define u64 unsigned long long
#define oo (1ll<<60)
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

const int B=3;
int n,q;
std::vector<int>G[N];

IL void add(reg int u,reg int v){G[u].push_back(v),G[v].push_back(u);}

namespace Segment
{

#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l[o]+r[o]>>1)

int l[N<<2],r[N<<2];
u64 sum[N<<2],tag[N<<2];

IL void pushup(reg int o){sum[o]=sum[ls]+sum[rs];}
IL void apply(reg int o,reg int k){sum[o]+=1ull*k*(r[o]-l[o]+1),tag[o]+=k;}
IL void pushdown(reg int o){if(tag[o])apply(ls,tag[o]),apply(rs,tag[o]),tag[o]=0;}

void build(reg int o,reg int L,reg int R)
{
    l[o]=L,r[o]=R;
    if(L<R)build(ls,L,mid),build(rs,mid+1,R);
}

void modify(reg int o,reg int L,reg int R,reg int k)
{
    if(L<=l[o]&&r[o]<=R)return apply(o,k);
    if(L>r[o]||l[o]>R)return;
    pushdown(o),modify(ls,L,R,k),modify(rs,L,R,k),pushup(o);
}

u64 query_sum(reg int o,reg int L,reg int R)
{
    if(L<=l[o]&&r[o]<=R)return sum[o]; if(L>r[o]||l[o]>R)return 0;
    return pushdown(o),query_sum(ls,L,R)+query_sum(rs,L,R);
}

#undef ls
#undef rs
#undef mid

}

int sz[N],dep[N],fa[N],son[N],anc[N];

void dfs1(reg int u)
{
    dep[u]=dep[fa[u]]+(sz[u]=1);
    for(auto v:G[u])if(!sz[v])
    {
        fa[v]=u,dfs1(v),sz[u]+=sz[v];
        if(sz[son[u]]<sz[v])son[u]=v;
    }
}

void dfs2(reg int u,reg int top)
{
    anc[u]=top; if(son[u])dfs2(son[u],top);
    for(auto v:G[u])if(!anc[v])dfs2(v,v);
}

IL int lca(reg int x,reg int y)
{
    for(;anc[x]!=anc[y];x=fa[anc[x]])
        if(dep[anc[x]]<dep[anc[y]])std::swap(x,y);
    return dep[x]<dep[y]?x:y;
}

template<class T>IL void clear(reg T &a){T b; std::swap(a,b);}

int dfn[N],ed[N],dfc;

void dfs3(reg int u)
{
    std::vector<int>P,Q;
    for(reg int x=u;x;x=son[x])
    {
        P.push_back(x);
        if(!dfn[x])dfn[x]=++dfc;
    }
    for(reg int o=1;o<=B;++o)
    {
        clear(Q);
        for(auto u:P)for(auto v:G[u])if(v!=fa[u])
        {
            if(!dfn[v])dfn[v]=++dfc;
            Q.push_back(v);
        }
        std::swap(P,Q);
    }
    for(reg int v=u;v;v=son[v])for(auto w:G[v])
        if(w!=fa[v]&&w!=son[v])dfs3(w);
}

struct Range{int l,r;};

#define Sets std::vector<Range>

Sets work(reg Sets a)
{
    Sets b;
    std::sort(a.begin(),a.end(),[&](const Range &x,const Range &y){return x.l<y.l;});
    reg int L=0,R=-1;
    for(auto &[l,r]:a)
        if(l==R+1)R=r;
        else ~R?b.push_back({L,R}),0:0,L=l,R=r;
    if(~R)b.push_back({L,R});
    return b;
}

Sets merge(const Sets &a,const Sets &b)
{
    Sets c;
    for(auto p:a)c.push_back(p);
    for(auto p:b)c.push_back(p);
    return c;
}

IL void ins(reg Sets &a,const Sets &b)
{
    a=work(merge(a,b));
}

Sets del(const Sets &a,const Sets &b)
{
    Sets c;
    reg int l=0,r=-1,n=b.size();
    for(auto &[al,ar]:a)
    {
        while(r<n-1&&b[r+1].r<=ar)++r;
        reg int p=al,i;
        for(i=l;i<=r;++i)
        {
            if(p<b[i].l)c.push_back({p,b[i].l-1});
            p=b[i].r+1;
        }
        if(p<=ar)c.push_back({p,ar});
        l=r+1;
    }
	return work(c);
}

Sets sub[N],subk[N][4],upk[N][4],linek[N][4],pointk[N][4];

void dfs4(reg int u)
{
    sub[u].push_back({dfn[u],dfn[u]});
    subk[u][0]=sub[u];
    for(auto v:G[u])if(v!=fa[u])
    {
        dfs4(v),ins(sub[u],sub[v]),upk[v][0].push_back({dfn[u],dfn[u]});
        for(reg int i=1;i<=B;++i)ins(subk[u][i],subk[v][i-1]);
    }
    Sets tmp[4];
    std::vector<int>P;
    for(auto v:G[u])if(v!=fa[u])P.push_back(v);
    for(reg int i=0;i<=B;++i)tmp[i].clear();
    for(auto v:P)for(reg int i=1;i<=B;++i)
        ins(upk[v][i],tmp[i]),ins(tmp[i],subk[v][i-1]);
    std::reverse(P.begin(),P.end());
    for(reg int i=0;i<=B;++i)tmp[i].clear();
    for(auto v:P)for(reg int i=1;i<=B;++i)
        ins(upk[v][i],tmp[i]),ins(tmp[i],subk[v][i-1]);
}

void dfs5(reg int u)
{
    for(reg int i=0;i<=B;++i)linek[u][i]=subk[u][i];
    for(reg int i=0;i<=B;++i)ins(linek[u][i],linek[fa[u]][i]);
    for(reg int i=0,j,v;i<=B;++i)
    {
        pointk[u][i]=subk[u][i];
        for(j=1,v=u;j<=i&&v;++j,v=fa[v])
            ins(pointk[u][i],upk[v][i-j]);
    }
    for(reg int i=1;i<=B;++i)ins(pointk[u][i],pointk[u][i-1]);
    for(auto v:G[u])if(v!=fa[u])dfs5(v);
}

Sets split(reg int x,reg int y,reg int k)
{
    reg int z=lca(x,y);
    return work(merge(pointk[z][k],merge(del(linek[x][k],linek[z][k]),del(linek[y][k],linek[z][k]))));
}

IL void cmax(reg int &x,reg int y){x<y?x=y:0;}

main()
{
    n=read(),q=read();
    for(reg int i=1;i<n;++i)add(read(),read());
    Segment::build(1,1,n);
    dfs1(1),dfs2(1,1),dfs3(1),dfs4(1),dfs5(1);
    for(reg int op,x,y,k,w;q--;)
    {
        op=read(),x=read();
        if(op==1)
        {
            y=read(),k=read(),w=read();
            auto P=split(x,y,k);
            for(auto &[l,r]:P)
                Segment::modify(1,l,r,w);
        }else if(op==2)
        {
            w=read();
            auto P=sub[x];
            for(auto &[l,r]:sub[x])
                Segment::modify(1,l,r,w);
        }else if(op==3)
        {
            y=read(),k=read();
            auto P=split(x,y,k);
            reg u64 res=0;
            for(auto &[l,r]:P)
                res+=Segment::query_sum(1,l,r);
            printf("%llu\n",res);
        }else
        {
            auto P=sub[x];
            reg u64 res=0;
            for(auto &[l,r]:P)
                res+=Segment::query_sum(1,l,r);
            printf("%llu\n",res);            
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 47ms
memory: 99968kb

input:

5000 5000
1 2
2 3
3 4
4 5
5 6
5 7
6 8
7 9
9 10
8 11
11 12
12 13
12 14
14 15
15 16
16 17
16 18
18 19
18 20
20 21
20 22
22 23
23 24
23 25
23 26
26 27
27 28
28 29
27 30
30 31
29 32
32 33
33 34
32 35
35 36
36 37
35 38
36 39
38 40
38 41
41 42
42 43
43 44
42 45
44 46
45 47
47 48
48 49
48 50
49 51
51 52
52...

output:

37227703492
2136305359188
2794367845468
1309925069860
1698169768858
2678958746332
6690595071246
2087826052960
4609511200067
18446744071601176942
3070072273956
1674542130
18446744071644275572
3104008526682
6341679964408
6006235988917
492570862
1127140172874
18446744072249278599
1844394554862
10080496...

result:

wrong answer 9th numbers differ - expected: '5786332239171', found: '4609511200067'

Subtask #2:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 1837ms
memory: 310952kb

input:

200000 200000
1 2
1 3
1 4
3 5
1 6
1 7
7 8
8 9
2 10
1 11
5 12
1 13
7 14
10 15
2 16
7 17
11 18
5 19
5 20
1 21
16 22
1 23
3 24
20 25
14 26
2 27
6 28
15 29
10 30
15 31
5 32
13 33
12 34
31 35
31 36
36 37
36 38
1 39
28 40
5 41
12 42
41 43
20 44
30 45
22 46
11 47
47 48
45 49
14 50
41 51
3 52
30 53
29 54
6 ...

output:

0
0
0
0
0
0
0
0
18446744072734690831
18446744073591495375
0
450687552
1927878522
0
0
1149208227
0
1424960716
929851494
5164351707
5127988881
4378093568
0
7315230368
0
0
9587792729
0
0
0
2747489046
8130683507
0
0
6896529180
0
29007569401
0
0
10869684653
10573808086
11264705820
0
12096061596
0
1143179...

result:

wrong output format Expected int64, but "18446744072734690831" found

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 616ms
memory: 274744kb

input:

200000 200000
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 51
51 ...

output:

0
134315201201061
38210069287857
75889674481730
25202765567748
179527420359031
75824479907233
153597207731803
236446702840007
241320278942639
129801336365495
234078161952004
203137132572663
166436235677589
53329676365026
451665818220
251649034404466
352771307201073
398863165818562
115602278279937
13...

result:

wrong answer 8th numbers differ - expected: '156951577189979', found: '153597207731803'

Subtask #4:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 1355ms
memory: 315848kb

input:

200000 200000
1 2
2 3
3 4
1 5
3 6
5 7
5 8
7 9
2 10
7 11
11 12
10 13
6 14
3 15
14 16
4 17
11 18
3 19
14 20
4 21
4 22
12 23
18 24
5 25
5 26
14 27
13 28
24 29
11 30
26 31
29 32
28 33
31 34
23 35
33 36
6 37
11 38
22 39
13 40
35 41
37 42
21 43
12 44
4 45
16 46
12 47
21 48
1 49
26 50
45 51
41 52
46 53
7 5...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 35677th numbers differ - expected: '4874907829', found: '579940533'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #2:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%