王峥睿
(王峥睿)
1
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,len,tr[10*N],vis1[100010],vis2[100010];
struct node
{
int x,y;
};
node a[N];
struct t
{
int y,l=1e9,r=-1e9;
vector<int> a;
vector<int> b;
};
t b[N];
map<int,int> lsh;
bool cmp(node x,node y)
{
if(x.y!=y.y)
{
return x.y<y.y;
}
return x.x<y.x;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int date)
{
while(x<=1e6)
{
tr[x]+=date;
x+=lowbit(x);
}
return;
}
int query(int x)
{
int ans=0;
while(x>0)
{
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
int qu(int l,int r)
{
return query(r)-query(l-1);
}
int main()
{
//freopen("uoj.in","r",stdin);
//freopen("uoj.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
lsh[a[i].x]=0;
lsh[a[i].y]=0;
}
int idx=0;
for(auto it=lsh.begin();it!=lsh.end();it++)
{
it->second=++idx;
}
for(int i=1;i<=n;i++)
{
a[i].x=lsh[a[i].x];
a[i].y=lsh[a[i].y];
}
sort(a+1,a+n+1,cmp);
idx=0;
for(int i=1;i<=n;i++)
{
if(a[i].y!=b[idx].y)
{
b[idx].r=a[i-1].x;
b[++idx].y=a[i].y;
b[idx].l=a[i].x;
}
if(vis1[a[i].x]==0)
{
vis1[a[i].x]=1;
b[idx].a.push_back(a[i].x);
}
}
b[idx].r=a[n].x;
m=idx;
for(int i=n;i>=1;i--)
{
if(a[i].y!=b[idx].y)
{
idx--;
}
if(vis2[a[i].x]==0)
{
vis2[a[i].x]=1;
b[idx].b.push_back(a[i].x);
}
}
int ans=0;
for(int i=1;i<=m;i++)
{
for(int j=0;j<b[i].a.size();j++)
{
update(b[i].a[j],1);
}
ans+=qu(b[i].l,b[i].r);
for(int j=0;j<b[i].b.size();j++)
{
update(b[i].b[j],-1);
}
}
cout<<ans;
}
/*
11
1 2
3 2
3 4
4 2
4 1
5 3
4 3
6 4
5 4
4 5
1 5
12
*/
王峥睿
(王峥睿)
7
很明显，只有在两条水平与竖直直线相截时，才可能出现一个点
王峥睿
(王峥睿)
12
我把除了int main()以外所有int全变成了long long,还是WA
王峥睿
(王峥睿)
13
从下到上扫描每条水平线段，记录在这条水平线段内的答案。每次可能有多条竖线经过这一行，在从下往上扫时用权值树状数组维护这条水平线段内的线段总数量（因为每个时刻可能会有一条竖线离开或经过，带修的，用权值树状数组）
1 个赞
王峥睿
(王峥睿)
17
啊啊啊啊啊跳出来了
int n,m,len,tr[10*N],vis1[200010],vis2[200010];
为什么没有REqwq