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);
}