Contest

　

contest

Contest

题意：一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。

思路：分别观察第一场比赛和第二场，第一场和第三场，第二场和第三场，如果在某一场比赛中a>b,另一场中b<a则对答案有贡献最终发现对所有情况都加了两次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int a[maxn],b[maxn],c[maxn];
int A[maxn],B[maxn],n;
int qu(int pos){
	int ans=0;
	while(pos > 0){
		ans+=B[pos];
		pos-=(pos & (-pos));
	}
	return ans;
}
void up(int pos,int x){
	while(pos<maxn){
		B[pos]+=x;
		pos+=(pos & (-pos));
	}	
	
}
ll solve(int x[],int y[]){
	for(int i=0;i<n;i++)
		A[x[i]]=y[i];
	memset(B,0,sizeof(B));
	ll res=0;
	for(int i=1;i<=n;i++){
		res+=(i-1-qu(A[i]));
		up(A[i],1);
	}
	return res;
}
int main(){
	iOS::sync_with_stdio(false);
	cin>>n;
	for(int i = 0;i < n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	ll ans=solve(a,b)+solve(a,c)+solve(b,c);
	ans/=2;
	cout<<ans<<"\n";
	return 0;
}

相关阅读

B. Build a Contest

                                                                         B. Build a

D - Decrease (Contestant ver.)（思维好题）

Problem Statement We have a sequence of length N consisting of non-negative integers. Consider performing the followin