题意:

　　一个长为l的环,环上有n个点,每个点以一定的速度顺时针或逆时针运动,两个点相遇即某一时刻内两个点位置相同.

　　求有多少点对相遇----相同点对出现多次仅统计一次.

 

SOL:

　　考试的时候想到用线段树或者树状数组统计的...但是被数据范围吓住了然后就没打...毕竟是一个差不多n^2logn的东西...然而n有10000....

　　事实证明数据结构题你要往小里想...胆大心细...

　　

　　怎么统计呢(这才是正事!!!)...  显然我们能把环上的运动放到直线上. 考虑两个点a,b的追及问题,若a在b身后(我们假设两个点运动方向相同),那么如果两个点在某一时刻相遇,那么a的速度一定大于b,则当他们运动ts后a的一定在b身前.

　　这是一个非常有用的性质,当我们将每个点的初始位置排序后,所有能与这个点相遇的最终位置坐标一定小于它,那么我们离散化后用树状数组统计即可

　　对于方向不同的点,减个L相同考虑就完啦...

struct Node{	int l,r,pos;}a[maxn];int e[maxn],c[2][maxn],ans=0,n;int cmp(Node x,Node y){return x.l
     
      >1;		if (e[mid]<=x) L=mid+1; else R=mid-1;	}	return L-1;}int main(){	//freopen("a.in","r",stdin);	int l,t; 	read(l); read(t); read(n);	FORP(i,1,n){		read(a[i].l); a[i].l%=l;		int x; read(x); a[i].r=a[i].l+x*t;		e[i]=a[i].r;	}	sort(e+1,e+1+n); sort(a+1,a+1+n,cmp);	e[0]=-INF;	FORP(i,1,n) {		a[i].pos=lower_bound(e+1,e+1+n,a[i].r)-e;		add(0,a[i].pos,1);	}	int i;	FOR(i,1,n){		int j;		for (j=i;j