\(\mathcal{Description}\)
Link.
有 \(n\) 个小球,坐标为 \(x_{1..n}\);还有 \(m\) 个洞,坐标为 \(y_{1..m}\),保证上述坐标两两不同。每次操作可以将所有小球向左或向右平移一个单位,若有小球的坐标与洞重合则掉进洞内。求所有小球都进洞时有多少种不同的状态。答案对 \((10^9+7)\) 取模。
\(n,m\le10^5\)。
\(\mathcal{Solution}\)
ARC 的题嘛……都这副德行。(
不考虑仅有一个方向有洞的球,可见剩余球要不进入左边最近的洞,要不进入右边最近的洞。设一个距离左边洞 \(x\),右边洞 \(y\) 的小球为 \((x,y)\),那么问题被刻画为:
平面上有若干点,每次将 \(x\) 轴向上或 \(y\) 轴向右平移一单位。每个点被染色为最先碰到它的坐标轴代表的颜色。求不同染色方案数。
可证和原问题等价。DP 即可,注意处理转化后重合的坐标。
复杂度 \(\mathcal O(n\log 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( '\n' );
return 0;
}