普及模拟3

\(T1\) 最大生成树 \(100pts\)

• 简化题意：给定一个 \(n(1 \le n \le 1 \times 10^5）\) 个点的完全图，给定各点的点权 \(a_i(1 \le i \le n)\) ，两点间的边权为 \(|a_i-a_j|\) ，求该图的最大生成树。
• 正解：贪心，考虑到一个点对答案产生的贡献为 \(\max(a_i-\min\limits_{j=1}^{n} a_j,\max\limits_{j=1}^{n} a_j-a_i)\) ，又因为是完全图，易证得连边后一定是符合题意的解。

  ll a[100001];//十年OI一场空，不开long long见祖宗
  int main()
  {
      ll n,i,ans=0;
      cin>>n;
      for(i=1;i<=n;i++)
      {
          cin>>a[i];
      }
      sort(a+1,a+1+n);
      for(i=1;i<=n-1;i++)//只需要n-1条边
      {
          ans+=max(a[n]-a[i],a[i]-a[1]);
      }
      cout<<ans<<endl;
      return 0;
  }
  

\(T2\) 红黑树 \(80pts\)

• 简化题意：给定一棵 \(n(1 \le n \le 1 \times 10^5）\) 个点的有根树， \(1\) 为根节点，初始每个点都是红色，有 \(n\) 次操作，每次操作会把 \(p_i\) 变成黑色，保证操作序列 \(p\) 是一个排列，即每次操作的点都不相同。每次操作完成后，你需要输出有多少个子树是红黑子树，即子树内既包含黑点又包含红点。
• 部分分：
  • \(20pts\) ：对链的情况特判。
  • \(80pts\)（在线做法） ：一遍 \(DFS\) 处理出以 \(i(1 \le i \le n)\) 为根的子树大小，每次修改暴力跳父亲直到根节点，卡在了链的测试点上，复杂度为 \(O(n^2)\) ，代码。
• 正解（离线做法）：
  • 前置知识：红黑子树的产生与消失都是由改变颜色的这个点造成的。
    • 例如，把节点 \(x\) 变成黑色后，对于所有包含 \(x\) 的子树 \(T\) ，如果 \(x\) 是该子树内第一个变成黑色的点，那么 \(x\) 会让 \(T\) 变成红黑子树；如果 \(x\) 是该子树内最后一个红色的点，那么 \(x\) 会让 \(T\) 变成非红黑子树。
  • 记录下这棵子树中黑点最先出现和最后一个红点变成黑点的时候。
    • 做法一：暴力跳父亲时跳到某个点时，若这个点既不是以这个点的父亲节点为根的子树内最先出现的黑点，也不是最后一个变成黑点的红点时就没有必要跳了，因为不会对答案产生贡献了（这里可能有些绕口，自己可以画图模拟一下）。
      • 复杂度貌似很神奇，官方题解写的是 \(O(n)\) 。

      struct node
      {
      	int nxt,to;
      }e[200001];
      int head[200001],minn[200001],maxx[200001],p[200001],id[200001],fa[200001],cnt=0;//minn表示（····）最早出现，maxx表示最后一个（····）消失
      void add(int u,int v)
      {
      	cnt++;
      	e[cnt].nxt=head[u];
      	e[cnt].to=v;
      	head[u]=cnt;
      }
      void dfs(int x)
      {
      	minn[x]=maxx[x]=id[x];
      	for(int i=head[x];i!=0;i=e[i].nxt)
      	{
      		dfs(e[i].to);
      		minn[x]=min(minn[x],minn[e[i].to]);
      		maxx[x]=max(maxx[x],maxx[e[i].to]);
      	}
      }
      int main()
      {
      	int n,i,j,u,v,ans=0,flag;
      	cin>>n;
      	for(i=1;i<=n-1;i++)
      	{
      		cin>>u;
      		v=i+1;
      		fa[v]=u;
      		add(u,v);
      	}
      	for(i=1;i<=n;i++)
      	{
      		cin>>p[i];
      		id[p[i]]=i;
      	}
      	dfs(1);
      	for(i=1;i<=n;i++)
      	{
      		for(j=p[i];j!=0;j=fa[j])//暴力跳父亲
      		{
      			flag=0;
      			if(minn[j]==id[p[i]])
      			{
      				ans++;
      				flag=1;
      			}
      			if(maxx[j]==id[p[i]])
      			{
      				ans--;
      				flag=1;
      			}
      			if(flag==0)
      			{
      				break;
      			}
      		}
      		cout<<ans<<" ";
      	}
      	return 0;
      }
      

    • 做法二：进行差分维护一下。————隔壁@xrlong的做法
      • 树状数组的区间修改单点查询操作：

      struct node
      {
      	int nxt,to;
      }e[200001];
      int head[200001],minn[200001],maxx[200001],p[200001],id[200001],c[400001],cnt=0;
      int lowbit(int x)
      {
      	return (x&(-x));
      }
      void add(int u,int v)
      {
      	cnt++;
      	e[cnt].nxt=head[u];
      	e[cnt].to=v;
      	head[u]=cnt;
      }
      void dfs(int x)
      {
      	minn[x]=maxx[x]=id[x];
      	for(int i=head[x];i!=0;i=e[i].nxt)
      	{
      		dfs(e[i].to);
      		minn[x]=min(minn[x],minn[e[i].to]);
      		maxx[x]=max(maxx[x],maxx[e[i].to]);
      	}
      }
      void update(int n,int x,int key)
      {
      	for(int i=x;i<=n;i+=lowbit(i))
      	{
      		c[i]+=key;
      	}
      }
      int getsum(int x)
      {
      	int ans=0;
      	for(int i=x;i>0;i-=lowbit(i))
      	{
      		ans+=c[i];
      	}
      	return ans;
      }
      int main()
      {
      	int n,i,j,u,v,ans=0,flag;
      	cin>>n;
      	for(i=1;i<=n-1;i++)
      	{
      		cin>>u;
      		v=i+1;
      		add(u,v);
      	}
      	for(i=1;i<=n;i++)
      	{
      		cin>>p[i];
      		id[p[i]]=i;
      	}
      	dfs(1);
      	for(i=1;i<=n;i++)
      	{
      		update(n,minn[i],1);
      		update(n,maxx[i]-1+1,-1);
      	}
      	for(i=1;i<=n;i++)
      	{
      		cout<<getsum(i)<<" ";
      	}
      	return 0;
      }
      

      • 差分：

      struct node
      {
      	int nxt,to;
      }e[200001];
      int head[200001],minn[200001],maxx[200001],p[200001],id[200001],sum[400001],cnt=0;
      void add(int u,int v)
      {
      	cnt++;
      	e[cnt].nxt=head[u];
      	e[cnt].to=v;
      	head[u]=cnt;
      }
      void dfs(int x)
      {
      	minn[x]=maxx[x]=id[x];
      	for(int i=head[x];i!=0;i=e[i].nxt)
      	{
      		dfs(e[i].to);
      		minn[x]=min(minn[x],minn[e[i].to]);
      		maxx[x]=max(maxx[x],maxx[e[i].to]);
      	}
      }
      int main()
      {
      	int n,i,j,u,v,ans=0;
      	cin>>n;
      	for(i=1;i<=n-1;i++)
      	{
      		cin>>u;
      		v=i+1;
      		add(u,v);
      	}
      	for(i=1;i<=n;i++)
      	{
      		cin>>p[i];
      		id[p[i]]=i;
      	}
      	dfs(1);
      	for(i=1;i<=n;i++)
      	{
      		sum[minn[i]]++;
      		sum[maxx[i]-1+1]--;
      	}
      	for(i=1;i<=n-1;i++)
      	{
      		ans+=sum[i];
      		cout<<ans<<" ";
      	}
      	cout<<"0";
      	return 0;
      }
      

\(T3\) 校门外的树 \(30pts\)

• 简化题意：给定一个长度为 \(n(1 \le n \le 5 \times 10^5）\) 的序列 \(h\) ，有 \(m(1 \le m \le 5 \times 10^5）\) 次操作，每次操作前对于每一个 \(i(1 \le i \le n)\) 均有 \(h_i\) 增加 \(v_i\)，操作如下（对 \(2^{64}\) 取模）：
  • 操作一：将 \([l,r]\) 内的 \(v_i(l \le i \le r)\) 增加 \(v\) 。
  • 操作二：求 \(\sum\limits_{i=l}^{r} h_i\) 。
• 部分分：
  • \(30pts\) ：\(n^2\) 暴力枚举。
  • \((30+20=50)pts\) ：考虑到没有修改操作，维护一下即可。
• 正解：建一棵线段树，

\(T4\) 种树 \(0pts\)

• 简化题意：给定一个长度为 \(n(1 \le n \le 5 \times 10^5）\) 的线段，要求在这个线段上种树，对于每个 \(i(1 \le i \le n)\) 最多只能种一次树，有 \(m\) 组互相独立的计划，内容是第 \(x\) 个位置不能种树，\(|a_i-a_j| \ge k(1 \le i,j \le n,i \ne j)\) ，输出每个计划的方案数对 \(998244353\) 取模的结果。

总结

• \(T1、T3、T4\)打到 \(8:30\) ，\(9:30\) 打完 \(T2\) 后就去打高斯消元了，导致没有看见 \(T3\) 的对 \(2^{64}\) 取模（打成了 \(2^{60}\) ）。
• \(T3\) 觉得线段树可做，但不想打了。
• \(T4\) 没有再多想想，没骗到计数类型的 \(DP\) 分。