题解 CF283E 【Cow Tennis Tournament】

题目大意

给出n个正整数，由大小确定数与数之间的指向关系（大的指向小的），其中大小处在某一区间的数指向关系全部取反，问n个数之间的三元环个数

正在做学长推荐的数据结构题，莫名看到了这道数学（蒟蒻感觉对这种有数学成分的题相当无力啊），于是本蒟蒻想（kan ti jie）了好久好久，终于受到学长数学+数据结构的真传切了这题（先orz切题的大佬一波）

具体思路

first

不管怎样，$s_i$数值范围很大，而区间取反也是从数值入手，既然如此，不管三七二十一，先把数值离散化一波，用数值大小的排名代替数值，将数值范围化为$1-n$，然后把要取反的区间两端做同样的操作。又因为反正是数值区间上的取反，干脆把所有数再排下序,这样基本操作就完成了。

second

三元环不好直接求，，终于发现可以 容斥 一波，先求出所有方案：

$$C_n^3$$
然后是不符合题意的方案数，本蒟蒻觉得分为两种：

1. 一群牛之间互相都不可以击败对方（即一堆相等的正整数），这样的一堆数之间没有指向性。这样的话，我们可以用一个数组$cnt_x$，来记录数x出现的个数，而明显看得出来，只要在每堆这些相等的数中任意取2个，则方案不合理。综上，该情况的不合理方案为(式子里的$s_i$为离散化处理过的$s_i$数组)：
   $$\sum_{i=s_1}^{s_n}{C_{cnt_{i}}^2}$$
   
2. 一头牛很勇，可以搞其他很多头牛（即一个数很nb，可以指（cha）向其他的很多个数）。而一个数x能指向的数有且仅有两种情况（又是两种……） ：a.一个数y比x小且未被经过x的区间经过奇数次（即未被经过x的区间给d掉）；b.一个数z比x大且被经过x的区间经过奇数次（即被经过x的区间给d掉）。设第一种情况存在可能的y有$res_1$种，第二种情况存在可能的z有$res_2$种，那么显然，在$res_1$和$res_2$中取出任两个和x搭配都会导致方案不合理。设$res=res_1+res_2$，则不合理方案数为： $C_{res}^2$。而总的不合理方案书如下：
   $$\sum_{i=s_1}^{s_n}{C_{res_i}^2}$$

third

由上总结后，求解答案的思路清晰很多了呢（没有的话别喷蒟蒻）。但看看上面我们要求的两个东西，$C_{cnt_i}^2$很好求，但那个很勇的牛的情况就有点%￥&……

关键是经过x的区间要算、而没经过的不能算进去这个不好处理，莫非一个个数值暴力枚举？？这样肯定超时，怎么办呢？？

本蒟蒻脑子转得慢，搞不懂怎么处理，去问学长，学长说要用扫描线，我说我不会，于是学长耐心地跟我讲了扫描线，我认真滴听，然后……没听懂。

关于学长讲的扫描线，我只记得好像是先按区间左界$sort$一波，再操作一波，再按右界$sort$一波，再操作一波，然后就有答案了……

但我不会操作啊！！

算了，按照学长的左界$sort$先yy一波，灵光一闪！从$s_1$开始遍历到$s_n$，每循环到一个点$i$就把左界小于$i$的还未取反的区间给进行取反，

然后把区间左界$l$压入以右界$r$为关键词的一个动态数组（$vector$）$e[r]$，然后再把$e[i-1]$里的左界一一取出，再进行一次取反（两次取反便为还原，就相当于把区间给排除了）。

forth

具体的区间取反使用线段树实现，这样我们就很愉快地切题了

时间复杂度$O(L+klogL)$，$L$为s中不同数值的个数， 感觉应该比$O(n+klogn)$的期望要好些

fifth

祝大家切题愉快

sixth

