(mathcal{Description})
Link.
有 (n) 个小球，坐标为 (x_{1..n})；还有 (m) 个洞，坐标为 (y_{1..m})，保证上述坐标两两不同。每次操作可以将所有小球向左或向右平移一个单位，若有小球的坐标与洞重合则掉进洞内。求所有小球都进洞时有多少种不同的状态。答案对 ((10^9+7)) 取模。
(n,mle10^5)。
(mathcal{Solution})
ARC 的题嘛……都这副德行。（
不考虑仅有一个方向有洞的球，可见剩余球要不进入左边最近的洞，要不进入右边最近的洞。设一个距离左边洞 (x)，右边洞 (y) 的小球为 ((x,y))，那么问题被刻画为：
平面上有若干点，每次将 (x) 轴向上或 (y) 轴向右平移一单位。每个点被染色为最先碰到它的坐标轴代表的颜色。求不同染色方案数。
可证和原问题等价。DP 即可，注意处理转化后重合的坐标。
复杂度 (mathcal O(nlog n))。
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <algorithm>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline int rint() {
int x = 0, f = 1, s = getchar();
for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
return x * f;
}
template<typename Tp>
inline void wint( Tp x ) {
if ( x < 0 ) putchar( '-' ), x = -x;
if ( 9 < x ) wint( x / 10 );
putchar( x % 10 ^ '0' );
}
const int MAXN = 1e5, MOD = 1e9 + 7;
int n, m, mx, x[MAXN + 5], y[MAXN + 5], dc[MAXN + 5];
inline int mul( const long long a, const int b ) { return a * b % MOD; }
inline int sub( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }
inline void subeq( int& a, const int b ) { ( a -= b ) < 0 && ( a += MOD ); }
inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline void addeq( int& a, const int b ) { ( a += b ) >= MOD && ( a -= MOD ); }
struct Point {
int x, y;
inline bool operator < ( const Point& p ) const {
return x != p.x ? x < p.x : y > p.y;
}
} pt[MAXN + 5];
struct BinaryIndexTree {
int val[MAXN + 5];
inline void upd( int x, const int v ) {
for ( ; x <= mx; x += x & -x ) addeq( val[x], v );
}
inline int sum( int x ) {
int ret = 0;
for ( ; x; x -= x & -x ) addeq( ret, val[x] );
return ret;
}
} bit;
int main() {
// freopen( "hole.in", "r", stdin );
// freopen( "hole.out", "w", stdout );
n = rint(), m = rint();
rep ( i, 1, n ) x[i] = rint();
rep ( i, 1, m ) y[i] = rint();
int cnt = 0;
rep ( i, 1, n ) {
int p = std::lower_bound( y + 1, y + m + 1, x[i] ) - y;
if ( p == 1 || p > m ) continue;
pt[++cnt] = { x[i] - y[p - 1], y[p] - x[i] }, dc[cnt] = pt[cnt].y;
}
std::sort( pt + 1, pt + cnt + 1 );
std::sort( dc + 1, dc + cnt + 1 );
mx = std::unique( dc + 1, dc + cnt + 1 ) - dc;
rep ( i, 1, cnt ) {
pt[i].y = std::lower_bound( dc + 1, dc + mx, pt[i].y ) - dc + 1;
}
bit.upd( 1, 1 );
rep ( i, 1, cnt ) {
if ( pt[i].x == pt[i - 1].x && pt[i].y == pt[i - 1].y ) continue;
int v = bit.sum( pt[i].y - 1 );
bit.upd( pt[i].y, v );
}
wint( bit.sum( mx ) ), putchar( '
' );
return 0;
}