CodeForces 689E Mike and Geometry Problem-白红宇

CodeForces 689E Mike and Geometry Problem

阅读量：6949 次

发布时间：2019-06-27

本文共 1628 字，大约阅读时间需要 5 分钟。

离散化，树状数组，组合数学。

这题的大致思路和$HDU$ $5700$一样。都是求区间交的问题。可以用树状数组维护一下。

这题的话只要计算每一个$i$被统计了几次，假设第$i$点被统计了$ans[i]$次，累加和就是答案。

$ans[i]$就是看$i$点之后有多少个区间右端点，假设有$m$个，那么$ans[i]$就等于$m$个里面选$k$个的方案数。

因为数据中$L$,$R$范围较大，所以需要先离散化，计算离散化之后的情况，然后再统计离散化之前的情况。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template 
               
                inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}}LL mod=1e9+7;const int maxn=1200010;int n,k;LL f[maxn],a[maxn];struct X { int L,R; }s[maxn];int c[maxn],b[maxn],sz;LL ans[maxn];int lowbit(int x){ return x&(-x);}int sum(int x){ int res=0; while(x>0) res=res+c[x],x=x-lowbit(x); return res;}void update(int x,int v){ while(x<=1200000) c[x]=c[x]+v,x=x+lowbit(x);}LL extend_gcd(LL a,LL b,LL &x,LL &y){ if(a==0&&b==0) return -1; if(b==0){x=1;y=0;return a;} LL d=extend_gcd(b,a%b,y,x); y-=a/b*x; return d;}LL mod_reverse(LL a,LL n){ LL x,y; LL d=extend_gcd(a,n,x,y); if(d==1) return (x%n+n)%n; else return -1;}int get(int x){ int L=0,R=sz-1,pos=0; while(L<=R) { int mid=(L+R)/2; if(b[mid]
                
                 b[i]) { pos=j; break; } } if(pos==-1) { Ans=(Ans+ans[i+1])%mod; break; } Ans=(Ans+(b[pos]-b[i])*ans[i+1]%mod)%mod; i=pos; } printf("%lld\n",Ans); return 0;}