题目链接：https://ac.nowcoder.com/acm/contest/903/E 题目大意：
有n个男孩，索引从1到n，n个女孩索引从n+1到2n。
有一天，他们在一起开派对。女孩们坐在第一排，男孩们坐在第二排。他们的坐姿是这样的：一个男孩坐在一个女孩的后面，一个男孩坐在最左边的椅子上，另一个男孩坐在第二个椅子上，等等。
每个男孩都有一个他喜欢的女孩，他可以通过在一张纸上写下他想对她说的话来和他的爱人取得联系，并把它做成一个纸飞机，他会直接朝她扔去。你可以假设飞机会直线飞行。
但是，当两个纸飞机在空中相撞并中途坠落时，问题就出现了。显然，这将是非常尴尬的。所以每个男孩都想知道，如果他扔纸飞机，有多少纸飞机有可能与它相撞。
每个女孩都是一个男孩的心上人。
输入： 第一行包含一个整数n。
接下来是n行，第i行包含两个整数，第一个是坐在第i个男孩前面的女孩和他喜欢的女孩的索引。1≤n≤10^5
输出n行，
其中i-th包含一个整数，可能与i个男孩碰撞的飞机数。 思路： 我们把右边的点也记做1-n
所有可以用主席树维护。每次把b[i]加进去。 查询[i, n]与[1,b[i]]匹配的数量： cx(root[i-1], 1, n, b[i]+1, n) 查询[0, i]与[b[i]+1, n]匹配的数量： cx(root[n], 1, n, 1, b[i]-1)-cx(root[i], 1, n, 1, b[i]-1);
还可以用树状数组写，我当时没有想到，也是用差分的思想，本来省赛还补过，也是因为这题才学的主席树:https://blog.csdn.net/qq_21433411/article/details/89528291。
因为这个查询是固定的所以可以边添加边查询，记录下来就ok了。
for(int i=n;i>=1;i--)//查询0-b[i] -> 1的和就是b[i]+1 -> n与1-b[i] -> 1匹配的数量 { L[i]=cx(mp[b[i]]-1); add(mp[b[i]], 1); } for(int i=1;i<=n;i++)//查询b[i]+1 -> n的和就是1 -> a[i]-1与b[i]+1 -> n匹配的数量。 { R[i]=cx(n)-cx(mp[b[i]]); add(mp[b[i]], 1); } //树状数组 #include<bits/stdc++.h> #define LL long long using namespace std; int n, x, sum[50005]; int a[50005], b[50005]; int L[50005]={0}, R[50005]={0}; map<int, int> mp; void add(int p, int y)//p位置+y { while(p<=n) { sum[p]+=y; p+=(p&-p); } } int cx(int p) //前缀和 { int ans=0; while(p) { ans+=sum[p]; p-=(p&-p); } return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); mp[a[i]]=i; } memset(sum, 0, sizeof(sum)); for(int i=n;i>=1;i--) { L[i]=cx(mp[b[i]]-1); add(mp[b[i]], 1); } memset(sum, 0, sizeof(sum)); for(int i=1;i<=n;i++) { R[i]=cx(n)-cx(mp[b[i]]); add(mp[b[i]], 1); } for(int i=1;i<=n;i++) { printf("%d\n",L[i]+R[i]); } return 0; } //主席树 #include<bits/stdc++.h> #define LL long Long using namespace std; const int maxn=2e5+10; int L[maxn*20], R[maxn*20], sum[maxn*20]; int n, q, m ,cnt = 0; int a[maxn], b[maxn], root[maxn]; map<int ,int> mp; #define mid ((l+r)>>1) int JS(int l, int r) { int rt=++cnt; sum[rt]=0; if(l<r) { L[rt]=JS(l ,mid); R[rt]=JS(mid+1, r); } return rt; } int gx(int i, int l, int r, int x) { int rt=++cnt; L[rt]=L[i], R[rt]=R[i], sum[rt]=sum[i]+1;//更新 if(l<r) { if(x<=mid) { L[rt]=gx(L[i], l, mid, x); } else { R[rt]=gx(R[i], mid+1, r, x); } } return rt; } int ans=0; int cx(int i, int l, int r, int L1, int R1) { if(R1<L1) { return 0; } if(l==L1&&r==R1) { ans+=sum[i]; return 0; } if(R1<=mid) { cx(L[i], l, mid, L1, R1); } else if(L1>=(mid)+1) { cx(R[i], (mid)+1, r, L1, R1); } else { cx(L[i], l, mid, L1, mid); cx(R[i], (mid)+1, r, (mid)+1, R1); } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i], &b[i]); mp[a[i]]=i; } for(int i=1;i<=n;i++) { b[i]=mp[b[i]]; } root[0] = JS(1, n);//建空树 for(int i=1;i<=n;i++) { //cout<<b[i]<<endl; root[i]=gx(root[i-1], 1, n, b[i]);//更新 } for(int i=1;i<=n;i++) { int s=0; ans=0; cx(root[i-1], 1, n, b[i]+1, n); s+=ans; ans=0; cx(root[n], 1, n, 1, b[i]-1); s+=ans; ans=0; cx(root[i], 1, n, 1, b[i]-1); s-=ans; printf("%d\n",s); } return 0; }