题目描述

 有一天，小W找了一个笛卡尔坐标系，并在上面选取了N个整点。他发现通过这些整点能够画出很多个“W”出来。具体来说，对于五个不同的点(x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5)，如果满足：

·x1 < x2 < x3 < x4 < x5

·y1 > y3 > y2

·y5 > y3 > y4

则称它们构成一个“W”形。

现在，小W想统计“W”形的个数，也就是满足上面条件的五元点组个数。你能帮助他吗？

---

输入格式

    第一行包含一个整数N，表示点的个数。

下面N行每行两个整数，第i+1行为(xi, yi)，表示第i个点的坐标。

---

输出格式

仅包含一行，为“W”形个数模1 000 000 007的值。

---

 

• 题解

  • 题目中的"W"是左右对称的，并且由于左右两边都x轴严格所以互不影响
  • 那么对每个三号点统计出左"V"和右"V"相乘即可得到答案；
  • 下面的诉述均在三号点确定的情况下；
  • 考虑统计左"V"，即满足条件①的对数：
  • $①：x_{1} < x_{2} < x_{3}，y_{2} < y_{3} < y_{1}$
  • 采用容斥，首先按x坐标做扫描线，可以用两个树状数组统计出条件②：
  • $②：x_{1} < x_{2} < x_{3}，y_{1} > y_{2}且y_{2} < y_{3}$
  • ②包含①，和①对比需要再统计条件③：
  • $③：x_{1} < x_{2} < x_{3}，y_{2} < y_{1} <= y_{3}$
  • 统计在$x_{3}$严格左边，不严格的下边的点数$num$，$C_{num}^{2}$ 可表示条件④：
    $④：x_{1} <= x_{2} < x_{3}，y_{1},y_{2}<= y_{3}$
  • 用一个树状数组去掉$x$轴的等号进一步统计⑤:
  • $⑤：x_{1} < x_{2} < x_{3}，y_{1},y_{2} <= y_{3}$
  • 同理用两个树状数组统计⑥：
  • $⑥：x_{1} < x_{2} < x_{3}，y_{1} <= y_{2} <= y_{3}$
  • 用⑥减去⑤得到③，用②减去③得到①；
  • 写得比较复杂，建议画图思考，想清楚再写代码不然很容易重构TAT.........
• 1 #include
          
            2 #define ll long long 3 using namespace std; 4 const int N=200010,mod=1e9+7; 5 int n,sub[N],tot,t1[N],t2[N],t3[N],t[N],L[N],R[N]; 6 ll c1[N],c2[N],c3[N];  7 struct P{ 8     int x,y,id; 9     P(int _x=0,int _y=0):x(_x),y(_y){};10 }p[N]; 11 bool cmp1(const P&a,const P&b){
        return a.x==b.x?a.y
           
            
             b.x;}13 char gc(){14     static char*p1,*p2,s[1000000];15     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);16     return(p1==p2)?EOF:*p1++; 17 }18 int rd(){19     int x=0; char c=gc();20     while(c<'0'||c>'9')c=gc();21     while(c>='0'&&c<='9')x=x*10+c-'0',c=gc();22     return x;23 }24 void init(){memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));memset(c3,0,sizeof(c3));}25 void add1(int x,int y){
        for(;x<=tot;x+=x&-x)c1[x]+=y;}26 int que1(int x){ll re=0;for(;x;x-=x&-x)re+=c1[x];return re%mod;}27 void add2(int x,int y){
        for(;x<=tot;x+=x&-x)c2[x]+=y;}28 int que2(int x){ll re=0;for(;x;x-=x&-x)re+=c2[x];return re%mod;}29 void add3(int x,int y){
        for(;x<=tot;x+=x&-x)c3[x]+=y;}30 int que3(int x){ll re=0;for(;x;x-=x&-x)re+=c3[x];return re%mod;}31 void upd(int&x,int y){x+=y;if(x>=mod)x-=mod;}32 void solve(){33     for(int i=1,j=1;i<=n;i=j){34         for(j=i;j<=n&&p[j].x==p[i].x;++j){35             t1[j]=que1(p[j].y);36             t2[j]=i-1-t1[j];37             t3[j]=j-i;38             t[j]=mod-1ll*t1[j]*(t1[j]-1)/2%mod;39             if(t[j]==mod)t[j]=0;40         }41         for(int k=i;k
             
              >1;++i)swap(p[i],p[n-i+1]);70     init();71     sort(p+1,p+n+1,cmp2);72     solve();73     for(int i=1;i<=n;++i)R[p[i].id]=t[i];74     ll ans=0;for(int i=1;i<=n;++i)ans=(ans+1ll*L[i]*R[i]%mod)%mod;75 //    for(int i=1;i<=n;++i)printf("%d %d\n",L[i],R[i]);76     cout<
              
               <