题意:
求满足(x1<x2<x3)和(y2<y1<y3)的三元组个数
思路:
不难想到先对(x)排序,再处理(y)的情况,然后就推不出来了。
应当排序后枚举每个点,每次将该点与前面的点统计答案,再将该点的贡献更新。
假设(sum1)表示第一个点的个数,(sum2)表示满足(x1<x2)和(y2<y1)的二元组个数。
假设枚举到的点为((x,y))
- 统计答案:查找(1<=y_{j}<y)的(sum2)值即为答案,因为(sum2)已经满足二元组,(x)已经排序,(y_{j}<y),满足三元组。
- 更新贡献:
更新(sum2):对于([y,+infty])的(sum1)都可以与((x,y))构成合法的二元组,所以要将([y,+infty])的(sum2)全部加(sum1).
更新(sum1):当枚举到后面的点时,点((x,y))可以作为第一个点,所以(y的sum1++)
区间修改单点修改区间查询用线段树来维护,先按(x)排序,再对(y)坐标离散化,建树。
只有(sum2)用到了区间修改的操作所以懒惰标记只记录(sum2)的就好。注意相同(x)轴坐标的要一起处理。
代码:
const int maxn=1e5+100;
struct node{
int x,y;
bool operator<(const node& a)const{
return x<a.x;
}
};
node p[maxn];
vector<int>v;
int n;
struct node1{
int l,r;
ll sum1,sum2,laz;///sum2的懒惰标记
}tr[maxn*4];
void pushup(int u){
tr[u].sum1=tr[u<<1].sum1+tr[u<<1|1].sum1;
tr[u].sum2=tr[u<<1].sum2+tr[u<<1|1].sum2;
}
void pushdown(int u){
if(tr[u].laz){
tr[u<<1].laz+=tr[u].laz;
tr[u<<1|1].laz+=tr[u].laz;
tr[u<<1].sum2+=tr[u<<1].sum1*tr[u].laz;
tr[u<<1|1].sum2+=tr[u<<1|1].sum1*tr[u].laz;
tr[u].laz=0;
}
}
void build(int u,int l,int r){
tr[u].l=l,tr[u].r=r;
tr[u].sum1=tr[u].sum2=tr[u].laz=0;
if(l==r) return ;
int mid=(l+r)/2;
build(u<<1,l,mid);build(u<<1|1,mid+1,r);
}
void update1(int u,int pos){//dan dian
if(tr[u].l==tr[u].r){
tr[u].sum1++;
return ;
}
int mid=(tr[u].l+tr[u].r)/2;
pushdown(u);
if(pos<=mid) update1(u<<1,pos);
else update1(u<<1|1,pos);
pushup(u);
}
void update2(int u,int l,int r){
if(tr[u].r<l||tr[u].l>r) return ;
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].sum2+=tr[u].sum1;
tr[u].laz++;
return ;
}
pushdown(u);
update2(u<<1,l,r);update2(u<<1|1,l,r);
pushup(u);
}
ll qask(int u,int l,int r){
ll res=0;
if(tr[u].r<l||tr[u].l>r) return 0;
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].sum2;
}
pushdown(u);
res=qask(u<<1,l,r)+qask(u<<1|1,l,r);
return res;
}
int get(int y){
return lower_bound(v.begin(),v.end(),y)-v.begin()+1;
}
int main(){
n=read;
rep(i,1,n){
p[i].x=read,p[i].y=read;
v.push_back(p[i].y);
}
sort(p+1,p+1+n);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
build(1,1,v.size());
ll res=0;
rep(i,1,n){
int j;
for(j=i;j<=n&&p[i].x==p[j].x;j++)
res=res+qask(1,1,get(p[j].y)-1);
for(j=i;j<=n&&p[i].x==p[j].x;j++)
update2(1,get(p[j].y)+1,v.size());
for(j=i;j<=n&&p[i].x==p[j].x;j++)
update1(1,get(p[j].y));
i=j-1;
}
printf("%lld
",res);
return 0;
}