제출 #527853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527853		AriaH	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5052 ms	8204 KiB

sterilizing

/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, q, k, A[N];

pii seg[N << 2];

ll sum[N << 2];

void build(int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		seg[v] = {A[tl], tl};
		sum[v] = A[tl];
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
	sum[v] = sum[v << 1] + sum[v << 1 | 1];
}

void upd(int p, int x, int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		seg[v] = Mp(x, tl);
		sum[v] = x;
		return;
	}
	int mid = (tl + tr) >> 1;
	if(p <= mid) upd(p, x, v << 1, tl, mid);
	else upd(p, x, v << 1 | 1, mid + 1, tr);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
	sum[v] = sum[v << 1] + sum[v << 1 | 1];
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if(l > tr || r < tl || l > r) return 0;
	if(l <= tl && tr <= r) return sum[v];
	int mid = (tl + tr) >> 1;
	return get(l, r, v << 1, tl, mid) + get(l, r, v << 1 | 1, mid + 1, tr);
}

pii ask(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if(l > tr || r < tl || l > r) return {-1, -1};
	if(l <= tl && tr <= r)
	{
		return seg[v];
	}
	int mid = (tl + tr) >> 1;
	return max(ask(l, r, v << 1, tl, mid), ask(l, r, v << 1 | 1, mid + 1, tr)); 
}

int main()
{
	fast_io;
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i ++)
	{
		cin >> A[i];
	}
	build();
	for(int j = 1; j <= q; j ++)
	{
		int tp, fir, sec;
		cin >> tp >> fir >> sec;
		if(tp == 1)
		{
			A[fir] = sec;
			upd(fir, sec);
		}
		if(tp == 2)
		{
			pii cu;
			vector < int > pos;
			while((cu = ask(fir, sec)).F > 0)
			{
				A[cu.S] /= k;
				upd(cu.S, 0);
				pos.push_back(cu.S);
			}
			for(auto x : pos)
			{
				upd(x, A[x]);
			}
		}
		if(tp == 3)
		{
			cout << get(fir, sec) << endl;
		}
		/*printf("j = %d\n", j);
		for(int i = 1; i <= n; i ++)
		{
			printf("%d ", A[i]);
		}
		printf("\n");
		*/
	}
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75