这真的是一道数据结构的好题。

题意是在一条直线上有n辆车，每辆车有一个初始位置x[i]和速度v[i],问最终（在无限时间后）一共会发生多少次超车事件（mod 1000000），以及输出这些事件（如果大于10000次输出前10000次）

对于第一问，很明显的求逆序对，如果满足x[i]<x[j]且v[i]>v[j]，那么就会产生超车事件

所以树状数组即可

第二问则比较复杂，但我们可以发现每次超车发生时都是相邻的两车

所以我们发现这个可以用堆来维护

要注意一下的是当事件发生的时间相同时，要按编号大小进行输出（WA死在这里）

只要堆的 bool operator 重载一下即可

CODE

#include<cstdio>

#include<queue>

using namespace std;

typedef double DB;

const int N=250005,mod=1000000;

int tree[105],n,x[N],v[N],num[N],id[N],t,ans;

struct data

{

	int x,y;

	DB t;

	bool operator <(const data &s) const

	{

		if (s.t<t) return 1;

		if (s.t>t) return 0;

		return num[s.x]<num[x];

	}

};

priority_queue <data> heap;

inline char tc(void)

{

	static char fl[100000],*A=fl,*B=fl;

	return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

	x=0; char ch=tc();

	while (ch<'0'||ch>'9') ch=tc();

	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();

}

inline void write(int x)

{

	if (x/10) write(x/10);

	putchar(x%10+'0');

}

inline int lowbit(int x)

{

	return x&(-x);

}

inline void add(int x)

{

	while (x)

	{

		++tree[x];

		x-=lowbit(x);

	}

}

inline int get(int x)

{

	int res=0;

	while (x<100)

	{

		res=(res+tree[x])%mod;

		x+=lowbit(x);

	}

	return res;

}

inline void swap(int a,int b)

{

	int temp=x[a]; x[a]=x[b]; x[b]=temp;

	DB t=v[a]; v[a]=v[b]; v[b]=t;

	temp=id[a]; id[a]=id[b]; id[b]=temp;

}

int main()

{

	register int i;

	//freopen("CODE.in","r",stdin); //freopen("CODE.out","w",stdout);

	read(n);

	for (i=1;i<=n;++i)

	{

		read(x[i]); read(v[i]); num[i]=id[i]=i;

		add(v[i]); ans=(ans+get(v[i]+1))%mod;

		if (i^1&&v[i-1]>v[i]) heap.push((data){i-1,i,(double)(x[i]-x[i-1])/(v[i-1]-v[i])});

	}

	write(ans); putchar('\n');

	while (t<10000&&!heap.empty())

	{

		int X=heap.top().x,Y=heap.top().y;

		DB T=heap.top().t; heap.pop();

		if (num[X]+1!=num[Y]) continue;

		write(X); putchar(' '); write(Y); putchar('\n'); ++t;

		int now1=num[X],now2=num[Y]; num[X]=now2; num[Y]=now1;

		swap(now1,now2);

		if (now1>1&&v[now1-1]>v[now1]) if (num[id[now1-1]]+1==num[id[now1]]) heap.push((data){id[now1-1],id[now1],(double)(x[now1]-x[now1-1])/(v[now1-1]-v[now1])});

		if (now2<n&&v[now2]>v[now2+1]) if (num[id[now2]]+1==num[id[now2+1]]) heap.push((data){id[now2],id[now2+1],(double)(x[now2+1]-x[now2])/(v[now2]-v[now2+1])});

	}

	return 0;

}