Submission #404475

#	Time	Username	Problem	Language	Result	Execution time	Memory
404475		penguinhacker	Garaža (COCI17_garaza)	C++14	160 / 160	969 ms	40472 KiB

garaza

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

struct Node {
	ll cnt=0;
	vector<ar<int, 2>> p, s;
	static void extend(vector<ar<int, 2>>& a, const vector<ar<int, 2>>& b) {
		for (const ar<int, 2>& x : b) {
			int g=__gcd(a.back()[0], x[0]);
			if (g==a.back()[0])
				a.back()[1]+=x[1];
			else
				a.push_back({g, x[1]});
		}
	}
	friend Node operator+(const Node& a, const Node& b) {
		assert(a.p.size()&&b.p.size());
		Node res;
		res.p=a.p, res.s=b.s, res.cnt=a.cnt+b.cnt;
		extend(res.p, b.p), extend(res.s, a.s);
		int j=b.p.size()-1, cur=0;
		for (ar<int, 2> x : b.p)
			cur+=x[1];
		for (ar<int, 2> x : a.s) {
			while(~j&&__gcd(x[0], b.p[j][0])==1)
				cur-=b.p[j--][1];
			res.cnt+=(ll)cur*x[1];
		}
		return res;
	}
};

Node make(int x) {
	Node res;
	res.p=res.s={{x, 1}};
	res.cnt=x>1;
	return res;
}

const int mxN=1e5;
int n, q, a[mxN];
Node st[4*mxN];

void bld(int u=1, int l=0, int r=n-1) {
	if (l==r) {
		st[u]=make(a[l]);
		return;
	}
	int mid=(l+r)/2;
	bld(2*u, l, mid), bld(2*u+1, mid+1, r);
	st[u]=st[2*u]+st[2*u+1];
}

void upd(int i, int x, int u=1, int l=0, int r=n-1) {
	if (l==r) {
		st[u]=make(x);
		return;
	}
	int mid=(l+r)/2;
	i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
	st[u]=st[2*u]+st[2*u+1];
}

Node qry(int ql, int qr, int u=1, int l=0, int r=n-1) {
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2;
	if (qr<=mid)
		return qry(ql, qr, 2*u, l, mid);
	if (ql>mid)
		return qry(ql, qr, 2*u+1, mid+1, r);
	return qry(ql, qr, 2*u, l, mid)+qry(ql, qr, 2*u+1, mid+1, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	bld();
	while(q--) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t==1)
			upd(x-1, y);
		else
			cout << qry(x-1, y-1).cnt << "\n";
	}
	return 0;
}

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