• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

义乌集训7.18 contest 11题解

admin

11月 28, 2021

2021.7.17 Contest 题解

T1:

Description:

​ 白云列出了一个方程:

(x^2 − 2Bx + C = 0)

​ 白兔给出了一个区间 ([L,R]),要求参数 (C) 必须在这个区间内。

​ 白云想知道,有多少组满足要求的正整数 ((B,C)) 使得这个方程有整数解。

Input:

​ 第一行数据组数 (T)

​ 接下来 (T) 行每行两个数 (L,R)

Output:

​ 对于每个询问输出答案。

Sample1 Input:

2
1 5
2 10

Sample1 Output:

4
7

Hint:

data range:

对于 (30\%) 的数据,(R le 1000)

对于 (60\%) 的数据,(R le 10^6)

对于 (100\%) 的数据,(1 le L le R le 10^{12},T le 10)

sample explaination:

第一问,合法的为 ((1,1),(2,3),(2,4),(3,5))

第二问,合法的为 ((2,3),(2,4),(3,5),(4,7),(3,8),(3,9),(5,9))

题目分析:

​ 稍微转变一下题意,就是让我们求 ((B^2-C)) 为完全平方数的 ((B,C)) 二元组。

​ 令 (B^2-C=P^2) ,则 ((B+P)*(B-P)=C),由于 (C in [L,R]),所以 ((B-P) in [0,sqrt{C}]),不妨枚举 ((B-P)),就能求出所有合法的 (C),于是这道题就结束了。

​ 但是我写的不是这个方法。我们考虑满足 ((B+P)*(B-P)=C)((B,P)) 二元整数组一定是这样构造的:

​ 令 (C=X*Y) ,则 (B=frac{X+Y}{2}),也就是说对于每一个 (C) 求出它拆分成两个约数相乘,且两个约数奇偶性相同的方案。

​ 若 (C) 为奇数,则 (X,Y) 一定都是奇数,于是对于奇数只需要求出约数个数和即可;

​ 若 (C)(2) 的倍数且不为 (4) 的倍数,则 (X,Y) 必为一奇一偶,不符合条件;

​ 若 (C)(4) 的倍数,则不妨令 (frac{C}{4}=frac{X}{2}*frac{Y}{2}),问题转化为 (frac{C}{4}) 的约数个数和;

​ 稍微用一些容斥的技巧,跑一遍数论分块即可。

代码如下(马蜂很丑,不喜勿喷)——

#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int T;LL L,R; inline LL calc(LL n){
	LL res=0;for(register LL i=1,j;i<=n;i=j+1) j=n/(n/i),res+=(n/i)*((((((j&1ll)?j:(j-1))-((i&1ll)?i:(i+1)))>>1ll)+1ll)-(((j-(j&1ll)-(i+(i&1ll)))>>1ll)+1ll)+((j-(j%4ll)-((i%4ll)?(i+4ll-i%4ll):i))/4ll+1ll));
	res+=(sqrt(n)+1ll)/2ll,res>>=1ll;LL res2=0;n/=4ll;for(register LL i=1,j;i<=n;i=j+1) j=n/(n/i),res2+=(j-i+1ll)*(n/i);res2+=sqrt(n),res2>>=1ll;return res+res2; 
}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
	fin>>T;while(T--) fin>>L>>R,cout<<calc(R)-calc(L-1)<<'
';return 0;
}

T2:

Description:

​ 白云有一个长度为 (n) 的序列 (a_1,…,a_n)

​ 白兔想找到这个序列的一些非空子序列。因为这些子序列多达 (2^n −1) 个,所以它只 需要字典序最小的 (k) 个。

​ 两个序列的字典序的比较方式为:如果一个序列是另一个的前缀,则长度小的序列字典序小,否则找到两个序列从前往后第一个不同的元素,这个元素小的序列字典序小。

