小W的问题
【问题描述】
有一天，小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”形的个数，也就是满足上面条件的五元点组个数。你能帮助他吗？
。
Input
第一行包含一个整数N，表示点的个数。
下面N行每行两个整数，第i+1行为(xi, yi)，表示第i个点的坐标。
Output
仅包含一行，为“W”形个数模1 000 000 007的值。
这道题我一开始不会做……感谢某神牛的讲解
顺带一提，没有重点
统计的形状十分蛋疼……必须严格是w形
需要把一个点当做研究对象，显然我们选取中间这个点
因为这个点左边和右边互不影响，方案数乘起来即可
问题转换成了统计312（就是指最左边最高，中间最低，最右边中间高）这种类型的数目，并把它存到2的位置
这个似乎不太好统计……所以采用容斥
显然，统计312+213也就是v形两边哪边高都行非常简单……排序后树状数组即可
那么如何求出312……？算出213即可
213似乎也不好求……
但可以发现，研究对象变成了最高的点，另外两个点在同一象限
那么我们可以很简单的算出123+213=([3左下角下的点数]-1)*[3左下角下的点数]/2
然后再减去123……
显然，123非常好求，排序后树状数组即可
细节比较多……认真思考后再开始写
program bzoj2441;
const
maxn=1000000007;
var
all,n,i,j,k:longint;
new,tree,dl,ans,x,y,u,d,c,o:array [0..200001] of longint;
function lowbit (x:longint):longint;inline;
begin
exit(x xor (x and (x-1)));
end;
procedure insert (p,x:longint);inline;
begin
if x=0 then exit;
while x<=n do
begin
tree[x]:=(tree[x]+p) mod maxn;
x:=x+lowbit(x);
end;
end;
function qsum (x:longint):longint;inline;
var
ans:longint=0;
begin
while x>0 do
begin
ans:=(ans+tree[x]) mod maxn;
x:=x-lowbit(x);
end;
exit(ans);
end;
procedure swap (var a,b:longint);inline;
begin
if a=b then exit;
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=new[(s+e) div 2];
while i<=j do
begin
while new[i]<k do inc(i);
while new[j]>k do dec(j);
if i>j then break;
swap(new[i],new[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
function convert (x:longint):longint;inline;
var
s,e,mid:longint;
begin
s:=1;
e:=all;
while s<>e do
begin
mid:=(s+e) div 2;
if new[mid]<x then s:=mid+1
else e:=mid;
end;
exit(s);
end;
procedure calc;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=dl[(s+e) div 2];
while i<=j do
begin
while (x[dl[i]]<x[k])or((x[dl[i]]=x[k])and(y[dl[i]]<y[k])) do inc(i);
while (x[dl[j]]>x[k])or((x[dl[j]]=x[k])and(y[dl[j]]>y[k])) do dec(j);
if i>j then break;
swap(dl[i],dl[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
begin
qsort(1,n);
fillchar(tree,sizeof(tree),0);
i:=1;
while i<=n do
begin
k:=i;
while (i<=n)and(x[dl[i]]=x[dl[k]]) do
begin
d[dl[i]]:=qsum(y[dl[i]]);
if d[dl[i]]>0 then d[dl[i]]:=int64(d[dl[i]]-1)*d[dl[i]] div 2 mod maxn;
inc(i);
end;
for j:=k to i-1 do
insert(1,y[dl[j]]);
end;
fillchar(tree,sizeof(tree),0);
for i:=1 to n do
begin
c[dl[i]]:=qsum(y[dl[i]]);
insert(1,y[dl[i]]);
end;
fillchar(tree,sizeof(tree),0);
o:=c;
i:=1;
while i<=n do
begin
k:=i;
while (i<=n)and(x[dl[i]]=x[dl[k]]) do
begin
c[dl[i]]:=qsum(y[dl[i]]);
inc(i);
end;
for j:=k to i-1 do
insert(o[dl[j]],y[dl[j]]);
end;
fillchar(tree,sizeof(tree),0);
i:=1;
while i<=n do
begin
k:=i;
while (i<=n)and(x[dl[i]]=x[dl[k]]) do
begin
u[dl[i]]:=qsum(all)-qsum(y[dl[i]]);
inc(i);
end;
for j:=k to i-1 do
insert(1,y[dl[j]]);
end;
fillchar(tree,sizeof(tree),0);
o:=u;
i:=1;
while i<=n do
begin
k:=i;
while (i<=n)and(x[dl[i]]=x[dl[k]]) do
begin
u[dl[i]]:=qsum(y[dl[i]]-1);
inc(i);
end;
for j:=k to i-1 do
insert(o[dl[j]],y[dl[j]]);
end;
for i:=1 to n do
ans[dl[i]]:=ans[dl[i]]*int64(u[dl[i]]-(d[dl[i]]-c[dl[i]])) mod maxn;
end;
begin
read(n);
for i:=1 to n do
read(x[i],y[i]);
for i:=1 to n do
new[i]:=y[i];
qsort(1,n);
i:=1;
while i<=n do
begin
inc(all);
new[all]:=new[i];
while (i<=n)and(new[i]=new[all]) do inc(i);
end;
for i:=1 to n do
y[i]:=convert(y[i]);
for i:=1 to n do
ans[i]:=1;
for i:=1 to n do
dl[i]:=i;
calc;
for i:=1 to n do
x[i]:=-x[i];
calc;
k:=0;
for i:=1 to n do
k:=(k+ans[i]) mod maxn;
writeln((k+maxn) mod maxn);
end.