2025杭电多校赛（2）1006 半

题目整理

问题描述
某学校举办两场个人比赛，共有相同的 n 名选手（编号 1∼n）。已知两场比赛的排名结果：

• 第一场排名：a1​,a2​,⋯,an​（从高到低）
• 第二场排名：b1​,b2​,⋯,bn​（从高到低）

其中 a 和 b 均为 1∼n 的排列（无重复排名）。
作为选手 i，你可以通过禁赛其他选手，使得自己在两场比赛中均成为第一名。要求计算：对于每个选手 i，最少需要禁赛多少名选手？
（禁赛后，剩余选手的相对排名保持原顺序不变）

输入格式

• 第一行：整数 T（1≤T≤20），表示测试数据组数
• 每组数据：
  • 第一行：整数 n（1≤n≤106）
  • 第二行：n 个整数 a1​,a2​,⋯,an​（第一场排名）
  • 第三行：n 个整数 b1​,b2​,⋯,bn​（第二场排名）
• 总数据规模：所有测试数据的 n 之和不超过 2×106

输出格式

• 每组测试数据输出一行：n 个整数，第 i 个整数表示选手 i 的最少禁赛人数

Sample Input

1

5

2 1 5 4 3

2 4 5 1 3

Sample Output

3 0 4 3 3

这题题意不难，就是找到一个数在两个数组中前面的数的集合的交集大小，而在这里我们要好好利用这两个数组是n的全排列的性质。

注意下面的代码是超时的，优化方法后面说。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,temp,a[1000005],b[1000005],n,ans[1000005];
set<int>arr;
int main() {
scanf("%d",&t);
while(t--){arr.clear();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&temp);b[temp]=i;}for(int i=1;i<=n;i++){arr.insert(b[a[i]]);int s1=i-distance(arr.begin(),arr.find(b[a[i]]))-1;int s2=b[a[i]]-1;ans[a[i]]=s1+s2; }for(int i=1;i<=n;i++){printf("%d ",ans[i]);}printf("\n");
}return 0;
}

解释：这里的a数组就是和题目的一样，而b数组记录的是数字为i的下标，这是为了利用全排列的性质。

1.我们从前向后遍历a数组，那么i-1就是这个数（now）前面有几个数。我们现在要确定这些数有几个在b数组的now的前面，也就是重复的。

2.我一开始用set来实现，每次就把遍历到的数now的在b数组的下标插入到set中，因为set会自动排序，而且下标是不会重复的。这样我们每次查询前面有几个数就是有几个重复的（我这样表述的不好），下面我讲线段树维护可能好懂一些。但是distance函数速度是n，我本以为是常数，这样就是n^2算法，和暴力没什么区别。

3.那只有用树状数组或线段树维护。我们要维护的实际是一个前缀和数组，而这个数组每次都要有一个数从0变为1，每次我们也都要查询一个特定的前缀和值。那这就是线段树的单点修改，区间查询。套用线段树模板就行。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{long long r,l,sum,lz;
};
node tree[5000005];
int t,temp,a[1000005],b[1000005],n,ans[1000005];
void init(){for(int i=1;i<=5000000;i++){tree[i].l=tree[i].lz=tree[i].r=tree[i].sum=0;}
}
void push_down(int i)//下传函数
{if(tree[i].lz!=0){tree[i*2].lz+=tree[i].lz;tree[i*2+1].lz+=tree[i].lz;tree[i*2].sum+=tree[i].lz*(tree[i*2].r-tree[i*2].l+1);tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-tree[i*2+1].l+1);tree[i].lz=0;}return;
}
void build(int i,int l,int r)//建树
{tree[i].l=l,tree[i].r=r;tree[i].lz=0;if(l==r){return;}int mid=(l+r)/2;build(2*i,l,mid);build(2*i+1,mid+1,r);
}
void add(int i,int l,int r,int k)//区间加减
{if(tree[i].l>=l&&tree[i].r<=r){tree[i].sum+=k*(tree[i].r-tree[i].l+1);tree[i].lz+=k;return;}push_down(i);if(tree[i*2].r>=l){add(i*2,l,r,k);}if(tree[i*2+1].l<=r){add(i*2+1,l,r,k);}tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;return;
}
long long search(int i,int l,int r)//查询
{if(tree[i].l>=l&&tree[i].r<=r){return tree[i].sum;}if(tree[i].r<l||tree[i].l>r){return 0;}push_down(i);long long ans=0;if(tree[i*2].r>=l){ans+=search(i*2,l,r);}if(tree[i*2+1].l<=r){ans+=search(i*2+1,l,r);}return ans;
}
int main() {
scanf("%d",&t);
while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&temp);b[temp]=i;}build(1,1,n);for(int i=1;i<=n;i++){add(1,b[a[i]],b[a[i]],1);ans[a[i]]=b[a[i]]-1+search(1,b[a[i]],n)-1;}for(int i=1;i<=n;i++){printf("%d ",ans[i]);}init();printf("\n");
}return 0;
}