​ 为了避免大量输出,对于每一个子序列你只需要输出它的哈希值。一个序列 (b_1,…,b_m) 的哈希值为 (sum_{i=1}^mb_iseed^{m-i}mod p)

Input:

​ 第一行四个数 (n,k,seed,p)

​ 第二行 (n) 个数表示这个序列。

Output:

​ 输出 (k) 行,表示前 (k) 小的子序列的哈希值

Sample1 Input:

2 3 1 5
1 2

Sample1 Output:

1
3
2

Sample2 Input:

3 4 2 3
1 3 1

Sample2 Output:

1
1
0
2

Sample3 Input:

5 6 23 1000
1 2 4 2 3

Sample3 Output:

1
25
25
577
274
578

Hint:

data range:

对于 (20\%) 的数据,(nle15)

对于 (30\%) 的数据,(nle2000)

对于 (40\%) 的数据,(nle10^4)

对于 (60\%) 的数据,(1le a_ile30)

对于 (100\%) 的数据,(1le n,k,a_ile 10^5,1le seed,ple 10^6,kle 2^n-1)

题目分析:

​ 由于 (k) 比较小,我们考虑通过搜索直接从小到大地找出每个子序列。

​ 首先我们找到全局最小值,然后用 (vector) 记录下所有全局最小值的位置,然后以第一个位置+1为起点往下递归,每两层递归之间用 two-pointers 扫一遍 (vector) 来算出以每个数字结尾有多少贡献,对于每一层都开一个 (vector) 存储。

​ 回溯的时候把最小值删除求剩余的次小值,这个过程可以用主席树实现,但是我太懒了,于是写了个 (set) + (st表) 实现了一个复杂度显然不正确但是很难被卡掉的算法。

代码如下(马蜂很丑,不喜勿喷)——

