SHARE
TWEET

珂朵莉与GCD

Mysakure Oct 15th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:  MySakure
  3.  *    created: 15.10.2019 20:15:26      
  4. **/
  5. #pragma GCC optimize(2)
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define int long long
  10. const int maxn=1e5+10;
  11. const int mod=1e9+7;
  12. int a[maxn],n,m,ans[maxn],id=1;
  13. struct q{
  14.     int l,r,id;
  15. }Q[maxn];
  16. bool cmp(const q&a,const q&b){
  17.     return a.r==b.r?a.l<b.l:a.r<b.r;
  18. }
  19. struct G{
  20.     int l,r,g;
  21. }tg[maxn<<2];
  22. inline int read(){
  23.     int sgn = 1; int cnt = 0;   //sgn表示正负号 cnt表示读取的数字
  24.     char ch = getchar();
  25.     while (ch < '0' || ch > '9') {      //读取非数字的字符,保留负号,忽略其余无关符号
  26.         if(ch == '-')
  27.             sgn = -sgn;
  28.         ch = getchar();
  29.     }
  30.     while ('0' <= ch && ch <= '9') {
  31.         cnt = cnt*10 + (ch-'0');
  32.         ch = getchar();
  33.     }
  34.     return  sgn*cnt;
  35. }
  36. void buildg(int u,int l,int r){
  37.     tg[u].l=l,tg[u].r=r;
  38.     if(l==r){
  39.         tg[u].g=0;
  40.         return;
  41.     }
  42.     int mid=(l+r)>>1;
  43.     buildg(u<<1,l,mid);
  44.     buildg(u<<1|1,mid+1,r);
  45.     tg[u].g=0;
  46. }
  47. void updateg(int u,int L,int R,int v){
  48.     int l=tg[u].l,r=tg[u].r;
  49.     if(tg[u].g){
  50.         tg[u].g=__gcd(tg[u].g,v);
  51.         return;
  52.     }
  53.     if(l==r){
  54.         if(tg[u].g==0)tg[u].g=v;
  55.         return;
  56.     }
  57.     int mid=(l+r)>>1;
  58.     if(L>mid)updateg(u<<1|1,L,R,v);
  59.     else if(R<=mid)updateg(u<<1,L,R,v);
  60.     else updateg(u<<1,L,mid,v),updateg(u<<1|1,mid+1,R,v);
  61.     if(tg[u<<1].g&&tg[u<<1|1].g&&__gcd(tg[u<<1|1].g,v)==__gcd(tg[u<<1].g,v)){
  62.         tg[u].g=__gcd(tg[u<<1].g,v);
  63.     }
  64. }
  65. int Quareg(int u,int pos){
  66.     int l=tg[u].l,r=tg[u].r;
  67.     if(l==r||tg[u].g){
  68.         return tg[u].g;
  69.     }
  70.     int mid=(l+r)>>1;
  71.     if(pos>mid)return Quareg(u<<1|1,pos);
  72.     else return Quareg(u<<1,pos);
  73. }
  74. struct s{
  75.     int l,r,s;
  76.     int lazy;
  77. }t[maxn<<2];
  78. void build(int u,int l,int r){
  79.     t[u].l=l,t[u].r=r;
  80.     if(l==r){
  81.         t[u].s=0;
  82.         return;
  83.     }
  84.     int mid=(l+r)>>1;
  85.     build(u<<1,l,mid);
  86.     build(u<<1|1,mid+1,r);
  87. }
  88. void pushdown(int u){
  89.     t[u<<1].s+=(t[u<<1].r-t[u<<1].l+1)%mod*t[u].lazy%mod;
  90.     t[u<<1].s%=mod;
  91.     t[u<<1].lazy+=t[u].lazy;
  92.     t[u<<1|1].s+=(t[u<<1|1].r-t[u<<1|1].l+1)%mod*t[u].lazy%mod;
  93.     t[u<<1|1].s%=mod;
  94.     t[u<<1|1].lazy+=t[u].lazy;
  95.     t[u].lazy=0;
  96. }
  97. void update(int u,int L,int R,int pos){
  98.     int l=t[u].l,r=t[u].r;
  99.     int mid=(l+r)>>1;
  100.    // cerr<<"update ing "<<pos<<endl;
  101.     if(l!=r)pushdown(u);
  102.     if(l==L&&R==r){
  103.         //cerr<<"hahah "<<pos<<endl;
  104.         int gl=Quareg(1,l),gr=Quareg(1,r);
  105.         //cerr<<pos<<" update "<<" "<<r<<" "<<gr<<endl;
  106.         //cerr<<pos<<" update "<<" "<<l<<" "<<gl<<endl;
  107.         if(gl==gr||l==r){
  108.             //cerr<<pos<<" update "<<l<<" "<<r<<" "<<gl<<endl;
  109.             t[u].s+=(t[u].r-t[u].l+1)*gl%mod;
  110.             t[u].s%=mod;
  111.             t[u].lazy+=gl;
  112.         }
  113.         else{
  114.             update(u<<1,L,mid,pos);
  115.             update(u<<1|1,mid+1,R,pos);
  116.             t[u].s=t[u<<1].s+t[u<<1|1].s;
  117.             t[u].s%=mod;
  118.         }
  119.         return;
  120.     }
  121.     if(L>mid)update(u<<1|1,L,R,pos);
  122.     else if(R<=mid)update(u<<1,L,R,pos);
  123.     else {
  124.         update(u<<1,L,mid,pos);
  125.         update(u<<1|1,mid+1,R,pos);
  126.     }
  127.     t[u].s=t[u<<1].s+t[u<<1|1].s;
  128.     t[u].s%=mod;
  129. }
  130. int Quaresum(int u,int L,int R){
  131.     int l=t[u].l,r=t[u].r;
  132.     int mid=(l+r)>>1;
  133.     if(l!=r)pushdown(u);
  134.     if(l==L&&r==R){
  135.         return t[u].s;
  136.     }
  137.     if(L>mid)return Quaresum(u<<1|1,L,R);
  138.     else if(R<=mid)return Quaresum(u<<1,L,R);
  139.     else return (Quaresum(u<<1,L,mid)+Quaresum(u<<1|1,mid+1,R))%mod;
  140. }
  141. signed main() {
  142.     ios::sync_with_stdio(false);
  143.     cin.tie(NULL);
  144. #ifdef mysakure
  145.     freopen("in1.txt","r",stdin);
  146. #endif
  147.     n=read(),m=read();
  148.     for(int i=1;i<=n;++i)a[i]=read();
  149.     for(int i=1;i<=m;++i){
  150.         Q[i].l=read();Q[i].r=read();
  151.         if(Q[i].l>Q[i].r){
  152.             swap(Q[i].l,Q[i].r);
  153.         }
  154.         Q[i].id=i;
  155.     }
  156.     sort(Q+1,Q+1+m,cmp);
  157.     buildg(1,1,n);
  158.     build(1,1,n);
  159.     for(int i=1;i<=n;++i){
  160.         updateg(1,1,i,a[i]);
  161.         update(1,1,i,i);
  162.         while(Q[id].r==i&&id<=m){
  163.             ans[Q[id].id]=Quaresum(1,Q[id].l,Q[id].r);
  164.             ++id;
  165.         }
  166.     }
  167.     for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
  168.     return 0;
  169. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top