QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#767736#7767. 数据结构zhouhuanyi0 0ms0kbC++177.2kb2024-11-20 21:57:272024-11-20 21:57:32

Judging History

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

  • [2024-11-20 21:57:32]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-20 21:57:27]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 200000
using namespace std;
int read()
{
	char c=0;
	int sum=0,f=1;
	while (c!='-'&&(c<'0'||c>'9')) c=getchar();
	if (c=='-') c=getchar(),f=-1;
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum*f;
}
struct reads
{
	int l,r;
};
reads operator + (reads a,reads b)
{
	return (reads){min(a.l,b.l),max(a.r,b.r)};
}
struct lines
{
	int x,y,data;
	bool operator < (const lines &t)const
	{
		return data<t.data;	
	}
};
lines dque[N+1];
int n,m,tops,dfn[N+1],leng,depth[N+1],rev[N+1],rev2[N+1],sz[N+1],top[N+1],fa[N+1],hs[N+1],num[N+1],length;
__int128 ans;
bool used[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<int>p[N+1][4];
vector<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[N+1];
bool cmp(int x,int y)
{
	return num[x]<num[y];
}
vector<reads>operator + (vector<reads>a,vector<reads>b)
{
	if (a.empty()) return b;
	if (b.empty()) return a;
	int ps=0,ps2=0;
	reads d=(reads){0,-1};
	vector<reads>sp;
	while (ps<a.size()||ps2<b.size())
	{
		if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
		{
			if (d.r+1>=a[ps].l) d=d+a[ps];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=a[ps];
			}
			ps++;
		}
		else
		{
			if (d.r+1>=b[ps2].l) d=d+b[ps2];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=b[ps2];
			}
			ps2++;
		}
	}
	sp.push_back(d);
	return sp;
}
vector<reads>operator * (vector<reads>a,vector<reads>b)
{
	if (a.empty()) return b;
	if (b.empty()) return a;
	int ps=0,ps2=0;
	reads d=(reads){0,-1};
	vector<reads>sp;
	while (ps<a.size()||ps2<b.size())
	{
		if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
		{
			if (d.r+1>=a[ps].l) d=d+a[ps];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=a[ps];
			}
			ps++;
		}
		else
		{
			if (d.r+1>=b[ps2].l) d=d+b[ps2];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=b[ps2];
			}
			ps2++;
		}
	}
	sp.push_back(d);
	if (sp.size()>=40) sp.clear(),sp.shrink_to_fit();
	return sp;
}
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	used[x]=sz[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		{
			fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,ES[x].push_back(E[x][i]),dfs(E[x][i]),sz[x]+=sz[E[x][i]];
			if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
		}
	return;
}
void dfs2(int x)
{
	dfn[x]=++leng,rev[dfn[x]]=x;
	if (ES[x].empty()) dque[++tops]=(lines){top[x],x,depth[top[x]]};
	if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
	for (int i=0;i<ES[x].size();++i)
		if (ES[x][i]!=hs[x])
			top[ES[x][i]]=ES[x][i],dfs2(ES[x][i]);
	return;
}
void dfs3(int x)
{
	for (int i=0;i<ES[x].size();++i)
	{
		if (ES[x][i]==hs[x])
		{
			for (int j=0;j<=3;++j) DP[ES[x][i]][j]=DP[ES[x][i]][j]+DP[x][j];
		}
		dfs3(ES[x][i]),DP2[x]=DP2[x]+DP2[ES[x][i]];
	}
	return;
}
struct seg
{
	struct node
	{
		int l,r;
		vector<reads>data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data*tree[k<<1|1].data;
		return;
	}
	void build(int k,int l,int r,int d)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r)
		{
			tree[k].data=dp[rev[l]][d];
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid,d),build(k<<1|1,mid+1,r,d),push_up(k);
		return;
	}
	vector<reads>query(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return query(k<<1,l,r);
		else if (l>=mid+1) return query(k<<1|1,l,r);
		else return query(k<<1,l,mid)*query(k<<1|1,mid+1,r);
	}
};
seg T[4];
struct seg2
{
	struct node
	{
		int l,r;
		long long lazy;
		__int128 data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
		return;
	}
	void push_tag(int k,long long d)
	{
		tree[k].lazy+=d,tree[k].data+=(__int128)(d)*(tree[k].r-tree[k].l+1);
		return;
	}
	void spread(int k)
	{
		if (tree[k].lazy!=0) push_tag(k<<1,tree[k].lazy),push_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;
		return;
	}
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
		return;
	}
	void add(int k,int l,int r,int d)
	{
		if (tree[k].l==l&&tree[k].r==r)
		{
			push_tag(k,d);
			return;
		}
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) add(k<<1,l,r,d);
		else if (l>=mid+1) add(k<<1|1,l,r,d);
		else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
		push_up(k);
		return;
	}
	__int128 query(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return query(k<<1,l,r);
		else if (l>=mid+1) return query(k<<1|1,l,r);
		else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
	}
};
seg2 T2;
vector<reads>get_path(int x,int y,int k)
{
	vector<reads>sp;
	while (top[x]!=top[y])
	{
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		sp=sp+DP[x][k],x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	sp=sp+T[k].query(1,dfn[x],dfn[y]);
	return sp;
}
void write(__int128 d)
{
	if (!d) return;
	write(d/10),printf("%d",(int)(d%10));
	return;
}
void output(__int128 d)
{
	if (d>0) write(d),puts("");
	else if (d==0) puts("0");
	else printf("-"),write(-d),puts("");
	return;
}
int main()
{
	int opt,x,y,d,k;
	vector<reads>sp;
	n=read(),m=read();
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	depth[1]=1,dfs(1);
	for (int i=1;i<=n;++i)
	{
		x=i;
		for (int j=0;j<=3;++j)
		{
			if (x) p[x][j].push_back(i);
			x=fa[x];
		}
	}
	top[1]=1,dfs2(1),sort(dque+1,dque+tops+1);
	for (int i=1;i<=tops;++i)
	{
		x=dque[i].x;
		while (x)
		{
			if (!num[x]) num[x]=++length;
			x=hs[x];
		}
		for (int j=0;j<=2;++j)
		{
			x=dque[i].x;
			while (x)
			{
				for (int k=0;k<E[x].size();++k)
					if (E[x][k]!=hs[x])
					{
						for (int t=0;t<p[ES[x][k]][j].size();++t)
							if (!num[p[ES[x][k]][j][t]])
								num[p[ES[x][k]][j][t]]=++length;
					}
				x=hs[x];
			}
		}
	}
	for (int i=1;i<=n;++i) dp[i][0]={(reads){num[i],num[i]}},rev2[num[i]]=i;
	for (int i=1;i<=n;++i) sort(E[i].begin(),E[i].end(),cmp);
	for (int i=1;i<=3;++i)
		for (int j=1;j<=n;++j)
		{
			dp[j][i]=dp[j][i-1];
			for (int t=0;t<E[j].size();++t) dp[j][i]=dp[j][i]+dp[E[j][t]][i-1];
		}
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<=3;++j) DP[i][j]=dp[i][j];
		DP2[i]=dp[i][0];
	}
	dfs3(1);
	for (int i=0;i<=3;++i) T[i].build(1,1,n,i);
	T2.build(1,1,n);
	for (int qt=1;qt<=m;++qt)
	{
		opt=read();
		if (opt==1)
		{
			x=read(),y=read(),k=read(),d=read(),sp=get_path(x,y,k);
			for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
		}
		else if (opt==2)
		{
			x=read(),d=read(),sp=DP2[x];
			for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
		}
		else if (opt==3)
		{
			x=read(),y=read(),k=read(),sp=get_path(x,y,k),ans=0;
			for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
			printf("%llu\n",(unsigned long long)(ans));
		}
		else
		{
			x=read(),sp=DP2[x],ans=0;
			for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
			printf("%llu\n",(unsigned long long)(ans));
		}
	}
	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:

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:


result:


Subtask #2:

score: 0
Runtime Error

Test #3:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Runtime Error

Test #5:

score: 0
Runtime Error

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:


result:


Subtask #4:

score: 0
Runtime Error

Test #7:

score: 0
Runtime Error

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:


result:


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%