题解：CF283E Cow Tennis Tournament

· · 题解

首先我们先离散化掉所有值。

接下来我们考虑容斥掉答案，改为统计不满足条件的三元环。

我们考虑一下如何统计不满足条件的三元环，发现一个这样的三元环中，一定有且仅有一个点指向另外两个点，也就是说对于每一个点，这个点和他指向的任意两个点都构成这样的三元环。也就是说设点 i 的出度为 d_i，不满足条件的三元环数量为 \sum_{i=1}^{n}\binom{d_i}{2}。

接下来考虑如何统计 d_i，我们记一个布尔数组 v_i，代表第 i 个点和当前点的连边情况。

我们考虑枚举当前点 x，考虑 x 右移时 v 的变化。显然对于每一个 r<x 的区间，其不再生效，其区间中的点与 x 的连边情况和与 x+1 的情况要相反，此时我们将区间反转。而对于 l=x 的区间，其应该开始生效，我们也将区间反转。

为了方便维护，i<x 的部分 v_i=0 表示 x 连向 i，i>x 的部分 v_i=0 表示 i 连向 x，现在对于 x，其 d_x 即为 (i-1-\sum_{j=1}^{i-1}v_j)+\sum_{j=i+1}^{n}v_j。

维护 v 的过程化为区间反转区间求和，使用线段树即可。

下附代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
#include<queue>
#define int long long
#define PII pair<int,int>
using namespace std;
int n,k,s[100005],q[100005],tot;
priority_queue<PII,vector<PII>,greater<PII>>q1,q2;
struct node{
    int cnt,lz;
}tr[400005];
unordered_map<int,int>mp;
void pushdown(int k,int l,int r,int mid){
    if(tr[k].lz){
        tr[k*2].cnt=mid-l+1-tr[k*2].cnt;tr[k*2].lz^=1;
        tr[k*2+1].cnt=r-mid-tr[k*2+1].cnt;tr[k*2+1].lz^=1;
        tr[k].lz=0;
    }
}
void pushup(int k){
    tr[k].cnt=tr[k*2].cnt+tr[k*2+1].cnt;
}
void change(int k,int l,int r,int x,int y){
    if(r<x||l>y) return;
    if(x<=l&&r<=y){
        tr[k].lz^=1;tr[k].cnt=r-l+1-tr[k].cnt;
        return;
    }
    int mid=(l+r)/2;
    pushdown(k,l,r,mid);
    change(k*2,l,mid,x,y);change(k*2+1,mid+1,r,x,y);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(r<x||l>y) return 0;
    if(x<=l&&r<=y) return tr[k].cnt;
    int mid=(l+r)/2;
    pushdown(k,l,r,mid);
    return query(k*2,l,mid,x,y)+query(k*2+1,mid+1,r,x,y);
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i],q[i]=s[i];
    sort(q+1,q+n+1);
    for(int i=1;i<=n;i++){
        if(q[i]!=q[i-1]) mp[q[i]]=++tot;
    }
    for(int i=1;i<=k;i++){
        int l,r;cin>>l>>r;
        l=mp[q[lower_bound(q+1,q+n+1,l)-q]];
        r=mp[q[upper_bound(q+1,q+n+1,r)-q-1]];
        if(!l||!r||l==r) continue;
        q1.push({r,l});q2.push({l,r});
    }
    int ans=n*(n-1)*(n-2)/6;
    for(int i=1;i<=n;i++){
        while(q1.size()&&q1.top().first<i) change(1,1,n,q1.top().second,q1.top().first),q1.pop();
        while(q2.size()&&q2.top().first<=i) change(1,1,n,q2.top().first,q2.top().second),q2.pop();
        int cnt=(i>1?i-1-query(1,1,n,1,i-1):0)+(i<n?query(1,1,n,i+1,n):0);
        ans-=cnt*(cnt-1)/2;
    }
    cout<<ans<<endl;
    return 0;
}