pastebin

Paste #GGk -- näytä pelkkänä tekstinä -- uusi tämän pohjalta

Värjäys: Tyyli: ensimmäinen rivinumero: Tabin korvaus: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

const int N=1<<18;
ll stm[2*N];
ll sts[2*N];
ll sisu[2*N];

const ll inf=1e18;

pair<ll, ll> qq(int i, int stl, int str, int l, int r, ll add){
	if (l>str||r<stl) return {0, inf};
	if (l<=stl&&str<=r){
		sisu[i]+=add;
		sts[i]+=add*(ll)(str-stl+1);
		stm[i]+=add;
		return {sts[i], stm[i]};
	}
	else{
		int m=(stl+str)/2;
		int lk=min(str, r)-max(stl, l)+1;
		sts[i]+=(ll)lk*add;
		pair<ll, ll> q1=qq(i*2, stl, m, l, r, add);
		pair<ll, ll> q2=qq(i*2+1, m+1, str, l, r, add);
		stm[i]=min(stm[i*2], stm[i*2+1])+sisu[i];
		return {q1.F+q2.F+(ll)lk*sisu[i], min(q1.S, q2.S)+sisu[i]};
	}
}

int main(){
	freopen("haybales.in", "r", stdin);
	freopen("haybales.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	for (int i=0;i<n;i++){
		cin>>sts[i+N];
		stm[i+N]=sts[i+N];
	}
	for (int i=N-1;i;i--){
		sts[i]=sts[i*2]+sts[i*2+1];
		stm[i]=min(stm[i*2], stm[i*2+1]);
	}
	for (int i=0;i<q;i++){
		char t;
		int l,r;
		cin>>t>>l>>r;
		l--;
		r--;
		if (t=='M'){
			pair<ll, ll> a=qq(1, 0, N-1, l, r, 0);
			cout<<a.S<<'\n';
		}
		if (t=='P'){
			ll c;
			cin>>c;
			qq(1, 0, N-1, l, r, c);
		}
		if (t=='S'){
			pair<ll, ll> a=qq(1, 0, N-1, l, r, 0);
			cout<<a.F<<'\n';
		}
	}
}