国家集训队2012
电子对撞机(刘洪轩)解题报告
题目:
见http://cogs.pro/cogs/problem/problem.php?pid=1784
Q国最近科学技术不断进步,经过不懈努力,Q国主席QQ终于在质子对撞机的基础上研发了新一代能量供给装置:电子对撞机。
这个设备呈长条状且对外封闭,设备内部有N个带有一定能量的电子。长条状的外形使得这些电子只能沿条形走向左右运动。设备长度为L,左端位置为0,右端位置为L。内部的电子速率恒定,每一个单位时间在左右方向上移动一个单位长度,而方向可能是向左或向右。当两个电子相遇即运动到同一个点时,它们之间会发生对撞,对撞后它们的速率不变但运动方向反向。设备的两个端点处(即坐标为0和L的位置)存在保护外壳,当电子运动到端点时会和外壳发生碰撞,碰撞后电子也会保持不变的速率但运动方向反向。电子分为高能电子和低能电子,电子之间对撞会产生能量,低能电子和低能电子对撞会产生1个单位的能量,低能电子和高能电子对撞会产生4个单位的能量,高能电子和高能电子对撞会产生25个单位的能量,电子和外壳碰撞不会产生能量。设备内部还有M个能量接收器,每个接收器可以接受从A到B的一个区间内(包括两个端点)的能量,且接收器可以接受的范围没有交集。若电子对撞的位置处于接收器的接受范围内,对撞产生的能量会被接收器接受,若对撞位置不在接收器上,这些能量则会丢失。这项技术的核心在于:对撞时电子的能量不会有损失,所以电子对撞机可以一直不断地运行下去供给能量。
现在QQ已经制造出了第一批电子对撞机,并测得了时刻为0时电子的位置和运动状态,现在QQ想知道从时刻0到时刻T(包括T)总共接收到的能量,于是这个任务交给了神犇你。
分析:
首先,T可能很大,而电子的运动以2L为周期,所以我们计算两个值:时间为[0,2L)内的答案,以及时间为[0,T%2L]内的答案。不过在实际操作中,由于电子位置不同(因此不会在0或2L时刻相遇),我们干脆计算[0,2L]的答案和[0,T%2L]的答案算了。
这种“碰撞”的题有个普遍的方法:将碰撞视作电子互相穿过。如此问题模型转化为:一堆电子在[0,L]上往复运动,在相遇时互相穿过。我们在这里先不考虑电子能量的问题,后面再说。
然后为了处理正反向的问题,将区间复制一份,当电子在左半边(向右)运动时代表它向右运动,当电子在右半边(向右)运动时代表它向左运动。如此一来,电子在[0,L]上的往复运动就转化成了在[0,2L]上的向右运动。可以想象,N个电子在[0,2L]上“编队飞行”,速度均为1,到了右端就循环从左端出现。自然,我们可以把这个0~2L的区间无限复制下去。这样就不需要考虑“循环出现”的问题了。
我们把原问题称作“往复碰撞模型”,将电子互相穿过的模型称作“往复相遇模型”,将这种“编队飞行”的模型称作“跨立模型”,原因下面讲。
那么怎么解决碰撞/穿过的问题呢?我们给“穿过”,即迎面相遇下一个精确的定义:“以相反的速度同时经过某点”。在上图中,一个点距离点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坐标之差有关!
换句话说,只要我们知道了跨立的位置,就知道了ab坐标之差。跨立的位置是什么?接收器的位置!
图4.跨立时,b的位置在接收器范围[Ai,Bi]内(准确说是[2L+Ai,2L+Bi],但不要在意这些细节)
如果某个接收器的坐标是[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的图像。
注意,那些坐标>=4L-Xa的点,跨立时间为负数。实际上,它们第一次跨立的是4L而非2L,跨立时间为f(x)+2L,如下图:
显然这样做不会遗漏,因为我们考虑的区间必定包含了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.x r||l>=N||r<0) return; s[max(l,1)]+=c; if(r+1 0&&4*L-x[ta-1]-x[i]<=2*T1) ta--; for(int j=0;j 4*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