{\rtf1\ansi\ansicpg1252\cocoartf1504\cocoasubrtf830
{\fonttbl\f0\fnil\fcharset0 Menlo-Regular;}
{\colortbl;\red255\green255\blue255;\red100\green56\blue32;\red196\green26\blue22;\red170\green13\blue145;
\red0\green0\blue0;\red92\green38\blue153;\red28\green0\blue207;\red63\green110\blue116;\red38\green71\blue75;
\red46\green13\blue110;}
{\*\expandedcolortbl;;\csgenericrgb\c39100\c22000\c12500;\csgenericrgb\c77000\c10200\c8600;\csgenericrgb\c66500\c5200\c56900;
\csgenericrgb\c0\c0\c0;\csgenericrgb\c35900\c14900\c60100;\csgenericrgb\c11000\c0\c81000;\csgenericrgb\c24700\c43100\c45600;\csgenericrgb\c14900\c27800\c29400;
\csgenericrgb\c18100\c5200\c43100;}
\paperw11900\paperh16840\margl1440\margr1440\vieww10800\viewh8400\viewkind0
\deftab272
\pard\tx272\pardeftab272\pardirnatural\partightenfactor0

\f0\fs22 \cf2 \CocoaLigature0 #include \cf3 <cstdio>\cf2 \
#include \cf3 <algorithm>\cf2 \
\cf4 using\cf5  \cf4 namespace\cf5  \cf6 std\cf5 ;\
\cf4 const\cf5  \cf4 int\cf5  NMAX = \cf7 100000\cf5 ;\
\cf4 int\cf5  v[\cf8 NMAX\cf5  * \cf7 4\cf5  + \cf7 5\cf5 ];\
\cf4 void\cf5  update(\cf4 int\cf5  nod, \cf4 int\cf5  poz, \cf4 int\cf5  val, \cf4 int\cf5  st, \cf4 int\cf5  dr)\
\{\
  \cf4 if\cf5 (st == dr) \{\
        \cf8 v\cf5 [nod] = val;\
        \cf4 return\cf5  ;\
      \}\
    \cf4 int\cf5  mij = (st + dr) / \cf7 2\cf5 ;\
    \cf4 if\cf5 (poz <= mij) \{\
        \cf9 update\cf5 (nod * \cf7 2\cf5 , poz, val, st, mij);\
      \}\
    \cf4 else\cf5  \{\
        \cf9 update\cf5 (nod * \cf7 2\cf5  + \cf7 1\cf5 , poz, val, mij + \cf7 1\cf5 , dr);\
      \}\
    \cf8 v\cf5 [nod] = \cf10 max\cf5 (\cf8 v\cf5 [nod * \cf7 2\cf5 ], \cf8 v\cf5 [nod * \cf7 2\cf5  + \cf7 1\cf5 ]);\
\}\
\cf4 int\cf5  query(\cf4 int\cf5  nod, \cf4 int\cf5  a, \cf4 int\cf5  b, \cf4 int\cf5  st, \cf4 int\cf5  dr)\
\{\
    \cf4 if\cf5 (a <= st && dr <= b) \{\
        \cf4 return\cf5  \cf8 v\cf5 [nod];\
      \}\
    \cf4 int\cf5  sol1 = \cf7 0\cf5 , sol2 = \cf7 0\cf5 ;\
    \cf4 int\cf5  mij = (st + dr) / \cf7 2\cf5 ;\
    \cf4 if\cf5 (a <= mij) \{\
        sol1 = \cf9 query\cf5 (nod * \cf7 2\cf5 , a, b, st, mij);\
      \}\
    \cf4 if\cf5 (mij < b) \{\
        sol2 = \cf9 query\cf5 (nod * \cf7 2\cf5  + \cf7 1\cf5 , a, b, mij + \cf7 1\cf5 , dr);\
      \}\
    \cf4 return\cf5  \cf10 max\cf5 (sol1, sol2);\
\}\
 \
\cf4 int\cf5  main()\
\{\
    \cf4 int\cf5  n, m;\
    \cf10 freopen\cf5 (\cf3 "arbint.in"\cf5 , \cf3 "r"\cf5 , \cf2 stdin\cf5 );\
    \cf10 freopen\cf5 (\cf3 "arbint.out"\cf5 , \cf3 "w"\cf5 , \cf2 stdout\cf5 );\
    \cf10 scanf\cf5 (\cf3 "%d%d"\cf5 , &n, &m);\
    \cf4 for\cf5 (\cf4 int\cf5  i = \cf7 1\cf5 ; i <= n; ++i) \{\
        \cf4 int\cf5  val;\
        \cf10 scanf\cf5 (\cf3 "%d"\cf5 , &val);\
        \cf9 update\cf5 (\cf7 1\cf5 , i, val, \cf7 1\cf5 , n);\
      \}\
    \cf4 for\cf5 (\cf4 int\cf5  q = \cf7 0\cf5 ; q < m; ++q) \{\
        \cf4 int\cf5  t, a, b;\
        \cf10 scanf\cf5 (\cf3 "%d%d%d"\cf5 , &t, &a, &b);\
        \cf4 if\cf5 (t == \cf7 1\cf5 ) \{\
            \cf9 update\cf5 (\cf7 1\cf5 , a, b, \cf7 1\cf5 , n);\
          \}\
        \cf4 else\cf5  \{\
            \cf10 printf\cf5 (\cf3 "%d\\n"\cf5 , \cf9 query\cf5 (\cf7 1\cf5 , a, b, \cf7 1\cf5 , n));\
          \}\
      \}\
    \cf4 return\cf5  \cf7 0\cf5 ;\
\}\
}