poj2274 The Race —— 逆序对，树状数组和线段树

Description

During the Annual Interstellar Competition for Tuned Spaceships, N spaceships will be competing. Each spaceship i is tuned in such a way that it can accelerate in zero time to its maximum speed Vi and remain cruising at that speed. Due to past achievements, each spaceship starts at a starting position Xi, specifying how many kilometers the spaceship is away from the starting line.
The race course is infinitely long. Because of the high speeds of the spaceships, the race course goes straight all the time. On that straight course, spaceships can pass one another very easily, without interfering with each other.
Many people in the audience have not realized yet that the outcome of the race can be determined in advance. It is your task to show this to them, by telling them how many times spaceships will pass one another, and by predicting the first 10 000 times that spaceships pass in chronological order.
You may assume that each spaceship starts at a different position. Furthermore, there will never be more than two spaceships at the same position of the course at any time.

Input

The first line of the input specifies the number of spaceshipsN (0 < N <= 250 000) that are competing. Each of the next N lines describe the properties of one spaceship. The i+1th line describes the ith ship with two integers Xi and Vi, representing the starting position and the velocity of the ith spaceship (0 <= Xi <= 1 000 000, 0 < Vi < 100). The spaceships are ordered according to the starting position, i.e. X1 < X2 < … < XN. The starting position is the number of kilometers past the starting line where the spaceship starts, and the velocity is given in kilometers per second.
Output

The first line of the output should contain the number of times that spaceships pass one another during the race modulo 1 000 000. By publishing the number of passes only modulo 1 000 000, you can at the same time prove your knowledge of it and don’t spoil the party for the less intelligent people in the audience.
Each of the subsequent lines should represent one passing, in chronological order. If there would be more than 10 000 passings, only output the first 10 000 passings. If there are less than 10 000 passings, output all passings. Each line should consist of two integers i and j, specifying that spaceship i passes spaceship j. If multiple passings occur at the same time, they have to be sorted by their position on the course. This means that passings taking place closer to the starting line must be listed first. The time of a passing is the time when the two spaceships are at the same position.
Sample Input

4
0 2
2 1
3 8
6 3
Sample Output

2
3 4
1 2

第一个很简单，就是逆序对的做法，只要找这个数之前有多少比他大的数就好了，
第二个我就想不出来了，也是看了别人才会做的。
首先坑定是两个相邻的车才是最快超越对方的，这个自己想想就出来了。
然后我们只需要建一个线段树找每次最快超越了那个相邻的两辆车，怎么找？
首先如果左边的车速度小于等于右边的车，那么就不可能相互超越，那么就标为-1，否则就标为左边的下标，注意不能他的位置是可以等于0的，所以不能在不允许的情况标成0，然后pushup，要注意的就是pushup会有几种情况，我就说说两个都不为-1的吧，因为t=s/v$t=s/v$，那么就只需要找到t最小的就好了。然后pushup= =。输出之后就要交换两辆车在线段树中的位置而不是实际位置代表这辆车已经被超过了，那么会波及m-1和m+1两个位置的值，然后判断一下需不需要交换，n-1是因为在n的时候就没有r值了。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<stdlib.h>
using namespace std;
#define ll long long
const ll mod=1e6;
const int maxn=1e6+5;
struct tree
{
    int l,r,pos;
}p[maxn*4],t[maxn*4];
int pos[maxn],n;
ll sum[105];
double v[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos)
{
    for(int i=pos;i>=1;i-=lowbit(i))
        sum[i]++;
}
ll query(int pos)
{
    ll ans=0;
    for(int i=pos;i<=100;i+=lowbit(i))
        ans+=sum[i];
    return ans;
}
void pushup(int root)
{
    if(p[root<<1].pos==-1&&p[root<<1|1].pos==-1)
        p[root].pos=-1;
    else if(p[root<<1].pos==-1)
        p[root].pos=p[root<<1|1].pos;
    else if(p[root<<1|1].pos==-1)
        p[root].pos=p[root<<1].pos;
    else
    {
        int l=p[root<<1].pos,r=p[root<<1|1].pos;
        double t1=(pos[t[l].r]-pos[t[l].l])/(v[t[l].l]-v[t[l].r]);
        double t2=(pos[t[r].r]-pos[t[r].l])/(v[t[r].l]-v[t[r].r]);
        if(t1<=t2)
            p[root].pos=l;
        else
            p[root].pos=r;
    }
}
void build(int l,int r,int root)
{
    p[root].l=l;
    p[root].r=r;
    p[root].pos=-1;
    if(l==r)
    {
        if(v[t[l].l]>v[t[l].r])
            p[root].pos=t[l].l;
        else
            p[root].pos=-1;
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    pushup(root);
}
void update(int l,int r,int root,int q)
{
    if(l==r)
    {
        if(v[t[l].l]>v[t[l].r])
            p[root].pos=l;
        else
            p[root].pos=-1;
        return ;
    }
    int mid=l+r>>1;
    if(mid>=q)
        update(l,mid,root<<1,q);
    else
        update(mid+1,r,root<<1|1,q);
    pushup(root);
}
void solve()
{
    for(int i=1;i<n;i++)
        t[i].l=i,t[i].r=i+1;
    build(1,n,1);
    int cas=0;
    while(cas<10000)
    {
        if(p[1].pos==-1)
            break;
        int m=p[1].pos;
        printf("%d %d\n",t[m].l,t[m].r);
        swap(t[m].l,t[m].r);
        update(1,n,1,m);
        if(m-1>=1)
        {
            t[m-1].r=t[m].l;
            update(1,n,1,m-1);
        }
        if(m+1<n)
        {
            t[m+1].l=t[m].r;
            update(1,n,1,m+1);
        }
        cas++;
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        ll ans=0;
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
        {
            scanf("%d%lf",&pos[i],&v[i]);
            add(v[i]);
            (ans+=query(v[i]+1))%=mod;
        }
        printf("%lld\n",ans);
        if(ans!=0)
            solve();
    }
    return 0;
}