记录编号	367835	评测结果	AAAAAAAAAA
题目名称	可持久化线段树	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.103 s
提交时间	2017-02-02 13:12:19	内存使用	17.21 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <list>
#include <string>
#include <cstring>
#include <cctype>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
}; using IO::readint; using IO::readc;
#define MAXN 10001
struct node{
  node *ls, *rs;
  int maxv;
  #define MAXV(x) ((x)?(x)->maxv:-0x7ffffff)
  void pushup(){maxv = max(MAXV(ls), MAXV(rs));}
};
inline node *new_node(){
  static node ns[(MAXN<<1)+14*100001];
  static int top = 0;
  return ns+top++;
}
node *modify(node *x, int p, int L, int R, int v){
  if(!x)return NULL;
  node *d = new_node(); *d = *x;
  if(L == R && p == L)
    d->maxv = v;
  else{
    int M = (L+R)>>1;
    if(p <= M)d->ls = modify(d->ls, p, L, M, v);
    else if(p > M)d->rs = modify(d->rs, p, M+1, R, v);
    d->pushup();
  }
  return d;
}
int query(node *x, int ql, int qr, int L, int R){
  if(!x)return -0x7ffffff;
  if(ql <= L && R <= qr)return x->maxv;
  int M = (L+R)>>1, ret = -0x7ffffff;
  if(ql <= M)ret = max(ret, query(x->ls, ql, qr, L, M));
  if(qr > M)ret = max(ret, query(x->rs, ql, qr, M+1, R));
  return ret;
}
node *roots[100001];
int data[10001];
node *build(int l, int r){
  if(l > r)return NULL;
  node *d = new_node();
  if(l == r)d->maxv = data[l];
  else{
    int m = (l+r)>>1;
    d->ls = build(l, m);
    d->rs = build(m+1, r);
    d->pushup();
  }
  return d;
}
int main(){
  freopen("longterm_segtree.in", "r", stdin);
  freopen("longterm_segtree.out", "w", stdout);
  int n = readint(); int q = readint();
  for(int i = 1; i <= n; i++)data[i] = readint();
  roots[1] = build(1, n);
  int cver = 1;
  while(q--){
    int op = readint(); int ver = readint();
    int arg1 = readint(); int arg2 = readint();
    if(op == 1)roots[++cver] = modify(roots[ver], arg1, 1, n, arg2);      
    else if(op == 0)printf("%d\n", query(roots[ver], arg1, arg2, 1, n));
  }
  return 0;
}