CF283E. Cow Tennis Tournament

· · 题解

正难则反，考虑求不合法的三元组的数量。

对于一个不合法的三元组，可以发现条件等价于三元组中有一个点出度为 2。记 m 次操作后每个点出度为 d_i，答案就是 \dbinom{n}{3}-\sum\limits_{i=1}^n\dbinom{d_i}{2}。

那么怎么统计？回忆 \mathcal{O}(nm) 的做法，数组 a_{i,j} 表示 i,j 间边的方向。假设当次修改影响的区间是 [l,r]，那么这个修改就是 \forall i,j\in[l,r]，a_{i,j}\gets a_{i,j}\oplus 1。显然可以对 j 这一维差分。

更进一步的，我们可以对操作应用差分的思想。更具体的，我们枚举 i，用线段树维护 a 数组，每个修改 [l,r] 就是在 i 为 l 或 r+1 的时候区间异或一下。时间复杂度 \mathcal{O}(n\log n)。

#include<bits/stdc++.h>
#define int long long
#define mk make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int,int>pii;
const int inf=1e18; 
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct segtree{
    #define ls p<<1
    #define rs p<<1|1
    #define lson l,mid,ls
    #define rson mid+1,r,rs
    struct Node{
        int s[2],tag;
    }c[400005];
    void pushup(int p){
        for(int i=0;i<2;i++)c[p].s[i]=c[ls].s[i]+c[rs].s[i];
    }
    void pushdown(int l,int r,int p){
        if(!c[p].tag)return;
        int siz=r-l+1,ln=siz-(siz>>1),rn=siz>>1;
        swap(c[ls].s[0],c[ls].s[1]);
        swap(c[rs].s[0],c[rs].s[1]);
        c[ls].tag^=c[p].tag,c[rs].tag^=c[p].tag;
        c[p].tag=0;  
    }
    void build(int l,int r,int p){
        c[p].tag=0;
        if(l==r){
            c[p].s[0]=1,c[p].s[1]=0;
            return;
        }
        int mid=(l+r)>>1;
        build(lson),build(rson);
        pushup(p);
    }
    void update(int l,int r,int p,int L,int R){
        if(L<=l&&r<=R){
            swap(c[p].s[0],c[p].s[1]);
            c[p].tag^=1;
            return;
        }
        int mid=(l+r)>>1;pushdown(l,r,p);
        if(L<=mid)update(lson,L,R);
        if(R>mid)update(rson,L,R);
        pushup(p);
    }
    int query(int l,int r,int p,int L,int R,int o){
        if(L<=l&&r<=R)return c[p].s[o];
        int mid=(l+r)>>1,res=0;pushdown(l,r,p);
        if(L<=mid)res+=query(lson,L,R,o);
        if(R>mid)res+=query(rson,L,R,o);
        return res;
    }
    #undef ls
    #undef rs
    #undef lson
    #undef rson
}Tr;
int h[100005];vector<pii>v[100005];
signed main(){
    int n=read(),m=read(),ans=n*(n-1)*(n-2)/6;
    for(int i=1;i<=n;i++)h[i]=read();
    sort(h+1,h+n+1);h[0]=-inf,h[n+1]=inf;
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        if(l>h[n]||r<h[1])continue;
        l=lower_bound(h,h+n+1+1,l)-h;
        r=upper_bound(h,h+n+1+1,r)-h-1;
        v[l].push_back(mk(l,r));
        v[r+1].push_back(mk(l,r));
    }
    Tr.build(1,n,1);
    for(int i=1;i<=n;i++){
        for(auto x:v[i])Tr.update(1,n,1,x.fi,x.se);
        Tr.update(1,n,1,1,i);
        int cnt=Tr.query(1,n,1,1,n,1)-Tr.query(1,n,1,i,i,1);
        ans-=cnt*(cnt-1)/2;
        Tr.update(1,n,1,1,i);
    }
    printf("%lld\n",ans);
    return 0;
}