[国家集训队2012]电子对撞机 解题…

那么怎么解决碰撞/穿过的问题呢？我们给“穿过”，即迎面相遇下一个精确的定义：“以相反的速度同时经过某点”。在上图中，一个点距离点L的距离就是往复相遇模型中，距离右端点的距离，因而，如果在图1中，两个电子a,b（a在b的左边）关于L对称，那么此时，ab互相穿过，且a向右，b向左。

我们把这种情况称作ab“跨立”了L。当然可以发现，ab跨立0,L,2L,3L……都对应往复相遇模型中的一次相遇事件。并且，无论哪两个区间内的a,b跨立了某个k*L，都对应一次“互相穿过”（取一下模，发现这是显然的）。

那这个事件和“碰撞”怎么对应呢？若ab跨立了2L，那么我们希望计算出：它在原问题中对应于谁和谁碰撞。可以发现，在往复碰撞模型中，如果将电子按照坐标排序，只有坐标相邻的（0和1,1和2……）电子会碰撞。

我们把电子i-1和电子i碰撞的事件编号为i。那么我们只需要关注一个量：在碰撞的时候，碰撞点左边有多少个电子。也就是，在往复相遇模型中，相遇点左边有多少个电子（因为往复碰撞模型和往复相遇模型中的电子位置是一一对应的）。

到底有多少个呢？在图2中，坐标Xa~2L的那些点肯定在相遇点左边，坐标2L~Xb的那些点也肯定在相遇点左边。也就是说，跨立模型中处于a和b之间的那些点，在往复相遇模型中，都在相遇点左边！

因此，相遇点左边有b-a-1个电子，也就是说该碰撞事件在往复碰撞模型中的编号为b-a。

至此就有了一个O(N^2*M)的算法，即枚举a,b，看它们的碰撞事件对应于往复碰撞模型中的哪一次碰撞，然后枚举接收器，看这次碰撞的能量是否被吸收。

但是这样会TLE，还需要继续优化。

我们观察到一个事实：在跨立模型中，两个电子的坐标之差始终不会改变。也就是说，其中点随着这两个电子同步向右运动。当中点到达某个k*L时，就形成跨立——也就是说，跨立时，a,b的位置只和ab坐标之差有关！

如果某个接收器的坐标是[Ai,Bi]，那么如果两个电子跨立2L，则b距离2L的距离一定在[Ai,Bi]范围内。这意味着，ab的距离在[2Ai,2Bi]范围内，也就是a,b坐标之差在[2Ai,2Bi]范围内。

所以，对于给定的接收器i和给定的a，能让ab跨立于接受范围内的b是连续的一段。自然，在往复碰撞模型中对应的碰撞事件也是相应的一段。这就启发我们，用差分进行快速的段修改。差分数组的意思是，如果我们现在要把l~r这些碰撞事件的出现次数都+1，设差分数组为d，则只需简单地让d[l]++,d[r+1]–。

一个初步的思路是：枚举a，然后枚举接收器，计算对于哪一段b，ab将在合法的位置和时间相遇，并且在往复相遇模型中，a向左b向右（这意味着ab跨立2L或4L），那么我们需要考虑b的范围是[a,a+1+N-1].

怎么求具体是哪一段呢？随着a的增加，这个[Xa+2Ai,Xa+2Bi]的“接收窗口”单调向右移动。所以，我们就可以在线性扫描时确定，对于每个a，其接收窗口到底是哪到哪。

既然接收器的合法范围是连续一段，那么时间的合法范围（跨立时间<=T%2L）是否也是连续一段呢？可以发现同样是！

我们来计算一个值：ab跨立K的时间。在跨立时，a距离K的距离是(Xb-Xa)/2，a的位置为K-(Xb-Xa)/2，因此a走到这个位置需要的时间是K-(Xb-Xa)/2-a=K-(Xa+Xb)/2.

因此，对于给定的a，ab跨立2L的时间随着b坐标的增大而递减。下图展示了Xa=0.5的图像。

显然这样做不会遗漏，因为我们考虑的区间必定包含了a~a+N-1的这一整段（或者在图像上，从Xa开始长度为2L的一整段）。那么会重复吗？也不会重复，因为我们要计算时间和跨立位置都合法的一段，而跨立位置的“合法窗口”必定不会超过这一段.

在图6中，能够清楚地看到，这基本是连续的一段。

为什么说“基本”呢？我们画出y=T1这条直线去截这个跨立时间的图像。截出来的那一段就是0<=跨立时间<=T1的一段。

如果T1比较小，图像可能是这样的：

如果T1比较大，有可能是这样的：

这时，合法区间变成了两段——[Xa,4L-Xa]（4L-Xa的跨立时间恰好为零，因为a和它已然跨立2L），以及从某个点到4L的一段。

那么在什么情况下合法区间可能是两段呢？有两种想法：第一种想法，是a和a（或曰，比a小一个极小量的点）跨立2L的时间小于T1（即，2L-Xa

标程用的是上面的第一种想法。而实际上这两种都是对的。还有一个技术性问题：观察标程可以发现，它并没有处理右边合法区间不存在的情况（此时，它对应的电子编号区间为默认的[2N-1,2N-1]）。怎么办呢？我们并不必担心这个问题，因为接收器的合法区间必定严格小于2N-1。

算法到这里基本就讲完了。最后注意一点：i=0时，所有的区间都需要暴力扫描。故i=0和0

对于枚举的电子i，算法的主要流程是：先扫描求出跨立时间的合法区间[ta,tb]（ta>tb代表有两个区间），再枚举接收器j，并扫描计算跨立位置的合法区间[ra[j],rb[j]]，然后两个区间求交集，相应修改[0,T1]答案的差分数组，并用[ra[j],rb[j]]修改[0,2L]答案的差分数组。

代码：

#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int SIZEN=2000010;
class ELECTRON{
public:
	int x,p,e;
}ele[SIZEN];
bool operator < (ELECTRON a,ELECTRON b){
	return a.xr||l>=N||r<0) return;
	s[max(l,1)]+=c;
	if(r+10&&4*L-x[ta-1]-x[i]<=2*T1) ta--;
		for(int j=0;j4*L-x[i]) T1=T-2*L,ta=2*N-1;
		while(ta>0&&4*L-x[ta-1]-x[i]<=2*T1) ta--;
		for(int j=0;j