Submission #48974

#	Time	Username	Problem	Language	Result	Execution time	Memory
48974		ami	Garaža (COCI17_garaza)	C++14	160 / 160	1504 ms	26904 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>>;

template<int N, typename Node>
struct segment_tree {
  Node tr[2*N];

  void set(int i, const Node &x) {
    tr[i+N]=x;
  }
  void build() {
    per(i,1,N) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
  }
  void update(int i, const Node &x) {
    tr[i+=N]=x;
    for (i/=2; i>0; i/=2) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
  }
  Node query(int l, int r) {
    Node L,R;
    l+=N;
    r+=N;
    while (l<=r) {
      if (l%2==1) { L=merge_nodes(L,tr[l]); }
      if (r%2==0) { R=merge_nodes(tr[r],R); }
      l=(l+1)/2;
      r=(r-1)/2;
    }
    return merge_nodes(L,R);
  }
};

struct node {
  i64 count;
  vii p,s;

  node():count(-1) {}
  node(i64 cc, vii pp, vii ss):count(cc),p(pp),s(ss) {}
  node(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;
}

vii merge_comb(vii a, const vii &b) {
  int cur=a.back().first;
  for (const auto &x:b) {
    cur=__gcd(cur,x.first);
    if (cur==a.back().first) {
      a.back().second+=x.second;
    } else {
      a.emplace_back(cur,x.second);
    }
  }
  return a;
}

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

  i64 count=L.count+R.count+merge_count(L.s,R.p);
  auto p=merge_comb(L.p,R.p);
  auto s=merge_comb(R.s,L.s);

  return {count,p,s};
}

int const MAXN=110000;
int n,q;
segment_tree<MAXN,node> st;

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;
    st.set(i,node(x));
  }

  st.build();

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

  return 0;
}

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