spoj-problems/KGSS.cpp at master · h-sinha/spoj-problems · GitHub

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
typedef long long ll;
typedef long double ld;
const int L=1e5;
std::map<int, int> counter;
set<int> SET;
pair<int,string> PAIR;
#define sz(a)	ll(a.size())
#define ln "\n"
int m=1000000007;
int arr[100002];
pii seg[4000002];
void build(int s,int e,int index)
{
	if(s>=e)
	{
		seg[index]=mp(arr[s],INT_MIN);
		return;
	}
	int mid=(s+e)/2;
	build(s,mid,index<<1);
	build(mid+1,e,(index<<1)+1);
	std::vector<int> v;
	v.pb(seg[index<<1].F);
	v.pb(seg[index<<1].S);
	v.pb(seg[(index<<1)+1].F);
	v.pb(seg[(index<<1)+1].S);
	sort(v.begin(), v.end());
	pii temp=mp(v[3],v[2]);
	v.clear();
	seg[index]=temp;
	return ;
}
pii query(int s,int e,int l,int r,int index)
{
	if(e<l || s>r )return mp(INT_MIN,INT_MIN);
	if(s>=l && e<=r)
		return seg[index];
	pii q1,q2;
	int mid=(s+e)/2;
	q1=query(s,mid,l,r,index<<1);
	q2=query(mid+1,e,l,r,(index<<1)+1);
	std::vector<int> v;
	v.pb(q1.F);
	v.pb(q1.S);
	v.pb(q2.F);
	v.pb(q2.S);
	sort(v.begin(), v.end());
	pii temp=mp(v[3],v[2]);
	v.clear();
	return temp;
}
void update(int s,int e,int index,int updind)
{
	if(updind<s||updind>e)return;
	if(updind==s && updind==e)
	{
		seg[index]=mp(arr[s],INT_MIN);
		return;
	}
	int mid=(s+e)/2;
	if(updind<=mid)
		update(s,mid,index<<1,updind);
	else
		update(mid+1,e,(index<<1)+1,updind);
	std::vector<int> v;
	v.pb(seg[index<<1].F);
	v.pb(seg[index<<1].S);
	v.pb(seg[(index<<1)+1].F);
	v.pb(seg[(index<<1)+1].S);
	sort(v.begin(), v.end());
	pii temp=mp(v[3],v[2]);
	v.clear();
	seg[index]=temp;
	return;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,x,y,q;
	char ch;
	cin>>n;
	FOR(i,1,n+1)cin>>arr[i];
	build(1,n,1);
	cin>>q;
	while(q--)
	{
		cin>>ch>>x>>y;
		if(ch=='U')
		{
			arr[x]=y;
			update(1,n,1,x);
		}
		else
		{
			pii temp=query(1,n,x,y,1);
			cout<<temp.F+temp.S<<ln;
		}
	}
	return 0;
}