제출 #170311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170311		ryansee	Garaža (COCI17_garaza)	C++14	160 / 160	1521 ms	34168 KiB

garaza

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T,typename B> inline T gcd(T a,B b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<int,int>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (300006)
int n, q;
struct stuff { vector<pi>pre,suf; ll v=0; }; 
struct node {
	stuff v;
	node *l,*r;
	node(int s,int e) { int m=(s+e)>>1;
// 		s=_S,e=_E,m=(s+e)>>1;
		v.pre.clear(),v.suf.clear();
		if(s^e) {
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
// 	typedef pair<deque<pi>,deque<pi>> dqpi;
	void update(int s,int e,int x,int nval) {
		if(s==e) {
			v.pre.clear(), v.suf.clear(), v.pre.eb(nval,s), v.suf.eb(nval,s), v.v=nval!=1;
			return;
		}
		int m=(s+e)>>1;
		if(x>m) r->update(m+1,e,x,nval);
		else l->update(s,m,x,nval);
		if(l->v.pre.size()&&r->v.pre.size()) v = merge(l->v,r->v,s,e,m);
// 		v.s=s,v.e=e,v.m=m;
	}
	stuff merge(stuff l,stuff r,int lds,int rde,int m,bool dg=0) {
// 		if(dg) cerr<<"start: "<<l.s<<' '<<l.e<<' '<<r.e<<'\n';
		stuff v;
// 		if(l.pre.empty() || r.pre.empty()) return v;
		if(dg) cerr<<l.v<<' '<<r.v<<'\n';
		v.v=l.v+r.v;
		l.suf.insert(l.suf.begin(), pi(1, lds-1));
		int ls=0;
		FOR(i,1,siz(l.suf)-1) {
			ll stop = rde+1;
			ll now = l.suf[i].f;
			if(now != 1) {
				// for(auto j:r.pre) {
					// if(gcd(j.f,now)==1) { stop=j.s; break; }
					// now=gcd(now,j.f);
				// }
				FOR(j,ls,r.pre.size()-1) {
					now=gcd(r.pre[j].f,now);
					if(now==1) { stop=r.pre[j].s; break; }
					ls=j+1;
				}
			} else {
				stop = m+1;
			}
			v.v += (l.suf[i].s-l.suf[i-1].s) * (stop-(m+1));
		}
		if(dg) cerr<<v.v-l.v-r.v<<'\n'<<'\n';
		l.suf.erase(l.suf.begin());
		v.pre=l.pre;
		ll now=v.pre.back().f;
		if(now != 1) {
			for(auto i:r.pre) {
				// if(gcd(i.f,now)==1) { v.pre.eb(1, i.s); break; }
				// ll on=now; 
				// now=gcd(i.f,now);
				// if(on^now) v.pre.eb(now, i.s);
				if(i.f%now) now=gcd(now,i.f), v.pre.eb(now,i.s); 
			}
		}
		v.suf=r.suf;
		now=v.suf[0].f;
		if(now != 1) {
			reverse(all(l.suf));
			for(auto i:l.suf) {
				// if(gcd(i.f,now)==1) { v.suf.emplace_front(1, i.s); break; }
				// ll on = now;
				// now=gcd(i.f,now);
				// if(on^now) v.suf.emplace_front(now,i.s);
				if(i.f%now) now=gcd(now,i.f), v.suf.insert(v.suf.begin(), {now,i.s});
			}
			reverse(all(l.suf));
		}
		if(dg) {
			for(auto i:v.pre) cerr<<i.f<<' '<<i.s<<'\n';
			cerr<<"\n";
			for(auto i:v.suf) cerr<<i.f<<' '<<i.s<<'\n';
			cerr<<"\n";
			for(auto i:l.suf) cerr<<i.f<<' '<<i.s<<'\n';
			cerr<<'\n';
		}
		return v;
	}
	stuff rmq(int s,int e,int x,int y) {
		if(s==x&&e==y) {
			return v;
		}
		int m=(s+e)>>1;
		if(x>m) return r->rmq(m+1,e,x,y);
		else if(y<=m) return l->rmq(s,m,x,y);
		else return merge(l->rmq(s,m,x,m),r->rmq(m+1,e,m+1,y),x,y,m);
	}
} *seg;
int main()
{
	FAST
	cin>>n>>q;
	seg=new node(1,n);
	FOR(i,1,n) { ll a; cin>>a; seg->update(1,n,i,a); }
	// stuff tmp = seg->rmq(1,n);
	// cerr<<"\n\n";
	// cerr<<tmp.v<<'\n';
	// for(auto i:tmp.pre) cerr<<i.f<<' '<<i.s<<'\n';
	// cerr<<'\n';
	// for(auto i:tmp.suf) cerr<<i.f<<' '<<i.s<<'\n';
	// return 0;
	FOR(ii,1,q) {
		ll op; cin>>op;
		if(op==1) {
			ll x, v; cin>>x>>v;
			seg->update(1,n,x,v);
		} else {
			ll l, r; cin>>l>>r;
			cout<<seg->rmq(1,n,l,r).v<<'\n';
		}
	}
	return 0;
}
/*
4 1
2 2 2 2
2 1 4
*/

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