题目大意
给出n个正整数，由大小确定数与数之间的指向关系（大的指向小的），其中大小处在某一区间的数指向关系全部取反，问n个数之间的三元环个数
正在做学长推荐的数据结构题，莫名看到了这道数学（蒟蒻感觉对这种有数学成分的题相当无力啊），于是本蒟蒻想（kan ti jie）了好久好久，终于受到学长数学+数据结构的真传切了这题（先orz切题的大佬一波）
具体思路
first
不管怎样，(s_i)数值范围很大，而区间取反也是从数值入手，既然如此，不管三七二十一，先把数值离散化一波，用数值大小的排名代替数值，将数值范围化为(1-n)，然后把要取反的区间两端做同样的操作。又因为反正是数值区间上的取反，干脆把所有数再排下序,这样基本操作就完成了。
second
三元环不好直接求，，终于发现可以 容斥 一波，先求出所有方案：
[C_n^3
]
然后是不符合题意的方案数，本蒟蒻觉得分为两种：
- 一群牛之间互相都不可以击败对方（即一堆相等的正整数），这样的一堆数之间没有指向性。这样的话，我们可以用一个数组(cnt_x)，来记录数x出现的个数，而明显看得出来，只要在每堆这些相等的数中任意取2个，则方案不合理。综上，该情况的不合理方案为(式子里的(s_i)为离散化处理过的(s_i)数组)：
[sum_{i=s_1}^{s_n}{C_{cnt_{i}}^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
",ans);
return 0;
}