poj 2274 The Race（逆序數+線段樹）

poj 2274 The Race（逆序數+線段樹）

The Race Time Limit: 15000MS Memory Limit: 65536K Total Submissions: 3237 Accepted: 664 Case Time Limit: 3000MS

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

題意：飛船往同一方向飛，已知每個飛船的起點（不重合）和速度，問題一：每個飛船被超過的次數的總和（模1000000）；問題二：輸出前10000次超越，按照時間排序，若時間相同按照超越別飛船的飛船的輸入順序排序。

解題思路：

問題一：按照起點排序（輸入已經給我們排好），若前一個速度比當前的速度大，則前面那個飛船一定能超越當前飛船，否則不可能。因此，只要算一下逆序數和就可以了。

問題二：第一個超越的一定是相鄰兩個飛船。

反證：設當前位置為A-B-C,若第一次超越為A->C，則必定A->B或B->C，與A->C為第一次超越矛盾。

因此：

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcHJlPgo8cHJlIGNsYXNzPQ=="brush:java;">這樣，我就能保證每次輸入的就是當前最早超越的飛船！

頂層設計完了之後就是實現問題了，逆序數我用的是線段樹。尋找超越飛船我也用了線段樹，把每段線段當作一個點，然後每次查詢最小，單點更新。

#include 
#include 
#include 
#include 
using namespace std;

const int maxn1 = 250010;
const int maxn2 = 110;
const int mod = 1000000;
struct tree1{
    int l , r , sum;
}a1[4*maxn2];
struct plane{
    int x , v;
}P[maxn1];
struct tree2{
    int l , r , Max;
}a2[4*maxn1];
struct Node{
    int l , r;
}node[maxn1];
int N;

void build1(int l , int r , int k){
    a1[k].l = l;
    a1[k].r = r;
    a1[k].sum = 0;
    if(l != r){
        int mid = (l+r)/2;
        build1(l , mid , 2*k);
        build1(mid+1 , r , 2*k+1);
    }
}

void add1(int l , int r , int k){
    if(l <= a1[k].l && a1[k].r <= r) a1[k].sum++;
    else{
        int mid = (a1[k].l+a1[k].r)/2;
        if(mid >= r) add1(l , r , 2*k);
        else add1(l , r , 2*k+1);
        a1[k].sum = (a1[2*k].sum+a1[2*k+1].sum)%mod;
    }
}

int query1(int l , int r , int k){
    if(l <= a1[k].l && a1[k].r <= r) return a1[k].sum;
    else{
        int mid = (a1[k].l+a1[k].r)/2;
        if(mid >= r) return query1(l , r , 2*k)%mod;
        else if(l > mid) return query1(l , r , 2*k+1)%mod;
        else return (query1(l , mid , 2*k)+query1(mid+1 , r , 2*k+1))%mod;
    }
}

void pushup(int k){
    if(a2[2*k].Max == -1 && a2[2*k+1].Max == -1) a2[k].Max = -1;
    else if(a2[2*k].Max == -1) a2[k].Max = a2[2*k+1].Max;
    else if(a2[2*k+1].Max == -1) a2[k].Max = a2[2*k].Max;
    else{
        int lson = a2[2*k].Max , rson = a2[2*k+1].Max;
        int lnode = (P[node[lson].r].v-P[node[lson].l].v)*(P[node[rson].r].x-P[node[rson].l].x);
        int rnode = (P[node[rson].r].v-P[node[rson].l].v)*(P[node[lson].r].x-P[node[lson].l].x);
        if(lnode <= rnode) a2[k].Max = a2[2*k].Max;
        else a2[k].Max = a2[2*k+1].Max;
    }
}

void build2(int l , int r , int k){
    a2[k].l = l;
    a2[k].r = r;
    a2[k].Max = -1;
    if(l == r){
        if(P[node[l].l].v <= P[node[l].r].v) a2[k].Max = -1;
        else a2[k].Max = l;
    }else{
        int mid = (l+r)/2;
        build2(l , mid , 2*k);
        build2(mid+1 , r , 2*k+1);
        pushup(k);
    }
}

void update(int l , int r , int k){
    if(l <= a2[k].l && a2[k].r <= r){
        if(P[node[l].l].v <= P[node[l].r].v) a2[k].Max = -1;
        else a2[k].Max = l;
    }else{
        int mid = (a2[k].l+a2[k].r)/2;
        if(r <= mid) update(l , r , 2*k);
        else update(l , r , 2*k+1);
        pushup(k);
    }
}

void computing(){
    for(int i = 1; i < N; i++){
        node[i].l = i;
        node[i].r = i+1;
    }
    build2(1 , N-1 , 1);
    int cnt = 0;
    while(cnt < 10000){
        if(a2[1].Max == -1) break;
        int m = a2[1].Max;
        printf("%d %d\n" , node[m].l , node[m].r);
        swap(node[m].l , node[m].r);
        update(m , m , 1);
        if(m-1 >= 1){
            node[m-1].r = node[m].l;
            update(m-1 , m-1 , 1);
        }
        if(m+1 < N){
            node[m+1].l = node[m].r;
            update(m+1 , m+1 , 1);
        }
        cnt++;
    }
}

void readcase(){
    build1(1 , 100 , 1);
    int ans = 0;
    for(int i = 1; i <= N; i++){
        scanf("%d%d" , &P[i].x , &P[i].v);
        ans = (ans+query1(P[i].v+1 , 100 , 1))%mod;
        add1(P[i].v , P[i].v , 1);
    }
    printf("%d\n" , ans);
    if(ans != 0) computing();
}

int main(){
    while(~scanf("%d" , &N)){
        readcase();
    }
    return 0;
}