题意
思路
- pre_work sort+离散化
- 如何求合法三元组，考虑补集转化，用C(n,3)-不合法的；
- 考虑不合法如何求，这个三元组必定有一个可以战胜其他两个，那么只要统计出他能打败的人，再C(cnt,2)，再sum一下
- 如何统计他能打败的人（in[i])
- 首先，我们考虑一个暴力，O(nnm);考虑一个矩阵，a[i][j]表示i和j对战的结果，0表示i输，1表示i赢，那么可以只考虑右上方的rt三角形，每次修改只要baoli修改一个RT三角形即可
- 瓶颈在于区间修改及查询，可以想到线段树，又发现对于i来说只有覆盖i的修改才对i有用，所以对于所有操作只要扫两遍即可
- O(n+mlogn)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll read()
{
char ch=' ';
ll f=1;ll x=0;
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';ch=getchar();
}
return x*f;
}
const ll N=1e5+100;
ll z[N];
struct node
{
ll l,r;
}c[N];
bool cmp1(node a,node b)
{
return a.l<b.l;
}
bool cmp2(node a,node b)
{
return a.r>b.r;
}
struct tree
{
ll cnt0;
ll cnt1;
ll tag;
}t[N<<2];
ll in[N];
void update(ll rt)
{
t[rt].cnt0=t[rt<<1].cnt0+t[rt<<1|1].cnt0;
t[rt].cnt1=t[rt<<1].cnt1+t[rt<<1|1].cnt1;
return ;
}
void build(ll rt,ll l,ll r)
{
t[rt].cnt0=1;
t[rt].cnt1=0;
t[rt].tag=0;
if(l==r)
{
return ;
}
ll mid=(l+r) >> 1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
update(rt);
}
void pushdown(ll rt)
{
t[rt].tag=0;
t[rt<<1].tag^=1;
t[rt<<1|1].tag^=1;
swap(t[rt<<1].cnt0,t[rt<<1].cnt1);
swap(t[rt<<1|1].cnt0,t[rt<<1|1].cnt1);
}
void modify(ll rt,ll l,ll r,ll x,ll y)
{
if(l>=x&&r<=y)
{
swap(t[rt].cnt0,t[rt].cnt1);
t[rt].tag^=1;
return ;
}
if(t[rt].tag) pushdown(rt);
ll mid=(l+r) >> 1;
if(x<=mid)
{
modify(rt<<1,l,mid,x,y);
}
if(y>mid)
{
modify(rt<<1|1,mid+1,r,x,y);
}
update(rt);
}
ll query(ll rt,ll l,ll r,ll x,ll y)
{
if(l>=x&&r<=y)
{
return t[rt].cnt1;
}
if(t[rt].tag==1)
{
pushdown(rt);
}
ll mid=(l+r) >> 1;
ll ret=0;
if(x<=mid)
{
ret+=query(rt<<1,l,mid,x,y);
}
if(y>mid)
{
ret+=query(rt<<1|1,mid+1,r,x,y);
}
return ret;
}
int main()
{
ll n,m;
n=read();m=read();
ll i,j;
for(i=1;i<=n;i++)
{
z[i]=read();
}
sort(z+1,z+1+n);
for(i=1;i<=m;i++)
{
c[i].l=read();
c[i].r=read();
c[i].l=lower_bound(z+1,z+1+n,c[i].l)-z;
c[i].r=upper_bound(z+1,z+1+n,c[i].r)-z-1;
//cout<<c[i].l<<' '<<c[i].r<<endl;
}
sort(c+1,c+1+m,cmp1);
build(1,1,n);
for(i=1,j=1;i<n;i++)
{
while(c[j].l>=c[j].r&&j<=m) j++;
while(c[j].l<=i&&j<=m)
{
modify(1,1,n,c[j].l,c[j].r);
j++;
while(c[j].l>=c[j].r&&j<=m) j++;
}
in[i]=query(1,1,n,i+1,n);
}
build(1,1,n);
sort(c+1,c+1+m,cmp2);
for(i=n,j=1;i>1;i--)
{
while(c[j].l>=c[j].r&&j<=m) j++;
while(c[j].r>=i&&j<=m)
{
modify(1,1,n,c[j].l,c[j].r);
j++;
while(c[j].l>=c[j].r&&j<=m) j++;
}
in[i]+=i-1-query(1,1,n,1,i-1);
}
ll ans=n*(n-1)*(n-2)/6;
for(i=1;i<=n;i++)
{
ans-=in[i]*(in[i]-1)/2;
}
cout<<ans<<endl;
return 0;
}
