Algorithm
Problem link- https://www.spoj.com/problems/COURAGE/
COURAGE - Living with Courage
Courage (the cowardly dog) lives with his master Muriel and her husband Eustace in the city of Nowhere. Eustace is a farmer but not a very good one. One fine day Courage was taking a stroll in Eustace's cropless field when he found seeds of a magical tree. He seow them in the field and the next morning n magical apple trees grew on the previously cropless field. The number of apples on the ith tree is apples[i] (0<=i< n). The number of apples on a tree may change as sometimes courage eats some apples from a tree and sometimes apples grow instantly on the trees (because they are MAGICAL!!).
Eustace wants to start a business of apples. So he frequently enquires Courage about the total number of apples present on a range of trees. A range of trees is denoted by two integers, l and r (0<=l<=r< n) and includes the trees from l to r (both inclusive).
Courage is very loyal to Muriel and wants to keep some apples for her. So whenever Eustace asks about the total number of apples on a range, he deliberately doesn't count the apples on a tree, s, such that l<=s<=r and MIN(apples[l],apples[l+1],apples[l+2],...,apples[r])=apples[s].
In other words, while calculating the sum of apples on the trees in a range, Courage doesn't include the apples on the tree that has the minimum number of apples in that range.
Input:
The first line contains n, the number of magical trees.
The second line contains n non-negative integers that denote the array apples.
The third line contains a non negative integer p, which is the number of events that take place.
Now follow p lines. Each line will be of the form 'EAT x y' or 'GROW x y' or 'COUNT x y'.
'EAT x y' means that Courage ate x apples from the yth tree. (0<=y< n)
'GROW x y' means that x apples grew magically on the yth tree (0<=y< n).
And 'COUNT l r' means that Eustace has told Courage to count the number of apples on the range of trees from l to r, both inclusive.
Remember that the trees are indexed from 0.
Output:
For each 'COUNT x y' event, output a single number that Courage tells to Eustace.
Constraints:
1<=n<=100000
1<=p<=100000
0<=apples[i]<=10^9
0<=l<=r
0<=y
The number of apples on a tree never exceeds 10^9.
Sample:
Input: 10 6 5 12 48 3 20 4 2 3 7 6 COUNT 2 4 COUNT 7 9 GROW 12 4 COUNT 2 4 EAT 6 9 COUNT 7 9 Output: 60 10 63 5
Explanation of the Sample:
For 'COUNT 2 4', the sum of apples on trees 2,3 and 4 is 12+48+3=63. But as Courage doesn't include the apples on the tree with the minimum number of apples in the specified range (which in this case is the 4th tree), the number that he has to tell Eustace is 12+48=60.
For 'COUNT 7 9', the sum of apples on trees 7,8 and 9 is 2+3+7=12. In this case the tree with the minimum number of apples in the range is the 7th tree. So Courage tell Eustace the number 3+7=10
'GROW 12 4' means that the 4th tree, which has 3 apples, grows 12 more apples on it. So the number of apples on the 4th tree becomes 15.
For 'COUNT 2 4', the answer will be 48+15=63
'EAT 6 9' means that Courage eats 6 apples from the 9th tree. So the 9th tree now has 7-6=1 apple.
For 'COUNT 7 9, the answer will be 2+3=5
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i, n) for(int i = 0;i < n; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b) si(a);si(b)
#define endl '\n'
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
int n;
const int MAXN = 1e5+5;
struct Tree{ ll sum, minn; };
int arr[MAXN];
Tree T[4*MAXN];
void build(int node, int start, int end){
if(start > end)
return;
if(start == end){
T[node].minn = T[node].sum = arr[start];
return;
}
int mid = (start+end)>>1;
int left = node<<1, right = left+1;
build(left, start, mid);
build(right, mid+1, end);
T[node].sum = T[left].sum + T[right].sum;
T[node].minn = min(T[left].minn, T[right].minn);
}
//point update
void update(int node, int start, int end, int idx, int value){
if(start > end)
return;
if(start == end){
T[node].minn += (ll)value;
T[node].sum = T[node].minn;
return;
}
int mid = (start+end)>>1;
int left = node<<1, right = left+1;
if(idx <= mid){
update(left, start, mid, idx, value);
}
else if(idx > mid){
update(right, mid+1, end, idx, value);
}
T[node].sum = T[left].sum + T[right].sum;
T[node].minn = min(T[left].minn, T[right].minn);
}
//query
Tree query(int node, int start, int end, int l, int r){
if(start > end || start > r || end < l){
Tree res;
res.sum = 0;
res.minn = INT_MAX;
return res;
}
if(l <= start && end <= r){
return T[node];
}
int mid = (start+end)>>1;
int left = node<<1, right = left+1;
Tree leftRet = query(left, start, mid, l, r);
Tree rightRet = query(right, mid+1, end, l, r);
Tree res;
res.sum = leftRet.sum+rightRet.sum;
res.minn = min(leftRet.minn, rightRet.minn);
return res;
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
si(n);
FOR(i, n) si(arr[i]);
build(1, 0, n-1);
int q;
si(q);
while(q--){
char str[10];
scanf("%s", str);
int l, r;
sdi(l,r);
if(str[0] == 'C'){
Tree res = query(1, 0, n-1, l, r);
printf("%lld\n", res.sum-res.minn);
}else if(str[0] == 'E'){
update(1, 0, n-1, r, -l);
}else{
update(1, 0, n-1, r, l>;
}
}
return 0;
}Input
6 5 12 48 3 20 4 2 3 7
6
COUNT 2 4
COUNT 7 9
GROW 12 4
COUNT 2 4
EAT 6 9
COUNT 7 9
Output
10
63
5
Demonstration
SPOJ Solution-Living with Courage-Solution in C, C++, Java, Python