oj.uz

답안 #474799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474799 2021-09-19T22:32:08 Z eulerdesoja Garaža (COCI17_garaza) C++17
160 / 160
 950 ms 34752 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define sz(x) int(x.size())

typedef pair<int,int>ii;
typedef vector<int> vi;

const int mxn = 100100;	

int n, q, a[mxn];

int gcd(int a,int b){
	while(b) a %= b, swap(a,b);
	return a;
}


struct Tournament{
	struct Node{
		vector<ii> l,r;
		ll cnt;

		Node() : cnt(0) {}

		Node (int  val){
			l = r = {{0,0}, {1,val}};
			cnt = (val != 1) ? 1 : 0;
		}

		static void expand(vector<ii> &cur, const vector<ii> &add){
			int sz_init = cur.back().first;
			for(auto it : add){
				int sz = sz_init + it.first;
				if(it.second % cur.back().second == 0)cur.back().first = sz;
				else cur.pb({sz, gcd(it.second, cur.back().second)});
			}
		}

		friend Node operator+(const Node &a, const Node &b){
			if(a.l.empty())return b;
			if(b.l.empty())return a;

			Node ret;
			ret.l = a.l;
			ret.r = b.r;
			expand(ret.l,b.l);
			expand(ret.r,a.r);

			ret.cnt = a.cnt + b.cnt;

			int rt = (int)b.l.size() - 1;

			for(int lt = 1; lt < (int)a.r.size(); lt++){
				while(rt > 0 && gcd(a.r[lt].second, b.l[rt].second) == 1)
					--rt;

				ret.cnt += (ll)(a.r[lt].first - a.r[lt-1].first) * b.l[rt].first;
			}

			return ret;

		}
	};

	static const int off = 1 << 17;
	Node seg[2 * off];
	int A, B;

	void update(int pos, int val){
		pos += off;
		seg[pos] = Node(val);
		for(pos /= 2; pos > 0; pos /= 2){
			seg[pos] = seg[2*pos] + seg[2*pos + 1];
		}
	}

	Node query(int no, int i, int j){
		if(i >= B || j <= A)return Node();
		if(i >= A && j <= B)return seg[no];

		int mid = (i + j)/2;

		return query(2*no, i, mid) + query(2*no+1, mid, j);
	}

	ll query(int l,int r){
		A = l, B = r;
		return query(1, 0, off).cnt;
	}

	void build(){
		for(int i = 0;i < n;i++){
			seg[i + off] = Node(a[i]);
		}
		for(int i = off - 1;i > 0; i--){
			seg[i] = seg[2*i] + seg[2*i + 1];
		}
	}
	
} T;

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;

	for(int i = 0;i < n;i++)cin>>a[i];

	T.build();

	while(q--){
		int op, i, j;
		cin>>op>>i>>j;

		if(op == 1) T.update(i-1, j);
		else cout<<T.query(i-1, j)<<"\n";
	}
	return 0;
}


/*
5 1
8 4 3 9 1
2 2 5

5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5

4 3
2 2 2 2
2 1 4
1 2 3
2 1 4

*/

Subtask #1
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 14796 KB Output is correct
2 Correct 27 ms 15180 KB Output is correct
3 Correct 40 ms 15704 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 18784 KB Output is correct
2 Correct 233 ms 20376 KB Output is correct
3 Correct 229 ms 20048 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 385 ms 24304 KB Output is correct
2 Correct 545 ms 24712 KB Output is correct
3 Correct 482 ms 25540 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 819 ms 34180 KB Output is correct
2 Correct 950 ms 34752 KB Output is correct
3 Correct 849 ms 33028 KB Output is correct