转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题意：给出n个人，每个人有个战力值，战力大的获胜。现在有k个区间，如果两个人的战力都在区间内，则会更改交战结果。问最后有多少个三元组(i,j,k)满足,i>j,j>k,k>i。
这题的一个转换是交补，C(n,3)是总共的三元组数目，求出有多少个不满足的。
不满足的肯定是其中1个人战胜了2个人。那么做法就是枚举这个人，判断他能战胜m个人，那么就应该减去C(m,2)
用线段树来维护。
初始状态全为0，更改则为1。
那么对于枚举当前人，他能战胜的，就是战力比他小的，而且没有更改状态的
以及战力比他大的但是更改状态了。也就是[1,i-1]中的0，以及[i+1,n]中的1数目。
维护two points更新区间即可。
即枚举当前人i，所有有效的更新区间是i所包含的区间，其余区间不要更新，或者更新两次抵消掉
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define lson (step<<1)
#define rson (step<<1|1)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define LL long long
using namespace std;
const int N=100005;
struct Seg_tree{
int left,right;
int cnt[2],cover;
}L[N<<2];
int n,k,s[N];
vector<pair<int,int> >change,other;
void push_up(int step){
for(int i=0;i<2;i++)
L[step].cnt[i]=L[lson].cnt[i]+L[rson].cnt[i];
}
void push_down(int step){
if(L[step].cover){
L[lson].cover^=1;
L[rson].cover^=1;
swap(L[lson].cnt[0],L[lson].cnt[1]);
swap(L[rson].cnt[0],L[rson].cnt[1]);
L[step].cover=0;
}
}
void bulid(int step,int l,int r){
L[step].left=l;
L[step].right=r;
L[step].cover=0;
if(l==r){
L[step].cnt[0]=1;
L[step].cnt[1]=0;
return ;
}
int m=(l+r)>>1;
bulid(lson,l,m);
bulid(rson,m+1,r);
push_up(step);
}
void update(int step,int l,int r){
if(L[step].left==l&&L[step].right==r){
swap(L[step].cnt[0],L[step].cnt[1]);
L[step].cover^=1;
return ;
}
int m=(L[step].left+L[step].right)>>1;
push_down(step);
if(r<=m) update(lson,l,r);
else if(l>m) update(rson,l,r);
else{
update(lson,l,m);
update(rson,m+1,r);
}
push_up(step);
}
int query(int step,int l,int r,int c){
if(L[step].left==l&&L[step].right==r)
return L[step].cnt[c];
int m=(L[step].left+L[step].right)>>1;
push_down(step);
if(r<=m) return query(lson,l,r,c);
else if(l>m) return query(rson,l,r,c);
else return query(lson,l,m,c)+query(rson,m+1,r,c);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>s[i];
sort(s+1,s+1+n);
bulid(1,1,n);
for(int i=0;i<k;i++){
int a,b;
cin>>a>>b;
a=lower_bound(s+1,s+1+n,a)-s;
b=upper_bound(s+1,s+1+n,b)-s-1;
if(a>b) continue;
other.pb(mp(b,a));
change.pb(mp(a,b));
}
sort(change.begin(),change.end());
sort(other.begin(),other.end());
LL ans=(LL)n*(n-1)*(n-2)/6;
for(int i=1,j=0,r=0;i<=n;i++){
while(j<change.size()&&change[j].first==i){
update(1,change[j].first,change[j].second);
j++;
}
int win=0;
if(i>1) win+=query(1,1,i-1,0);
if(i<n) win+=query(1,i+1,n,1);
//cout<<win<<endl;
ans-=(LL)win*(win-1)/2;
while(r<other.size()&&other[r].first==i){
update(1,other[r].second,other[r].first);
r++;
}
}
cout<<ans<<endl;
return 0;
}