ARC101D Robots and Exits
Description
一维直线上有 个球和 个洞互不重叠。
你可以进行若干次操作，每次可以把所有球向左或向右移动 单位长度。
当球移动到洞的位置时，球就会掉进洞中。
你需要求出对于所有操作序列能得到球掉入洞里的方案数。对 取模。
两个方案不同当且仅当存在一个球在两种方案中掉进了不同的洞。
。
Sol
首先第一个洞左边和最后一个洞右边的球会掉进的洞是确定的，可以忽略。
其次所有球都会掉入它左边或右边的第一个洞。
考虑决定一个球掉入的洞的是其历史最左/最右位置达到其左/右的洞的先后，于是处理出每个球到达左/右的洞的距离
。
那么就可以理解为：一条从
出发的折线，每次只能向右或向上，碰到 或
的时候就会导致一个球向左/向右掉到洞里。
或者说：从
的左上/右下（均为不含）经过时就会掉到左/右的洞里。
然后我们发现我们发现在一个点左边的哪里经过都是一样的结果，于是只需要计算恰好经过的方案数。
然后就可以 DP 了： 表示以第
个点作为结尾的折线条数，则：
然后这个东西就是一个比较基础的二维偏序，离散化后开一个 BIT 即可。
时间复杂度 。
Code
借鉴了洛谷第一篇题解的写法（之前从来没想过可以把 DP 值存在 BIT 里最后
qry 一下就完了欸）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using std::vector;
typedef vector<int> vi;
typedef long long ll;
typedef std::array<int,2> pii;
#define all(a) a.begin(),a.end()
#define all1(a) a.begin()+1,a.end()
const int inf=(1<<30);
const int Mod=1e9+7;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
void cmod(int& x){x>Mod?x-=Mod:1;}
struct BIT{
private:
vi T;
int n;
public:
BIT(int _n=0){T.resize((n=_n)+1);}
void add(int x,int k){for(;x<=n;x+=(x&(-x)))cmod(T[x]+=k);}
int qry(int x){int ans=0;for(;x;x-=(x&(-x)))cmod(ans+=T[x]);return ans;}
};
int main(){
int n=read(),m=read();
vi a(n+1),b(m+3),X;
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i)b[i]=read();
b[m+1]=inf,b[m+2]=-inf;
std::sort(all1(b));
vector<pii> A={{0,0}};
for(int i=1;i<=n;++i){
int l=*(std::lower_bound(all1(b),a[i])-1),r=*std::upper_bound(all(b),a[i]);
if(l==-inf||r==inf)continue;
A.push_back({a[i]-l,r-a[i]}),X.push_back(r-a[i]);
}
int N=A.size()-1;
std::sort(all(X));X.erase(std::unique(all(X)),X.end());
for(int i=1;i<=N;++i)A[i][1]=std::lower_bound(all(X),A[i][1])-X.begin()+2;
std::sort(all1(A),[](pii x,pii y){return x[0]==y[0]?x[1]>y[1]:x[0]<y[0];});
BIT t(N+50);
t.add(1,1);
for(int i=1;i<=N;++i)if(A[i]!=A[i-1])t.add(A[i][1],t.qry(A[i][1]-1));
printf("%d\n",t.qry(N+10));
return 0;
}
|