[[Sweep Line]] [[Segment Tree]] [[math]]
This will go over the basic outline for solution.
The first thing to note, is that, if you interpret the problem as a graph,
you can compute the answer if you have the degrees (i.e. number of wins) of every cow.
Call three cows "unbalanced" if the is one cow that beats the other two.
Note that every three cows is either unbalanced or balanced (there are no other configurations of three cows).
Thus, \(\text{balenced}+\text{unbalanced}=C_n^3\).
So to count the number of balanced, it suffices to count the number of unbalanced.
But it is easy to show that \(\text{unbalanced}=\sum_{cows_i}C_{out_i}^2\), ([[CF1662N 翻|a similar idea]])
so \(\text{balanced}=C_n^3-\sum_{cows_i}C_{out_i}^2\).
Now sort the skill levels of the cows (the order of the \(s_i\) doesn’t actually matter). \(s_1\) is lowest skill.
Now consider an \(n × n\) grid where the i-th row and j-th column of the grid is a 1 if the match between cow \(i\) and cow \(j\) is flipped.
The grid is initially all zeros and Farmer John’s query simply flips a rectangle of the form \([a, b] × [a, b]\).
We can process these queries and compute the number of wins for each cow using a vertical sweep line on the grid and updating with a seg tree on the interval \([1,n]\). The seg tree needs to handle queries of the form
- Flip all numbers (0->1, 1->0) in a range \([a, b]\).
- Query number of 1 in a range \([a, b]\).
Note that given this seg tree we can compute the number of wins for each cow at every point in the sweep line as
\[\begin{aligned}&\text{Number of 1 in range [ 1 , i - 1 ]} + \text{Number of 0 in range [ i + 1, n ]}\\ =& \text{Number of 1 in range [ 1 , i - 1 ]} + N-i-\text{Number of 1 in range [ i + 1, n ]}\end{aligned}\]There are \(m\) queries so this solution takes \(O(m\log n)\) time.
Note that the seg tree needed to handle this problem is the same seg tree you need for problem lites on USACO 2008 Gold
#include<bits/stdc++.h>
#define mid (l+r>>1)
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int N=200005;
int n,m,s[N],a,b,t,an[N];
struct A{
int id,x,y;
}po[N];
long long ans;
int su[N<<1],lz[N<<1],x,y;
void down(int l,int r,int p){
if(lz[p]){
lz[ls]^=1;
lz[rs]^=1;
su[ls]=mid-l+1-su[ls];
su[rs]=r-mid-su[rs];
lz[p]^=1;
}
}
void up(int p){
su[p]=su[ls]+su[rs];
}
void update(int l,int r,int p){
if(l>r)return;
if(l==r){
su[p]^=1;
return;
}
if(x<=l&&r<=y){
lz[p]^=1;
su[p]=r-l+1-su[p];
return;
}
down(l,r,p);
if(x<=mid)update(l,mid,ls);
if(y>mid)update(mid+1,r,rs);
up(p);
}
int o;
void query(int l,int r,int p){
if(l>r)return;
if(l==r){
o+=su[p];
return;
}
if(x<=l&&r<=y){
o+=su[p];
return;
}
int ret=0;
down(l,r,p);
if(x<=mid)query(l,mid,ls);
if(mid<y)query(mid+1,r,rs);
up(p);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
}
sort(s+1,s+1+n);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
a=lower_bound(s+1,s+1+n,a)-s;
b=upper_bound(s+1,s+1+n,b)-s;
if(a>b-1)continue;
po[++t]={a,a,b-1};
po[++t]={b,a,b-1};
}
sort(po+1,po+1+t,[](A a,A b){
return a.id<b.id;
});
for(int i=1,c=1;i<=n;i++){
for(;po[c].id==i;c++)
x=po[c].x,y=po[c].y,update(1,n,1);
an[i]=n-i;
x=1,y=i-1;if(x<=y)o=0,query(1,n,1),an[i]+=o;
x=i+1,y=n;if(x<=y)o=0,query(1,n,1),an[i]-=o;
}
for(int i=1;i<=n;i++)ans+=1ll*an[i]*(an[i]-1)/2;
ans=1ll*(n-2)*(n-1)*n/6-ans;
printf("%lld",ans);
}