#include<bits/stdc++.h>
#define N 200005
#define LL long long
#define s_id set<int>::iterator
#define inf 2147483647
using namespace std;
int n,K,top,seed,p,tot,tmp=1,a[N],ST[N][20],pw[N],P[20];vector<int> g[N],G[N];set<int> T[N];
inline int get(int x,int y){int len=log2(y-x+1);if(a[ST[x][len]]<=a[ST[y-P[len]+1][len]]) return ST[x][len];return ST[y-P[len]+1][len];}
inline void solve(int H){
	int TMP=tmp,s=G[TMP][0];if(s==n) return;int x=a[get(s+1,n)],ss=G[TMP].size(),sum=0;H=1ll*H*seed%p,T[TMP].insert(G[TMP][0]),T[TMP].insert(n+1);while(sum<n-s){
		int S=g[x].size(),now=0;for(register int i=0;i<S;i++) if(g[x][i]>s){
			int pos=g[x][i];T[TMP].insert(pos),sum++;while(now<ss&&G[TMP][now]<pos) now++;now--;
			for(register int j=0;j<=now;j++){K--,cout<<(H+x)%p<<'
';if(!K) exit(0);G[tmp+1].push_back(pos);} 
		}
		if(G[tmp+1].size()) tmp++,solve((H+x)%p);int y=inf;for(s_id it=T[TMP].begin();it!=T[TMP].end();it++){int posx=*it+1;if(posx==n+2) break;s_id itt=it;itt++;int posy=*itt-1;if(posx<=posy){int tt=a[get(posx,posy)];y=min(y,tt);}}x=y;
	}
}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
	fin>>n>>K>>seed>>p,pw[0]=1;for(register int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*seed%p;P[0]=1;for(register int i=1;i<=16;i++) P[i]=P[i-1]*2;
	for(register int i=1;i<=n;i++) fin>>a[i],g[a[i]].push_back(i),ST[i][0]=i;
	for(register int i=1;i<=16;i++) for(register int j=1;j<=n-P[i]+1;j++) if(a[ST[j][i-1]]<=a[ST[j+P[i-1]][i-1]]) ST[j][i]=ST[j][i-1];else ST[j][i]=ST[j+P[i-1]][i-1];G[1].push_back(0),solve(0);return 0;
}

T3:

Description:

白云和白兔想占领一棵树。

白云列举了游戏玩法:

首先,白云任意选择一个结点 (k),把这个结点占领,其它结点都未被占领。
每一轮,白云可以选择若干个已经被占领的点,然后分别从每个点出发,找一条出边,把到达的结点占领。
当所有结点都被占领时游戏结束。

白兔想知道,选择一个最优的 (k),白云最少几轮可以完成游戏。

接下来白云和白兔想一起玩游戏,规则是这样:

一开始,白云选择了 (a) 号点,白兔选择了 (b) 号点,这两个结点都被占领,其它点都未被占领。
每一轮,白兔可以选择若干个已经被占领的点,然后分别从每个点出发,找任意一条出边,把到达的结点占领。
当所有结点都被占领时游戏结束。

白兔还想知道,最小多少轮可以占领所有结点?注意,这个游戏的 (a)(b) 是固定的。

Input:

​ 第一行三个数 (n,a,b)

​ 接下来 (n-1) 行每行两个数表示这棵树。

Output:

​ 输出两行,第一行是第一个游戏的答案,第二行是第二个游戏的答案。

Sample1 Input:

6 2 1
1 2
2 3
2 4
1 5
5 6

Sample1 Output:

3
2

Hint:

对于 (30\%) 的数据,(n le 100)

对于 (100\%) 的数据,(n le 10^5, a, b in [1, n], a
e b)

题目分析:

​ 第一个游戏一眼看去就是个换根DP套路题,注意换根的时候用前后缀优化,不然复杂度会退化成 (O(n^2))

​ 第二个游戏看起来有浓浓的二分性。我们二分在 (a)(b) 的路径上断开某一条边,分别以 (a)(b) 为根跑一遍树形DP,如果 (a) 需要的轮数比 (b) 多,就把断开的那条边向 (a) 的方向移动;反之向 (b) 的方向移动。

​ 由于函数单调,正确性显然。

代码如下(马蜂很丑,不喜勿喷)——

#include<bits/stdc++.h>
#define N 300005
#define LL long long
#define inf 2147483647
using namespace std;
int n,a,b,tot,ans=inf,g[N],rk[N],A[N],f[N],F[N],W[N],fir[N],nxt[N<<1],son[N<<1],pre[N],suf[N],B[N];
inline void add(int x,int y){son[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;} inline bool cmp(int x,int y){return x>y;} inline void dfs(int x,int fa){
	for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) dfs(son[i],x);tot=0;for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) A[++tot]=f[son[i]];
	sort(A+1,A+tot+1,cmp);for(register int i=1;i<=tot;i++) f[x]=max(f[x],A[i]+i);
}
inline void dfs2(int x,int fa,int X){
	tot=0,A[++tot]=X;for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) A[++tot]=f[son[i]];
	sort(A+1,A+tot+1,cmp);for(register int i=1;i<=tot;i++) pre[i]=max(pre[i-1],i+A[i]),(A[i]>=0)&&(rk[A[i]]=i,0);suf[tot+1]=-n;for(register int i=tot;i;i--) suf[i]=max(suf[i+1],i-1+A[i]);
	ans=min(ans,pre[tot]);for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa){int to=son[i],tmp=max(suf[rk[f[to]]+1],pre[rk[f[to]]-1]);g[to]=tmp;}
	for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) dfs2(son[i],x,g[son[i]]);
}
inline void DFS(int x,int fa){for(register int i=fir[x];i;i=nxt[i]) if(son[i]^fa) W[son[i]]=i,F[son[i]]=x,DFS(son[i],x);}
inline void check(int x,int fa,int id){
	for(register int i=fir[x];i;i=nxt[i]) if((son[i]^fa)&&(i^id)&&((i^1)^id)) check(son[i],x,id);tot=0;for(register int i=fir[x];i;i=nxt[i]) if((son[i]^fa)&&(i^id)&&((i^1)^id)) A[++tot]=f[son[i]];
	sort(A+1,A+tot+1,cmp),f[x]=0;for(register int i=1;i<=tot;i++) f[x]=max(f[x],A[i]+i);
}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
	fin>>n>>a>>b,tot=1;for(register int i=1,x,y;i<n;i++) fin>>x>>y,add(x,y),add(y,x);dfs(1,0),ans=f[1],dfs2(1,0,-n);cout<<ans<<'
