正題

題目鏈接:https://www.luogu.com.cn/problem/AT4353

---

題目大意

數(shù)軸上有$n$個球$m$個洞，每次可以將所有球左移或者右移，球到洞的位置會掉下去。

求有多少讓球掉進不同洞的方案。

$1\le n,m\le 10^5$

---

解題思路

設(shè)一個球距離左右洞的距離分別為$(x,y)$，那么一個球$(x_1,y_1)$對球$(x_2,y_2)$產(chǎn)生限制當且僅當$x_1\le x_2$且$y_1\ge y_2$。

那么我們相當于找一些兩兩沒有限制的數(shù)字的集合，一種方法是按照$x$升序排序，然后求$y$的上升序列數(shù)量即可。

時間復(fù)雜度$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define lowbit(x) (x&-x) #define mp(x,y) make_pair(x,y) using namespace std; const ll N=1e5+10,P=1e9+7; ll n,m,cnt,bnt,b[N],x[N],y[N],t[N],ans; pair<ll ,ll >a[N]; void Change(ll x,ll val){while(x<=n){(t[x]+=val)%=P;x+=lowbit(x);}return; } ll Ask(ll x){ll ans=0;while(x){(ans+=t[x])%=P;x-=lowbit(x);}return ans; } signed main() {freopen("hole.in","r",stdin);freopen("hole.out","w",stdout);scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",&x[i]);for(ll i=1;i<=m;i++)scanf("%lld",&y[i]);ll z=1;for(ll i=1;i<=n;i++){while(z<=m&&y[z]<x[i])z++;if(z==1||z>m||y[z]==x[i])continue;a[++cnt]=mp(x[i]-y[z-1],x[i]-y[z]);b[++bnt]=y[z]-x[i];}sort(a+1,a+1+cnt);b[++bnt]=0;sort(b+1,b+1+bnt);cnt=unique(a+1,a+1+cnt)-a-1;bnt=unique(b+1,b+1+bnt)-b-1;Change(1,1);ans=1;for(ll i=1;i<=cnt;i++){ll w=lower_bound(b+1,b+1+bnt,-a[i].second)-b;;ll sum=Ask(w-1);Change(w,sum);(ans+=sum)%=P;}printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的AT4353-[ARC101D]Robots and Exits【LIS】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。