【题解】ARC101F Robots and Exits(DP转格路+树状数组优化DP)

【题解】ARC101F Robots and Exits(DP转格路+树状数组优化DP)

由于要考试了，先贴代码

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define lowbit(x) ((x)&(-(x)))

using namespace std;  typedef long long ll;
inline int qr(){
      register int ret=0,f=0;
      register char c=getchar();
      while(c<48||c>57)f|=c==45,c=getchar();
      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
      return f?-ret:ret;
}


const int mod=1e9+7;
const int maxn=5e5+5;
pair < int,int > fal[maxn];
int seg[maxn<<1|1];
int pos[maxn];
vector < int > ve;
int tmp[maxn];
int n,m,ans=1;
int len;

inline void add(const int&pos,const int&tag){
      for(register int t=pos;t<=len;t+=lowbit(t)) seg[t]=(seg[t]+tag)%mod;
}

inline int que(const int&pos){
      register int ret=0;
      for(register int t=pos;t;t-=lowbit(t)) ret=(ret+seg[t])%mod;
      return ret;
}


inline int divd(const int&data){
      register int l=1,r=m,mid,ret=-1;
      do{
        mid=(l+r)>>1;
        if(pos[mid]<data) l=mid+1,ret=mid;
        else r=mid-1;
      }while(l<=r);
      return ret;
}

int main(){
      //freopen("robot.in","r",stdin);
      //freopen("robot.out","w",stdout);
      n=qr();m=qr();
      for(register int t=1;t<=n;++t) tmp[t]=qr();
      for(register int t=1;t<=m;++t) pos[t]=qr();
      
      //sort(data+1,data+n+1);
      sort(pos+1,pos+m+1);
      
      for(register int t=1;t<=n;++t){
        if(tmp[t]<pos[1]||tmp[t]>pos[m])continue;
        register int k=lower_bound(pos+1,pos+m+1,tmp[t])-pos;
        fal[t].second=pos[k]-tmp[t];
        k=divd(tmp[t]);
        fal[t].first=tmp[t]-pos[k];
        //cout<<fal[t].first<<' '<<fal[t].second<<endl;
        ve.push_back(fal[t].second);//ve.push_back(fal[t].first)
        //cout<<tmp[t]<<' '<<fal[t].first<<' '<<fal[t].second<<endl;
        //for(register int t=1;t<=n;++t) cout<<pos[t]<<' ';
      }
      //cout<<endl;
      
      sort(ve.begin(),ve.end());
      ve.resize(unique(ve.begin(),ve.end())-ve.begin());
      for(auto t:ve) tmp[++tmp[0]]=t;//,cout<<"ttmp="<<t<<endl;
      for(register int t=1;t<=n;++t){
        if(!fal[t].first||!fal[t].second)continue;
        //cout<<"qaq="<<tmp[0]<<endl;
        //fal[t].first=lower_bound(tmp+1,tmp+tmp[0]+1,fal[t].first)-tmp;
        fal[t].second=-(lower_bound(tmp+1,fal[t].second)-tmp);
        //printf("%d %dn",fal[t].first,fal[t].second);
      }
      len=m;
      sort(fal+1,fal+n+1);
      int ed=unique(fal+1,fal+n+1)-fal-1;
      //for(register int t=1;t<=ed;++t) if(fal[t].first&&fal[t].second) printf("%d %dn",fal[t].second);
      
      for(register int t=1;t<=ed;++t){
        if(((!fal[t].second)||(!fal[t].first))) continue;
        register int s=que(-fal[t].second-1)+1;
        //cout<<"qaq="<<fal[t].second<<endl;//<<' '<<s<<endl;
        //cout<<s<<endl;
        ans=(ans+s)%mod;
        add(-fal[t].second,s);
      }
      
      printf("%dn",ans);
      return 0;
}