飞船赛跑（race） CEOI2003

时间：2010-11-08 来源：LitIce

你的任务是算出一共有多少次“超车”，并按时间顺序输出前10000次。保证在同一时刻不会有两个以上的飞船位于同一位置。

输入：

第1行：N（0<=N<=250000）

第（i+1）行：Xi和Vi（0<=Xi<=1000000, 0<Vi<100）

后N行是Xi按升序排列的。

输出：

第1行：“超车”次数对1000000的模。

接下来按时间顺序每行输出i和j，表示第i个飞船超过第j个飞船。若两次超车在同一时刻发生，则按“超车”地点与起跑线的距离由小到大排序。

若“超车”次数大于10000，则输出前10000次，否则输出全部。

Sample Input

0 2

2 1

3 8

6 3

Sample Output

3 4

1 2

Source

CEOI 2003

第一问求逆序对。因为速度都比较小，我就用了树状数组。速度大点的话用归并解决。

第二问求前10000小时间，时间相同安相遇地点前后排序。就维护一个堆，以每个节点各自追上前一个的时间为关键字建成最小堆。再一个链表维护当前的位置关系。每次取出堆顶之后有可能改变的就该节点和前驱和后继节点。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#define P 1000000
#define N 1000000
#define INF 1000000000
#define LL long long
using namespace std;

LL  a[300],X[300000],V[300000];
LL  heap[N],palce[N],pred[N],next[N],place[N];
double t1,t2;
LL  ans,n,x,y,size,now,pre,nex,t,j;
LL  lowbit(LL  x)
{
    return (x & (-x) ) ;
}
LL  sum(LL  x)
{
    LL  tt=0;
    while (x>0) 
    {
          tt+=a[x];tt%=P;
          x-=lowbit(x);
    }
    return tt;
}
void add(LL  x)
{
    if (x==0) return;
    while (x<=256)
    {
          a[x]+=1;
          x+=lowbit(x);
    }
}
double calc(LL  x,LL  y)
{
     if (y==-1) return INF;
     if (x==-1) return INF;
     if (V[x]==V[y]) return INF;
     if (V[x]<V[y]) return INF;
     return double(X[y]-X[x])/(V[x]-V[y]);
}
bool Bigger(LL  i,LL  j)
{
     i=heap[i];j=heap[j];
     t1=calc(i,pred[i]);t2=calc(j,pred[j]);
     if (abs(t1-t2)<0.00001)
     {
        if (X[i]<X[j]) return 1; else return 0;
     } 
     if (t1>t2) return 0; else return 1;
}
void swap(LL  i,LL  j)
{
     x=heap[i];y=heap[j];
     t=heap[i];heap[i]=heap[j];heap[j]=t;
     t=place[x];place[x]=place[y];place[y]=t;
}
void down(LL  i)
{
    while (i*2<=size)
    {
          j=i*2;
          if (j<size && Bigger(j+1,j) )  ++j;
          if (Bigger(j,i) ) 
          {
             swap(i,j);
             i=j;
          } else return;
    }
}
void up(LL  i)
{
    while (i>1)
    {     
          if (Bigger(i,i/2) ) 
          {
             swap(i,i/2);
             i=i/2;
          } else return;
    }
}
int  main()
{
    freopen("race.in","r",stdin);
    freopen("race.out","w",stdout);
    scanf("%I64d",&n);
    for (LL  i=1;i<=n;++i) scanf("%I64d%I64d",&X[i],&V[i]);
    
    for (LL  i=n;i>=1;--i)
    {
        ans+=sum(V[i]-1);
        ans%=P;
        add(V[i]);
    }
    printf("%I64d\n",ans);
    
    for (LL  i=1;i<=n;++i) pred[i]=i+1,next[i]=i-1;
    pred[n]=-1;next[1]=-1;
    
    heap[1]=1;place[1]=1;size=1;
    
    for (LL  i=2;i<=n;++i) 
    {
        ++size;heap[size]=i;place[i]=size;
        up(size);
    }
    
    for (LL  i=1;i<=10000;++i)
    {
        now=heap[1];
        pre=pred[now];nex=next[now];
        if (calc(now,pre)==INF) break;
        
        pred[now]=pred[pre];
        next[now]=pre;
        if (pred[pre]!=-1) next[pred[pre]]=now;
        pred[pre]=now;
        next[pre]=nex;
        if (nex!=-1) pred[nex]=pre;
        
        printf("%I64d %I64d\n",now,pre);
        
        if (now!=-1) {up(place[now]);down(place[now]);}
        if (pre!=-1) {up(place[pre]);down(place[pre]);}
        if (nex!=-1) {up(place[nex]);down(place[nex]);}
    }
    
    return 0;   
}