';
	DFS(a,0);int x=b,res=0;while(x^a) B[++res]=W[x],x=F[x];int l=1,r=res;ans=inf;while(l<=r){int mid=l+r>>1;check(a,0,B[mid]),check(b,0,B[mid]);ans=min(ans,max(f[a],f[b]));if(f[a]>=f[b]) l=mid+1;else r=mid-1;}
	cout<<ans<<'
';return 0;
}

T4:

Description:

​ 特别提醒:本题时间限制只有 5.0s。

内鬼 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一一棵包含 (n) 个结点和 (n-1) 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 (1)(n) 的连续正整数。

现在有 (m) 个玩家,第 (i) 个玩家的起点为 (s_i),终点为 (t_i)。每天打卡任务开始时,所有玩家在第 (0) 秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去,跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树,所以每个人的路径是唯一的)

内鬼 想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点 (j) 的观察员会选择在第 (w_j) 秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第 (w_j) 秒也正好到达了结点 (j)内鬼 想知道每个观察员会观察到多少人?

注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一 段时间后再被观察员观察到。 即对于把结点 (j) 作为终点的玩家:若他在第 (w_j) 秒前到达终点,则在结点 (j) 的观察员不能观察到该玩家;若他正好在第 (w_j) 秒到达终点,则在结点 (j) 的观察员可以观察到这个爪巴者内鬼。 ——《P1600 [NOIP2016 提高组 ] 天天爱跑步

​ 但是这个游戏是在是太难了,所以游戏还增加了氪金的功能,具体来说,某人使用了钞能力之后,可以对地图上的边进行修改,删除边 ((a,b)),并添加边 ((c,d)),同时,为了维持服务器正常运行,保证地图仍然是一棵树。随着树形态的变化,内鬼 为了更全面地了解活跃度,决定在某些时刻修改某个 (W_j)

Input:

​ 输入第一行包含两个正整数 (n,m),其中 (n) 代表结点的数量,同时也是观察员的数量,(m) 代表事件的数量。

​ 接下来 (n−1) 行,每行两个数 (a,b),描述这棵树。 接下来一行 (n) 个数,表示每个观察员的初始 (W) 值。

​ 接下来 (m) 行,每行描述一个事件,有三种形式:

1 a b: 表示新的一天开始了,有一个玩家在时刻 (0)(a) 沿最短路径跑到 (b)

2 a b c d: 表示某人投了币,把边 ((a,b)) 替换为了边 ((c,d))。保证 ((a,b)) 边存在,并且替换结束后仍然是一棵树。

3 a b: 表示内鬼决定把 (a) 号观察员的 (W) 修改为 (b)

Output:

​ 输出仅包含 (1)(n) 个数,第 (j) 个整数表示结点 (j) 的观察员可以观察到多少人。

Sample1 Input:

6 5
2 3
1 2
1 4
4 5
5 6
1 2 5 1 2 3
2 6 5 6 4
3 1 0
1 1 5
1 1 3
1 2 6

Sample1 Output:

2 0 0 1 1 1

Hint:

对于 (20\%) 的数据无操作 (2、3)

对于另 (20\%) 的数据无操作 (2)

对于另 (20\%) 的数据无操作 (3)

对于另 (20\%) 的数据所有玩家经过的路径总长 (le 10^8)

对于 (100\%) 的数据 (n,m le 10^5)

题目分析:

