POJ2274

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

题意是在一条直线上有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;
}