제출 #48969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48969		ami	Garaža (COCI17_garaza)	C++14	0 / 160	3 ms	852 KiB

garaza

#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using i64 = long long;
using vii = vector<pair<int,int>>;

struct node {
  i64 count=-1;
  vii p,s;

  void set(int x) {
    count=(x==1 ? 0 : 1);
    p=s={make_pair(x,1)};
  }
};

i64 merge_count(const vii &S, const vii &P) {
  i64 res=0,r=0,psum=0;
  per(l,0,sz(S)) {
    while (r<sz(P) && __gcd(S[l].first,P[r].first)>1) {
      psum+=P[r].second;
      r+=1;
    }
    res+=S[l].second*psum;
  }
  return res;
}

// s3 s2 s1 s0 p0 p1 p2 p3

node merge_nodes(const node &L, const node &R) {
  if (L.count==-1) return R;
  if (R.count==-1) return L;

  node res;
  res.count=L.count+R.count+merge_count(L.s,R.p);

  res.p=L.p;
  auto &p=res.p;
  int cur=p.back().first;
  for (const auto &x:R.p) {
    cur=__gcd(cur,x.first);
    if (cur==p.back().first) {
      p.back().second+=x.second;
    } else {
      p.emplace_back(cur,x.second);
    }
  }

  // a.s3 a.s2 a.s1 a.s0 b.s3 b.s2 b.s1 b.s0
  // c.s7 c.s6 c.s5 c.s4 c.s3 c.s2 c.s1 c.s0

  res.s=R.s;
  auto &s=res.s;
  cur=s.back().first;
  for (const auto &x:L.s) {
    cur=__gcd(cur,x.first);
    if (cur==s.back().first) {
      s.back().second+=x.second;
    } else {
      s.emplace_back(cur,x.second);
    }
  }

  return res;
}

// int const N=1<<17;
int const N=8;
int n,q;
node tr[2*N];

void update(int i, int x) {
  tr[i+=N].set(x);
  for (i/=2; i>0; i/=2) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
}

i64 get(int l, int r) {
  // cerr<<l<<" "<<r<<endl;
  node L,R;
  L.count=R.count=-1;
  l+=N;
  r+=N;
  while (l<=r) {
    if (l%2==1) {
      L=merge_nodes(L,tr[l]);
      // cerr<<"merge: L and ("<<l<<","<<tr[l].count<<")"<<endl;
    }
    if (r%2==0) {
      R=merge_nodes(tr[r],R);
      // cerr<<"merge: ("<<r<<","<<tr[r].count<<") and R"<<endl;
    }
    l=(l+1)/2;
    r=(r-1)/2;
  }
  // cerr<<L.count<<endl;
  // cerr<<R.count<<endl;
  return merge_nodes(L,R).count;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);

  cin>>n>>q;
  rep(i,0,n) {
    int x;
    cin>>x;
    tr[i+N].set(x);
    // cerr<<x<<" ";
  }
  // cerr<<endl;

  per(i,1,N) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }

  // cerr<<tr[1].count<<endl;

  rep(iq,0,q) {
    int t,l,r;
    cin>>t>>l>>r;
    if (t==1) { update(l-1,r); } else { cout<<get(l-1,r-1)<<'\n'; }
  }

  return 0;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 40
• Subtask 4: 0 / 40