​ 考场上看到这道题就知道是道大毒瘤数据结构题。于是我们开始扣部分分。

​ 无操作 (2、3) 就是天天爱跑步原题,直接上线段树合并;(事实上其实不需要线段树合并,可以用 (LCA) + 树上差分来实现)

​ 路径总长 (leq 10^8) 直接拉一棵 (LCT) 来暴力维护;

​ 由于博主太菜了,暂时没有想到第 (2,3) 个数据点怎么艹,欢迎大家踊跃留言告诉我。

​ 正解:考虑分块。我们将询问分块,设块长为 (sqrt{n}) ,每 (sqrt{n}) 次操作之后直接暴力重构,块内操作考虑加入未删除的边,原来的一棵树就变成了一棵森林,而森林的总大小为 (n),对于森林重新 dfs 一遍扫答案,同时注意 (W_i) 的更新以及 (a)(b) 的实际路径,实现难度很高。

​ 最终复杂度 (O(nsqrt{n} logn))虽然常数巨大但是能把暴力艹掉

20分代码如下(马蜂很丑,不喜勿喷)——

#include<bits/stdc++.h>
#define s_id vector<int>::iterator
#define N 200005
using namespace std;
int tim,n,m,tot,tott,size,C[N],D[N],op[N],ans[N],sum[N*100],sum2[N*100],son[N*100][2],son2[N*100][2],rt[N],rt2[N],dep[N],fir[N],nxt[N<<1],to[N<<1],w[N],f[N][20],s[N],t[N];vector<int> g;
inline void add(int x,int y){to[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;}
inline void dfs(int x){
	dep[x]=dep[f[x][0]]+1;for(register int i=1;i<=18;i++) f[x][i]=f[f[x][i-1]][i-1];
	for(register int i=fir[x];i;i=nxt[i])
	if(to[i]!=f[x][0]) f[to[i]][0]=x,dfs(to[i]);
}
inline int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);for(register int i=18;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;for(register int i=18;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}
inline void modify(int &now,int l,int r,int x,int v){
	if(!now) now=++tot;if(l==r){sum[now]+=v;return;}
	int mid=l+r>>1;if(mid>=x) modify(son[now][0],l,mid,x,v);
	else modify(son[now][1],mid+1,r,x,v);sum[now]=sum[son[now][0]]+sum[son[now][1]];
}
inline void merge(int &now,int last,int l,int r){
	if(!now){now=last;return;}else sum[now]+=sum[last];if(l==r) return;
	int mid=l+r>>1;if(son[last][0]) merge(son[now][0],son[last][0],l,mid);
	if(son[last][1]) merge(son[now][1],son[last][1],mid+1,r);
}
inline void modify2(int &now,int l,int r,int x,int v){
	if(!now) now=++tott;if(l==r){sum2[now]+=v;return;}
	int mid=l+r>>1;if(mid>=x) modify2(son2[now][0],l,mid,x,v);
	else modify2(son2[now][1],mid+1,r,x,v);sum2[now]=sum2[son2[now][0]]+sum2[son2[now][1]];
}
inline void merge2(int &now,int last,int l,int r){
	if(!now){now=last;return;}else sum2[now]+=sum2[last];if(l==r) return;
	int mid=l+r>>1;if(son2[last][0]) merge2(son2[now][0],son2[last][0],l,mid);
	if(son2[last][1]) merge2(son2[now][1],son2[last][1],mid+1,r);
}
inline int query(int now,int l,int r,int x){
	if(l==r) return sum[now];if(!now) return 0;
	int mid=l+r>>1;if(mid>=x) return query(son[now][0],l,mid,x);
	return query(son[now][1],mid+1,r,x);
}
inline int query2(int now,int l,int r,int x){
	if(l==r) return sum2[now];if(!now) return 0;
	int mid=l+r>>1;if(mid>=x) return query2(son2[now][0],l,mid,x);
	return query2(son2[now][1],mid+1,r,x);
}
inline void dfs2(int x){
	for(register int i=fir[x];i;i=nxt[i])
	if(to[i]!=f[x][0]) dfs2(to[i]),merge(rt[x],rt[to[i]],1,size),merge2(rt2[x],rt2[to[i]],1,size);
	int xx=lower_bound(g.begin(),g.end(),dep[x]+w[x])-g.begin()+1;
	int yy=lower_bound(g.begin(),g.end(),dep[x]-w[x])-g.begin()+1;
	ans[x]=query(rt[x],1,size,xx)+query2(rt2[x],1,size,yy);
}
inline void U(int x,int y){
	int xx=x,yy=y;if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=f[x][0];while(x^y) x=f[x][0],y=f[y][0];int z=x;
	x=xx;while(x^z){if(dep[xx]-dep[x]==w[x]) ans[x]++;x=f[x][0];}if(dep[xx]-dep[x]==w[x]) ans[x]++;
	y=yy;while(y^z){if(dep[xx]-dep[z]+dep[y]-dep[z]==w[y]) ans[y]++;y=f[y][0];}
}
inline void U2(int a,int b,int c,int d){
//	if(f[b][0]==a) swap(a,b);f[c][0]=
}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
	fin>>n>>m;for(register int i=1,x,y;i<n;i++) fin>>x>>y,add(x,y),add(y,x);dfs(1);tot=0;
	for(register int i=1;i<=n;i++) fin>>w[i],g.push_back(w[i]+dep[i]),g.push_back(dep[i]-w[i]);bool flg=1;
	for(register int i=1;i<=m;i++){
		fin>>op[i]>>s[i]>>t[i];if(op[i]!=1) flg=0;if(op[i]==2) fin>>C[i]>>D[i];int x=lca(s[i],t[i]),dis=dep[s[i]]+dep[t[i]]-2*dep[x];
		g.push_back(dep[s[i]]),g.push_back(dep[t[i]]-dis);
	}
	if(flg){
		sort(g.begin(),g.end());g.erase(unique(g.begin(),g.end()),g.end());size=g.size();
		for(register int i=1;i<=m;i++){
			int x=lca(s[i],t[i]),dis=dep[s[i]]+dep[t[i]]-2*dep[x];
			int xx=lower_bound(g.begin(),g.end(),dep[s[i]])-g.begin()+1;
			int yy=lower_bound(g.begin(),g.end(),dep[t[i]]-dis)-g.begin()+1;
			modify(rt[s[i]],1,size,xx,1),modify2(rt2[t[i]],1,size,yy,1);
			modify(rt[x],1,size,xx,-1),modify2(rt2[x],1,size,yy,-1);
		}
		dfs2(1);for(register int i=1;i<=m;i++){
			int x=lca(s[i],t[i]),xx=lower_bound(g.begin(),g.end(),dep[s[i]])-g.begin()+1;
			int yy=lower_bound(g.begin(),g.end(),dep[x]+w[x])-g.begin()+1;if(xx==yy) ans[x]++;
		}
		for(register int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;
	}
	for(register int i=1;i<=m;i++){if(op[i]==1) U(s[i],t[i]);if(op[i]==2) U2(s[i],t[i],C[i],D[i]);if(op[i]==3) w[s[i]]=t[i];}
	for(register int i=1;i<=n;i++) cout<<ans[i]<<' ';return 0;
}

正解代码如下——

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#define md double
#define LL long long
using namespace std;
const int N=3e5+100;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int head[N],next[N],to[N],n;
int Q[N],p[N],C[N],tim[N];pair<int,int>e[N],del[N];
int G[N],dep[N],fa[N],q[N],rt[N],pos[N],pre[N],L[N],R[N],dfn;
int cur[N],nxt[N],lca[N],go[N],d[N];
int Cur[N],Nxt[N],Go[N],D[N];
int s1[N],s2[N],ans[N];
int op[N],oa[N],ob[N],oc[N],od[N];
int Qu[N],Qv[N],Qs[N];
bool use[N],end[N],die[N];
inline int find(int x) { return G[x]==x?x:G[x]=find(G[x]); }
inline void dfs(int k) {
	G[k]=k;L[k]=++dfn;
	for (int i=cur[k];i;i=nxt[i]) if (G[go[i]]) lca[i>>1]=find(go[i]);
	for (int i=head[k];i;i=next[i]) if (to[i]!=fa[k]) {
			fa[to[i]]=k;
			dfs(to[i]);
			G[to[i]]=k;
		}
	R[k]=dfn;
}
inline void dfs2(int k) {
	ans[k]-=s1[Q[k]+dep[k]]+s2[dep[k]-Q[k]+n];
	for (int i=head[k];i;i=next[i]) if (to[i]!=fa[k]) dfs2(to[i]);
	for (int i=cur[k];i;i=nxt[i]) s1[go[i]]+=d[i];
	for (int i=Cur[k];i;i=Nxt[i]) s2[Go[i]]+=D[i];
	ans[k]+=s1[Q[k]+dep[k]]+s2[dep[k]-Q[k]+n];
}
int main()
{
	n=gi();const int B=sqrt(n);
	int m=gi(),i,a,b,tot,g,l,r,k,len,t,top,fix,s,E,De;
	for (i=1;i<n;i++) if ((e[i].first=gi())>(e[i].second=gi())) swap(e[i].first,e[i].second);
	for (i=1;i<=n;i++) Q[i]=gi();
	for (;m;m-=g) {
		for (i=1;i<=n;i++) head[i]=cur[i]=fa[i]=0;
		g=min(m,B);
		for (i=1,De=0;i<=g;i++) if (op[i]=gi(),oa[i]=gi(),ob[i]=gi(),op[i]==2) {
				oc[i]=gi(),od[i]=gi();
				if (oa[i]>ob[i]) swap(oa[i],ob[i]);
				if (oc[i]>od[i]) swap(oc[i],od[i]);
				del[++De]=make_pair(oa[i],ob[i]);
			}
		sort(e+1,e+n);E=n-1;
		sort(del+1,del+1+De);
		for (i=1,k=1,tot=0;i<n;i++) {
			while (k<=De&&del[k]<e[i]) k++;
			if (del[k]==e[i]) use[i]=true;
			else {
				a=e[i].first,b=e[i].second;
				to[++tot]=b,next[tot]=head[a],head[a]=tot;
				to[++tot]=a,next[tot]=head[b],head[b]=tot;
			}
		}
		for (t=1,len=0;t<=n;t++) if (!fa[t]) for (l=0,q[r=1]=rt[++len]=t;l!=r;) for (i=head[k=q[++l]],pos[k]=len,dep[k]=dep[fa[k]]+1;i;i=next[i]) if (to[i]!=fa[k]) fa[q[++r]=to[i]]=k;
		for (i=1;i<=len;i++) cur[i]=0;
		for (i=1,tot=1;i<n;i++) if (use[i]) {
				a=pos[e[i].first],b=pos[e[i].second];use[i]=false;
				go[++tot]=b,Go[tot]=e[i].second,nxt[tot]=cur[a],cur[a]=tot;
				go[++tot]=a,Go[tot]=e[i].first,nxt[tot]=cur[b],cur[b]=tot;
			}
		for (t=1,top=fix=0;t<=g;t++)
			if (op[t]==1) {
				a=oa[t],b=ob[t];
				for (l=0,pre[q[r=1]=pos[b]]=0;l!=r;) for (i=cur[k=q[++l]];i;i=nxt[i]) if (!die[i]&&i!=pre[k]) pre[q[++r]=go[i]]=i^1;
				Qu[++top]=a;
				for (k=pos[a];pre[k];k=go[pre[k]])
					Qv[top]=Go[pre[k]^1],end[top]=false,Qu[++top]=Go[pre[k]];
				Qv[top]=b,end[top]=true;
			}
			else if (op[t]==2) {
				a=pos[oa[t]],b=pos[ob[t]];e[++E]=make_pair(oc[t],od[t]);
				for (i=cur[a];i;i=nxt[i]) if (!die[i]&&go[i]==b) { die[i]=die[i^1]=true; break; }
				a=pos[oc[t]],b=pos[od[t]];
				go[++tot]=b,Go[tot]=od[t],nxt[tot]=cur[a],cur[a]=tot;
				go[++tot]=a,Go[tot]=oc[t],nxt[tot]=cur[b],cur[b]=tot;
			}
			else {
				a=oa[t],b=ob[t];
				p[++fix]=a,C[fix]=b,tim[fix]=top;
			}
		while (tot>1) die[tot--]=false;

		for (i=1;i<=n;i++) cur[i]=G[i]=0;
		for (i=1,r=1;i<=top;i++) {
			nxt[++r]=cur[Qu[i]],cur[Qu[i]]=r,go[r]=Qv[i];
			nxt[++r]=cur[Qv[i]],cur[Qv[i]]=r,go[r]=Qu[i];
		}
		for (i=1,dfn=0;i<=len;i++) dfs(rt[i]);
		for (i=0;i<=n;i++) cur[i]=Cur[i]=0;
		for (i=1,l=r=s=0;i<=top;i++) {
			Qs[i]=s;
			nxt[++l]=cur[Qu[i]],cur[Qu[i]]=l,go[l]=dep[Qu[i]]+s,d[l]=1;
			nxt[++l]=cur[fa[lca[i]]],cur[fa[lca[i]]]=l,go[l]=dep[Qu[i]]+s,d[l]=-1;
			if (lca[i]!=Qv[i]) {
				Nxt[++r]=Cur[Qv[i]],Cur[Qv[i]]=r,Go[r]=n+(dep[lca[i]]<<1)-dep[Qu[i]]-s,D[r]=1;
				Nxt[++r]=Cur[lca[i]],Cur[lca[i]]=r,Go[r]=n+(dep[lca[i]]<<1)-dep[Qu[i]]-s,D[r]=-1;
			}
			end[i]?s=0:s+=dep[Qu[i]]+dep[Qv[i]]-(dep[lca[i]]<<1)+1;
		}
		for (i=1;i<=len;i++) dfs2(rt[i]);
		for (i=cur[0];i;i=nxt[i]) s1[go[i]]+=d[i];
		for (i=Cur[0];i;i=Nxt[i]) s2[Go[i]]+=D[i];

		for (i=1;i<=fix;Q[a]=C[i++])
			if (Q[a=p[i]]!=C[i])
				for (k=top;k>tim[i];k--)
					if (pos[Qu[k]]==pos[a]) {
#define in(a,b) (L[a]<=L[b]&&L[b]<=R[a])
						if (in(lca[k],a)&&
							((in(a,Qu[k])&&dep[Qu[k]]+Qs[k]==Q[a]+dep[a])
							 ||(in(a,Qv[k])&&(dep[lca[k]]<<1)-dep[Qu[k]]-Qs[k]==dep[a]-Q[a]))) ans[a]--;
						else if (in(lca[k],a)&&
								  ((in(a,Qu[k])&&dep[Qu[k]]+Qs[k]==C[i]+dep[a])
								   ||(in(a,Qv[k])&&(dep[lca[k]]<<1)-dep[Qu[k]]-Qs[k]==dep[a]-C[i]))) ans[a]++;
					}
		sort(e+1,e+1+E);
		for (i=1,k=1,top=0;i<=E;i++) {
			while (k<=De&&del[k]<e[i]) k++;
			if (k<=De&&del[k]==e[i]) k++;
			else e[++top]=e[i];
		}
	}
	for (i=1;i<=n;i++) printf("%d ",ans[i]);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注