[CF283E] Cow Tennis Tournamsan

CF283E
答案即为 \(\binom{n}{3}\) 减去不合法环数。
一个三元环中最多1个点出度为2,所以出度为 x 的点会造成 \(\binom{x}{2}\) 个不合法的环。
\(\Omicron(nm)\) 的做法就是枚举 i,判断 i 与 n 个点连边是否反向(0,1表示)。
然后可以发现对于一段区间 [l,r] 修改后做贡献的点是一样的,所以区间排序后直接计算即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define ls p<<1
#define rs p<<1|1
#define mp make_pair
typedef pair<int,int> kk;
const int MAXN=1e5+5;
const int INF=0x3f3f3f3f;
void read(int &x){
	x=0;int f=1;char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);s=getchar();
	}
	x*=f;
}
int n,m,a[MAXN],b[MAXN];
vector<kk> v[MAXN],v1[MAXN];
ll Ans;
struct ren{
	int len,va,ta;
}t[MAXN<<2];
void pup(int p){
	t[p].va=t[ls].va+t[rs].va;
}
void pdo(int p){
	if(!t[p].ta) return;
	t[ls].va=t[ls].len-t[ls].va;t[ls].ta^=1;
	t[rs].va=t[rs].len-t[rs].va;t[rs].ta^=1;
	t[p].ta=0;
}
void bui(int p,int l,int r){
	t[p].len=r-l+1;t[p].va=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	bui(ls,l,mid);bui(rs,mid+1,r);
}
void modi(int p,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr){
		t[p].va=t[p].len-t[p].va;t[p].ta^=1;return;
	}
	pdo(p);
	int mid=(l+r)>>1;
	if(ql<=mid) modi(ls,l,mid,ql,qr);
	if(qr>mid) modi(rs,mid+1,r,ql,qr);
	pup(p);
}
int que(int p,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr) return t[p].va;
	pdo(p);
	int mid=(l+r)>>1,tmp=0;
	if(ql<=mid) tmp+=que(ls,l,mid,ql,qr);
	if(qr>mid) tmp+=que(rs,mid+1,r,ql,qr);
	return tmp;
}
int main(){
	read(n);read(m);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	a[n+1]=INF;
	sort(a+1,a+2+n);
	for(int i=1,x,y;i<=m;i++){
		read(x);read(y);
		if(y<a[1]||x>a[n]) continue;
		int xx=lower_bound(a+1,a+2+n,x)-a;
		int yy=upper_bound(a+1,a+2+n,y)-a-1;
		v[xx].push_back(mp(xx,yy));
		v1[yy+1].push_back(mp(xx,yy));
	}
	bui(1,1,n);
	Ans=1ll*n*(n-1)*(n-2)/6;
	for(int i=1;i<=n;i++){
		for(auto u:v[i]){
			modi(1,1,n,u.first,u.second);
		}
		for(auto u:v1[i]){
			modi(1,1,n,u.first,u.second);
		}
		ll op=0;
		if(i>1) op+=i-1-que(1,1,n,1,i-1);
		if(i<n) op+=que(1,1,n,i+1,n);
		if(op>=2) Ans-=op*(op-1)/2;
	}
	printf("%lld",Ans);
}