Submission #87874

#	Time	Username	Problem	Language	Result	Execution time	Memory
87874		jasony123123	Garaža (COCI17_garaza)	C++11	160 / 160	2015 ms	36308 KiB

garaza

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

int __gcd(int x, int y) {
	if (x < y)
		return __gcd(y, x);
	if (y == 0)
		return x;
	else
		return __gcd(y, x%y);
}

struct Node {
	ll cnt;
	v<pii> pref, suff; // gcd val, number

	Node() {
		cnt = -1;
	}
	Node(int a) {
		if (a == 1) cnt = 1;
		else cnt = 0;
		pref.push_back({ a,1 });
		suff.push_back({ a,1 });
	}
	Node(Node &a, Node &b) {
		assert(!a.pref.empty() && !b.pref.empty());
		// make pref
		for (pii x : a.pref)
			pref.push_back(x);
		for (pii x : b.pref) {
			pii add = { __gcd(a.pref.back().first, x.first), x.second };
			if (pref.back().first == add.first)
				pref.back().second += add.second;
			else
				pref.push_back(add);
		}

		// make suff
		RFORE(i, b.suff.size() - 1, 0)
			suff.push_back(b.suff[i]);
		RFORE(i, a.suff.size() - 1, 0) {
			pii add = { __gcd(a.suff[i].first, b.suff[0].first), a.suff[i].second };
			if (suff.back().first == add.first)
				suff.back().second += add.second;
			else
				suff.push_back(add);
		}
		reverse(suff.begin(), suff.end());



		cnt = a.cnt + b.cnt;
		v<ll> bprefsums(b.pref.size());
		bprefsums[b.pref.size() - 1] = b.pref.back().second;
		RFORE(i, b.pref.size() - 2, 0) bprefsums[i] = bprefsums[i + 1] + b.pref[i].second;

		for (int i = 0, j = 0; i < a.suff.size(); i++) {
			while (j + 1 < b.pref.size() && __gcd(a.suff[i].first, b.pref[j].first) > 1)
				j++;
			if (__gcd(a.suff[i].first, b.pref[j].first) > 1)
				break;
			cnt += (ll)a.suff[i].second*bprefsums[j]; // sum b.pref[j].second->end
		}
	}
	bool isId() {
		if (cnt == -1) return 1;
		return 0;
	}
};

template<int SZ, class T> struct SegmentTree {
	T data[2 * SZ];
	int _N;

	T id = Node(); // identity function (a,id) = a; (id,a) = a;
	T combine(T a, T b) {
		if (a.isId()) return b;
		if (b.isId()) return a;
		return Node(a, b);
	}

	SegmentTree() {}
	void build(int N) {
		_N = N;
		//	! make sure you do this first
		//	for (int i = 0; i < n; ++i) scanf("%d", t + n + i);
		for (int i = _N - 1; i > 0; --i)
			data[i] = combine(data[i << 1], data[(i << 1) | 1]);
	}
	void update(int p, T val) {
		data[p += _N] = val;
		for (p >>= 1; p > 0; p >>= 1)
			data[p] = combine(data[p << 1], data[(p << 1) | 1]);
	}

	T query(int l, int r) { // sum [l,r]
		r++;
		T resl = id, resr = id;
		for (l += _N, r += _N; l < r; l >>= 1, r >>= 1) {
			if (l & 1) resl = combine(resl, data[l++]);
			if (r & 1) resr = combine(data[--r], resr);
		}
		return combine(resl, resr);
	}
};

SegmentTree<100010, Node> stree;

int main() {
	io();
	int N, Q;
	cin >> N >> Q;
	FOR(i, 0, N) {
		int a;
		cin >> a;
		stree.data[i + N] = Node(a);
	}
	stree.build(N);
	FOR(i, 0, Q) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 1)
			stree.update(a - 1, Node(b));
		else {
			ll len = b - a + 1;
			len = len*(len - 1) / 2 + len;
			cout << len - stree.query(a - 1, b - 1).cnt << "\n";
		}
	}
	return 0;
}


void io() {
#ifdef LOCAL_PROJECT
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// add i/o method of specific testing system
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message (stderr)

garaza.cpp: In constructor 'Node::Node(Node&, Node&)':
garaza.cpp:78:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0, j = 0; i < a.suff.size(); i++) {
                          ~~^~~~~~~~~~~~~~~
garaza.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (j + 1 < b.pref.size() && __gcd(a.suff[i].first, b.pref[j].first) > 1)
           ~~~~~~^~~~~~~~~~~~~~~

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