Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/detail/standard_policies.hpp>
- using namespace std;
- using namespace __gnu_cxx;
- using namespace __gnu_pbds;
- typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll;
- typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vii; typedef vector<pll> vll;
- typedef map<ll, ll> mii; typedef map<string, ll> msi; typedef vector< vi > vvi;
- #define sz size()
- #define pb push_back
- #define inf (1<<30)
- #define mod (1000000007)
- #define pi (acos(-1.0))
- #define mem(a,b) memset((a), (b), sizeof(a));
- #define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define what_is(x) cerr << #x << " is " << x << endl;
- #define rep(i, n) for(__typeof(n) i=0; i<(n); i++)
- #define foab(i, a, b) for(__typeof(b) i=(a); i<=(b); i++)
- #define foba(i, a, b) for(__typeof(b) i=(b); i>=(a); i--)
- #define foch(it, l) for(__typeof((l).begin()) it = begin(l); it != end(l); it++)
- #define d_value(x) cout<<fixed<<setprecision(x);
- #define file_io { \
- freopen("input.txt", "r", stdin); \
- freopen("output.txt", "w", stdout); \
- }
- #define error(args...) { \
- string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
- stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); \
- }
- void err(istream_iterator<string> it) {} template<typename T, typename... Args>
- void err(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << endl; err(++it, args...); }
- inline ll bigMul(ll a,ll b,ll m){
- ll result = 0; a %= m;
- while(b) { if(b&1LL) result=(result+a)%m; a=(a+a)%m; b>>=1; }
- return result;
- }
- ll bigMod(ll b, ll e, ll m){
- if(!e)return 1%m;
- if(!(e&1LL)){ ll y = bigMod(b, e>>1LL, m); return bigMul(y, y, m); }
- ll z = bigMod(b, e-1, m); return (bigMul(b%m, z, m));
- }
- /**Define BitWise operation**/
- #define checkBit(n, pos) (n & (1<<(pos)))
- #define bitOn(n, pos) (n | (1<<(pos)))
- #define bitOff(n, pos) (n & ~(1<<(pos)))
- inline void printBits(int n){ if(n >= 2)printBits(n/2); cout<<(n&1); }
- inline int countOnes(int n) { int r=0; while(n && ++r) n -= n&(-n); return r; }
- template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- template <typename T>
- string toString(T n) { stringstream ss; ss << n; return ss.str(); }
- template< typename T >
- T exEuclid(T a, T b, T& x, T& y) {
- if(!b){ x = 1, y = 0; return a; }
- T x1, y1, temp = exEuclid<T>(b, a%b, x1, y1);
- x = y1, y = x1 - y1*(a/b);
- return temp;
- }
- template< typename T >
- inline T modInverse(T a, T m){ T x, y; T g = exEuclid<T>(a, m, x, y); if(g != 1){ return -1; } else{ return (x%m + m)%m; } }
- template<typename T> ostream&
- operator<<(ostream& os, const vector<T> &t) { ll n = t.size(); rep(i, n) os<<t[i]<<" "; return os; }
- template<typename T,typename TT>
- ostream& operator<<(ostream &os, const pair<T,TT> &t) { return os<<"("<<t.first<<","<<t.second<<")"; }
- enum COLOR{ white=1 , grey=2 , black=3, red = 4, green = 5, blue = 6 };
- vii dir_4 {{1,0}, {0,1}, {-1,0}, {0,-1}};
- vii dir_8 {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}};
- vii dir_knight {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}};
- //-------------- ---------------- ----------------- --------------- ------------ ----------
- //This is a Segment Tree Data structure for Range Query, Point Update
- class SegmentTree{
- int* ara;
- pii *tree;//{max, indx}
- public:
- explicit SegmentTree(int n, const int _ara[]){
- ara = new int[n+1], tree = new pii[4*n+1];
- foab(i, 1, n){
- ara[i] = _ara[i-1];
- }
- }
- void init(const int& pos, const int& begin, const int& end){
- if(begin == end){//leaf node
- tree[pos] = {ara[end], end};
- }else{//internal node
- init(pos<<1, begin, (begin+end)>>1);
- init((pos<<1)+1, ((begin+end)>>1)+1, end);
- tree[pos] = tree[pos<<1].first > tree[(pos<<1)+1].first? tree[pos<<1] : tree[(pos<<1)+1];
- }
- }
- void update(const int& pos, const int& begin, const int& end, const int& indx, const int& newVal){
- if(end < indx || indx < begin){//out of boundary
- return;
- }else if(indx<=begin && indx>=end){//relevant segment(index)
- tree[pos].first = newVal;
- }else{//partial overlap
- update(pos<<1, begin, (begin+end)>>1, indx, newVal);
- update((pos<<1)+1, ((begin+end)>>1)+1, end, indx, newVal);
- tree[pos] = tree[pos<<1].first > tree[(pos<<1)+1].first? tree[pos<<1] : tree[(pos<<1)+1];
- }
- }
- pii query(const int& pos, const int& begin, const int& end, const int& i, const int& j){
- if(i > j)return {0, -1};
- if(i<=begin && end<=j){//relevant segment
- return tree[pos];
- }else if(j<begin || i>end){//out of boundary
- return {0, -1};
- }else{//partial overlap
- pii left = query(pos<<1, begin, (begin+end)>>1, i, j);
- pii right = query((pos<<1)+1, ((begin+end)>>1)+1, end, i, j);
- if(left.first > right.first)return left;
- else return right;
- }
- }
- virtual ~SegmentTree(){
- delete [] ara;
- delete [] tree;
- ara = nullptr, tree = nullptr;
- }
- };
- int main(int argc, char** argv) {
- #ifdef LOCAL
- file_io
- #endif
- //d_value(20);
- fast_io
- int n; cin>>n;
- int ara[n]; rep(i, n)cin>>ara[i];
- SegmentTree tumi(n, ara);
- tumi.init(1, 1, n);
- int q; cin>>q;
- while(q--){
- char ch; int x, y;
- cin>>ch>>x>>y;
- if(ch == 'U'){
- tumi.update(1, 1, n, x, y);
- }else{
- pii f = tumi.query(1, 1, n, x, y);
- pii a = tumi.query(1, 1, n, x, f.second-1);
- pii b = tumi.query(1, 1, n, f.second+1, y);
- a.first > b.first? f.first+=a.first: f.first+=b.first;
- cout<<f.first<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement