思路：
主席树模板。
注意内存的分配，原始的线段树有$2n$个结点，每次更新时最多增加$log(n)$个结点，总共有$q$次询问，所以存储结点的数组大小为$2N+q log(n)$。
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {
char ch;
while(!isdigit(ch=getchar()));
int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=,Q=,logN=;
class FotileTree {
private:
unsigned int left[(N<<)+Q*logN],right[(N<<)+Q*logN];
std::vector<int> val;
void push_up(const int p) {
val[p]=std::max(val[left[p]],val[right[p]]);
}
public:
unsigned int root[Q];
unsigned int newnode() {
val.push_back();
return val.size()-;
}
void build(const int p,const int b,const int e) {
if(b==e) {
val[p]=getint();
return;
}
int mid=(b+e)>>;
build(left[p]=newnode(),b,mid);
build(right[p]=newnode(),mid+,e);
push_up(p);
}
unsigned int modify(const int p,const int b,const int e,const int x,const int y) {
unsigned int new_p=newnode();
if(b==e) {
val[new_p]=y;
return new_p;
}
int mid=(b+e)>>;
if(x<=mid) left[new_p]=modify(left[p],b,mid,x,y),right[new_p]=right[p];
if(x>mid) right[new_p]=modify(right[p],mid+,e,x,y),left[new_p]=left[p];
push_up(new_p);
return new_p;
}
int query(const int p,const int b,const int e,const int l,const int r) {
if((b==l)&&(e==r)) return val[p];
int mid=(b+e)>>;
int ans=;
if(l<=mid) ans=std::max(ans,query(left[p],b,mid,l,std::min(mid,r)));
if(r>mid) ans=std::max(ans,query(right[p],mid+,e,std::max(mid+,l),r));
return ans;
}
};
FotileTree t;
int main() {
freopen("longterm_segtree.in","r+",stdin);
freopen("longterm_segtree.out","w+",stdout);
int n=getint(),q=getint(),ver=;
t.build(t.root[++ver]=t.newnode(),,n);
while(q--) {
int op=getint(),k=getint(),x=getint(),y=getint();
if(!op) printf("%d\n",t.query(t.root[k],,n,x,y));
if(op) t.root[++ver]=t.modify(t.root[k],,n,x,y);
}
fclose(stdin),fclose(stdout);
return ;
}