[atARC101F]Robots and Exits

每一个点一定匹配其左边/右边的第一个出口（在最左/右边的出口左/右边的点直接删除即可），否则记到左右出口的距离分别为$x_{i}$和$y_{i}$

令$p_{i}$表示$i$匹配的出口（左0右1），结论：存在不合法当且仅当$p_{i}=0$、$p_{j}=1$、$x_{i}\ge x_{j}$且$y_{i}\le y_{j}$

充分性显然，考虑必要性，我们每一次所能做的就是删除最小的$x_{i}$（相同都要删除）且这些$x_{i}$的$p_{i}=0$或删除最小的$y_{i}$且这些$y_{i}$的$p_{i}=1$

如果能够不断删除，每一次至少删除1个，因此一定可以删除完（即合法），那么考虑当不能删除，令$j$为最小的$x_{i}$中某一个$p_{i}=1$（$i$类似）

此时有$p_{i}=0$、$p_{j}=1$、$x_{i}\ge x_{j}$（$j$是最小值）且$y_{i}\le y_{j}$，因此若不存在这种情况，一定可以不断删除，即必要性成立

先将所有位置按照$x_{i}$从小到大排序（相同$y_{i}$从大到小），即对于所有为$p_{i}=1$的位置，需要保证其之后（$x_{i}$比其大）所有$y_{i}$小于等于它的位置都要选

（这里有一个小问题，就是当$x_{i}$和$y_{i}$都相同，那么对于排在后面，其前面与其相同的也会影响他，由于这两个点状态必然相同，不妨删去1个）

答案可以看作任选若干个位置$p_{i}=1$使得合法的方案数，实际上强制选择等价于强制不选（因为这些位置选择再对其之后的影响一定包含在$i$中），所以也可以理解为统计最长上升子序列的个数

考虑dp，令$f[i]$表示以$i$为结尾的最长上升子序列个数，线段树维护转移即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 #define mod 1000000007

 5 #define mid (l+r>>1)

 6 pair<int,int>c[N];

 7 int V,r,n,m,t,ans,a[N],b[N],f[N*30],ls[N*30],rs[N*30];

 8 void update(int &k,int l,int r,int x,int y){

 9     if (!k)k=++V;

10     f[k]=(f[k]+y)%mod;

11     if (l==r)return;

12     if (x<=mid)update(ls[k],l,mid,x,y);

13     else update(rs[k],mid+1,r,x,y);

14 }

15 int query(int k,int l,int r,int x,int y){

16     if ((!k)||(l>y)||(x>r))return 0;

17     if ((x<=l)&&(r<=y))return f[k];

18     return (query(ls[k],l,mid,x,y)+query(rs[k],mid+1,r,x,y))%mod;

19 }

20 int main(){

21     scanf("%d%d",&n,&m);

22     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

23     for(int i=1;i<=m;i++)scanf("%d",&b[i]);

24     for(int i=1;i<=n;i++){

25         if ((a[i]<b[1])||(a[i]>b[m]))continue;

26         int x=lower_bound(b+1,b+m+1,a[i])-b;

27         c[++t]=make_pair(a[i]-b[x-1],-(b[x]-a[i]));

28     }

29     sort(c+1,c+t+1);

30     ans=1;

31     update(r,0,1e9,0,1);

32     for(int i=1;i<=t;i++){

33         if ((i)&&(c[i-1]==c[i]))continue;

34         int s=query(r,0,1e9,0,-c[i].second-1);

35         ans=(ans+s)%mod;

36         update(r,0,1e9,-c[i].second,s);

37     }

38     printf("%d",ans);

39 }

巴特西

[atARC101F]Robots and Exits

最新文章

热门文章