Eternity

Until The End

数据结构2022.03.20练习

发表于 更新于 分类于
本文字数： 5.8k 阅读时长 ≈ 5 分钟

结果：C Accepted

改题进度：BC Accepted

Task One——Tree

始终不得求解

Task Two——普通计算姬(common)

题目链接

思路

求出该树的 $dfs$ 序。对于每一次询问，用树状数组或者线段树维护即可。对于修改，部分分做法即是对树状数组进行暴力修改。然而这样只能得 $90pt$ 。然后将整个 $dfs$ 序的序列进行分块，记录每一个点对每一个序列的贡献，修改序列和即可。最后一个点会爆 $long \ long$ ，需要开 $ull$

AC Code

查看代码 
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
#define ls p<<1
#define rs p<<1|1
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAXN=1e5+1;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N,M,u,v,op,Qf,Qs,Rt,Idx,Blo;
struct edge
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total,cnt[MAXN],pos[MAXN],r[MAXN][401];
ull Val[MAXN],Tre[MAXN],sum[MAXN];
struct Segment
{
    int l,r;
}Seg[MAXN];
inline void underAddEdge(int u,int v)
{
    Edge[++Total]=(edge){Head[u],v};Head[u]=Total;
    Edge[++Total]=(edge){Head[v],u};Head[v]=Total;
}
inline void underDfs(int x,int last)
{
    Seg[x].l=++Idx;++cnt[pos[x]];
    for(int i=1;i<=Blo;++i) r[x][i]=cnt[i];
    for(int e=Head[x];e;e=Edge[e].next)
    {
        int v=Edge[e].to;
        if(v!=last) underDfs(v,x);
    }
    Seg[x].r=Idx;--cnt[pos[x]];
}
inline int underLowbit(int x)
{
    return x&(-x);
}
inline void underAdd(int x,ull val)
{
    for(;x<=N;x+=underLowbit(x)) Tre[x]+=val;
}
inline ull underQuery(int x)
{
    ull ans=0;
    for(;x>=1;x-=underLowbit(x)) ans+=Tre[x];
    return ans;
}
inline ull underCalc(int l,int r)
{
    return underQuery(r)-underQuery(l-1);
}
inline void underInitBlock()
{
    int block=sqrt(N);
    Blo=(N%block)?(N/block+1):(N/block);
    for(int i=1;i<=N;++i) pos[i]=(i-1)/Blo+1;
}
inline void underUpdate(int x,ull k)
{
    for(int i=1;i<=Blo;++i) sum[i]+=(ull)r[x][i]*k;
    underAdd(Seg[x].l,k);
}
inline ull underAns(int l,int r)
{
    ull res=0;
    if(pos[r]-pos[l]<=1)
    {
        for(int i=l;i<=r;++i) res+=underCalc(Seg[i].l,Seg[i].r);
        return res;
    }
    for(int i=l;i<=pos[l]*Blo;++i) res+=underCalc(Seg[i].l,Seg[i].r);
    for(int i=pos[l]+1;i<=pos[r]-1;++i) res+=sum[i];
    for(int i=(pos[r]-1)*Blo+1;i<=r;++i) res+=underCalc(Seg[i].l,Seg[i].r);
    return res;
}
int main()
{
    freopen("common.in","r",stdin);
    freopen("common.out","w",stdout);
    underRead(N),underRead(M);
    underInitBlock();
    for(re int i=1;i<=N;++i) underRead(Val[i]);
    for(re int i=1;i<=N;++i)
    {
        underRead(u),underRead(v);
        if(!u) Rt=v;
        else if(!u) Rt=u;
        else underAddEdge(u,v);
    }
    underDfs(Rt,-1);
    for(int i=1;i<=N;++i) underUpdate(i,Val[i]);
    while(M--)
    {
        underRead(op),underRead(Qf),underRead(Qs);
        if(op==1)
        {
            underUpdate(Qf,Qs-Val[Qf]);
            Val[Qf]=Qs;
        }
        else printf("%llu\n",underAns(Qf,Qs));
    }
    return 0;
}
/*
6 4
0 0 3 4 0 1
0 1
1 2
2 3
2 4
3 5
5 6
2 1 2
1 1 1
2 3 6
2 3 5
*/

Task Three——文艺计算姬(art)

题目链接

思路

暴力取一些比较小的点，然后推公式。毕竟 $1 \leq n,m \leq 10^{18}$ 。

然后推得公式为 $ans=n^{m-1}m^{n-1}$ 。然后用快速幂即可。注意 $1e18*1e18$ 会爆 $long\ long$ 。所以需要快速乘。

AC Code

查看代码 
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
ll N,M,P,tot,ans;
int fa[MAXN<<1];
inline void underInit(int n,int m)
{
    for(int i=1;i<=n+m;++i) fa[i]=i;
}
inline int underFind(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=underFind(fa[x]);
}
inline void underD(int n,int m,int edge)
{
    if(edge==n+m-1)
    {
        ++ans;
        return ;
    }
    for(re int i=1;i<=n;++i)
    {
        for(re int j=n+1;j<=m;++j)
        {
            if(underFind(i)!=underFind(j))
            {
                int p1=underFind(i),p2=underFind(j);
                fa[p1]=p2;
                underD(n,m,edge+1);
                fa[p1]=p1;
            }
        }
    }
}
inline ll underSmi(ll a,ll b,ll p)
{
    ll res=0;
    while(b>0)
    {
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
        // printf("%lld %lld %lld\n",a,b,res);
    }
    return res;
}
inline ll underQmi(ll a,ll b,ll p)
{
    ll res=1;
    while(b>0)
    {
        if(b&1) res=underSmi(res,a,p)%p;
        a=underSmi(a,a,p)%p;
        b>>=1;
    }
    return res;
}
int main()
{
    freopen("art.in","r",stdin);
    freopen("art.out","w",stdout);
    underRead(N),underRead(M),underRead(P);
    printf("%lld",underSmi(underQmi(N,M-1,P),underQmi(M,N-1,P),P));
    // printf("%lld %lld\n",N,M);
    /*for(re int i=1;i<=N;++i)
    {
        for(re int j=1;j<=M;++j)
        {
            underInit(i,j);
            underD(i,j,0);
            printf("%d,%d=%lld\n",i,j,ans);
        }
    }*/
    return 0;
}
/*
1,1=1
1,2=1
2,2=4
2,3=12
2,4=32
3,1=1
3,2=12

f(n,m)=n^(m-1)*m^(n-1)
*/
相关文章