附上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;i++)
#define xx 110000
#define int long long
#define ll long long
inline int read()
{
    int x=0,f=1;char ch=getchar();
    for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
int s2[xx],s1[xx],s[xx],cnt[xx];    //s存战斗力，s2存排序后的，s1存s2去重后的，再将s1里的排名赋到s上
int n,c[4][xx],all=0;  //c存组合数（当然也可以在线算），all记录s2长度
struct prom{int a,b;}t[xx];  //存储区间
struct linetree{int l,r,tot,sum;bool tag;}lt[xx<<2];  //tot存储总数，sum存储被取反数
inline bool cmp(prom x,prom y){return x.a<y.a;}
vector<int>e[xx];
inline int look2(int x)  //取出s1中第一个小于等于x的数的下标，即排名
{
    int head=1,tail=all,ans=1;
    while(head<=tail)
    {
        int mid=(head+tail)>>1;
        if(s1[mid]<=x) ans=mid,head=mid+1;
        else tail=mid-1;
    }
    return ans;
}
inline int look1(int x)  //取出s1中第一个大于等于x的数
{
    int head=1,tail=all,ans=all;
    while(head<=tail)
    {
        int mid=(head+tail)>>1;
        if(s1[mid]>=x) ans=mid,tail=mid-1;
        else head=mid+1;
    }
    return ans;
}
 
//------------
 
//线段树
inline void up(int k)
{
    int q=k<<1;
    lt[k].sum=lt[q].sum+lt[q+1].sum;
    lt[k].tot=lt[q].tot+lt[q+1].tot;
}
inline void down(int k)
{
    if(lt[k].tag)
    {
        int q=k<<1;
        lt[q].sum=lt[q].tot-lt[q].sum;
        lt[q+1].sum=lt[q+1].tot-lt[q+1].sum;
        lt[q].tag^=1;
        lt[q+1].tag^=1;
        lt[k].tag^=1;
    }
}
inline void build(int k,int i,int j)
{
    lt[k].l=i;
    lt[k].r=j;
    if(i==j)
    {
        lt[k].tot=cnt[i];
        return;
    }
    int q=k<<1,mid=(i+j)>>1;
    build(q,i,mid);
    build(q+1,mid+1,j);
    up(k);
}
inline void change(int k,int i,int j)
{
    if(i<=lt[k].l&&j>=lt[k].r)
    {
        lt[k].sum=lt[k].tot-lt[k].sum;
        lt[k].tag^=1;
        return;
    }
    down(k);
    int q=k<<1,mid=lt[q].r;
    if(i<=mid) change(q,i,j);
    if(j>mid) change(q+1,i,j);
    up(k);
}
inline int askus(int k,int i,int j) //访问区间中没有被取反的数的个数
{
    if(i>j) return 0;
    if(i<=lt[k].l&&j>=lt[k].r) return lt[k].tot-lt[k].sum;
    down(k);
    int q=k<<1,mid=lt[q].r,res=0;
    if(i<=mid) res+=askus(q,i,j);
    if(j>mid) res+=askus(q+1,i,j);
    return res;
}
inline int askrs(int k,int i,int j) //访问区间中被取反的数的个数
{
    if(i>j) return 0;
    if(i<=lt[k].l&&j>=lt[k].r) return lt[k].sum;
    down(k);
    int q=k<<1,mid=lt[q].r,res=0;
    if(i<=mid) res+=askrs(q,i,j);
    if(j>mid) res+=askrs(q+1,i,j);
    return res;
}
//线段树
 
//------------
 
signed main()
{
    n=in;
    fur(i,1,n)
    {
        c[0][i]=1;c[1][i]=i;
        fur(j,2,min(i,3ll)) c[j][i]=c[j-1][i-1]+c[j][i-1];
    }
    int k=in;
    fur(i,1,n) s2[i]=s1[i]=s[i]=in;
    sort(s2+1,s2+n+1);
    fur(i,1,n)
    {
        while(s2[i]==s2[i+1]) i++;
        s1[++all]=s2[i];
    }
    fur(i,1,n) s[i]=look1(s[i]),cnt[s[i]]++;
    sort(s+1,s+n+1);
    build(1,1,s[n]);
    fur(i,1,k) t[i].a=in,t[i].b=in;
    fur(i,1,k) t[i].a=look1(t[i].a),t[i].b=look2(t[i].b);
    sort(t+1,t+k+1,cmp);
    int ans=c[3][n],tnt=1;
    fur(i,1,s[n])
    {
        while(t[tnt].a<=i&&tnt<=k)  //先算区间左界小于等于当前i的
        {
            change(1,t[tnt].a,t[tnt].b);
            e[t[tnt].b].push_back(t[tnt].a);
            tnt++;
        }
        fur(j,0,(int)e[i-1].size()-1) change(1,e[i-1][j],i-1ll);  //再删区间右界小于当前i的
        int res=0;
        res+=askus(1,1,i-1);
        res+=askrs(1,i+1,s[n]);
        ans-=cnt[i]*c[2][res];
        ans-=c[2][cnt[i]];
    }
    printf("%lld\n",ans);
    return 0;
}