台湾菜

POJ 3416 Crossing

twcai • acm/icpc

区间统计的题目,不过因为数据范围很大,内存会吃不消,所以需要用到降维。即先按照X轴排序,然后对Y轴进行区间统计。其实这道题目可以看成POJ2352的扩展,2352是对某点左下方的点进行统计。
而这道题目可以看成统计给出的坐标原点左下方(第三区间)的点数,第四区间可以通过原点下方的点数减去第三区间点数得到,第二区间可以通过原点左方的点数减去第三区间点数得到。
这道题目的数据量很大,我把qsort换成手打快排,原先用二分查找所有点集中的原点,后来换成直接标记原点的位置,也没有明显的优化。。
#include
using namespace std;

struct point{
int x;
int y;
int fl;
};
point d[100002];
int w[50002];
int no[50002];
int nn[50002];
int bit[500002];
int n,m,top;

inline int lowbit(const int &x)
{
if(x==0) return 1;
return x&(-x);
}

inline void plus(int x)
{
while(x<=top)
{
bit[x]++;
x+=lowbit(x);
}
}

inline int sum(int x)
{
int s=0;
while(x>0)
{
s+=bit[x];
x-=lowbit(x);
}
return s;
}

inline void QuickSort(int low, int high)
{
int LOW,HIGH;
point key;
if(low>=high) return;
key=d[low];LOW=low;HIGH=high;
while(low {
while(low {
if(d[high].x {d[low++]=d[high];break;}
high--;
}
while(low {
if(d[low].x>key.x || (d[low].x==key.x && d[low].y>key.y))
{d[high--]=d[low];break;}
low++;
}
}
d[low]=key;
QuickSort(LOW,low-1);
QuickSort(low+1,HIGH);
}

int main()
{
int t,c,tol,t0,t1;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
top=0;
for(int i=0;i {
scanf("%d %d",&d[i].x,&d[i].y);
d[i].fl=0;
if(top }
tol=n+m;
for(int i=0;i {
t0=n+i;
scanf("%d %d",&d[t0].x,&d[t0].y);
d[t0].fl=i+1;
if(top }
QuickSort(0,tol-1);
for(int i=0;i<=top+1;i++) bit[i]=0;
c=0;
for(int i=0;i {
if(!d[i].fl) {plus(d[i].y);c++;}
else {no[d[i].fl]=sum(d[i].y);nn[d[i].fl]=c;w[d[i].fl]=i;}
}
for(int i=1;i<=m;i++)
{
t0=no[i]; //第三区间
t1=sum(d[w[i]].y)-t0; //第四区间
t1+=nn[i]-t0; //加上第二区间
t0=n-t1;
printf("%dn",abs(t1-t0));
}
if(t!=0) printf("n");
}
return 0;
}

/*
3
6 1
11 2
1 2
3 22
20 5
7 11
9 22
10 30
*/

comments powered by Disqus