[BZOJ 3038 & & BZOJ 3211] 위치 분석 라인 트 리

위치 분석 라인 트 리 는 이러한 것 이다. 어떤 조작 에 대해 자성 표 시 를 하지 않 고 폭력 적 으로 변경 할 수 있 지만 조작 이 적은 후에 결 과 를 바 꾸 지 않 을 것 이다 (가장 흔히 볼 수 있 는 것 은 구간 개근 번호). 우 리 는 이 구간 이 바 뀔 수 있 는 지 를 유지 할 수 있다.예: 구간 루트 번 호 를 열 고 min 과 max 를 유지 합 니 다. 만약 min > = 0 및 max < = 1 은 상관 하지 않 습 니 다.구간 을 정리 하고 min 과 max 를 유지 하 며 min + 1 = max 가 있 으 면 구간 수정 또는 구간 가 (아 례 합숙 훈련 day 1 T1) 로 직접 변 합 니 다.
코드:

type
  tree=^treenode;
  treenode=record
    l,r,max,min:longint;
    sum:int64;
    ls,rs:tree;
  end;

var
  n,i,q,opt,l,r:longint;
  delta:array[0..100100]of longint;
  xtr:tree;
function max(x,y:longint):longint;
begin
  if xthen exit(y)
  else exit(x);
end;
function min(x,y:longint):longint;
begin
  if x>y then exit(y)
  else exit(x);
end;
procedure updata(x:tree);
begin
  x^.max:=max(x^.ls^.max,x^.rs^.max);
  x^.min:=min(x^.ls^.min,x^.rs^.min);
  x^.sum:=x^.ls^.sum+x^.rs^.sum;
end;

procedure build(x:tree;l,r:longint);
var
  mid:longint;
begin
  x^.l:=l;
  x^.r:=r;
  if l=r then
  begin
    x^.max:=delta[l];
    x^.min:=delta[l];
    x^.sum:=delta[l];
    x^.ls:=nil;
    x^.rs:=nil;
    exit;
  end;
  mid:=(l+r)div 2;
  new(x^.ls);new(x^.rs);
  build(x^.ls,l,mid);
  build(x^.rs,mid+1,r);
  updata(x);
end;
function ask(x:tree;l,r:longint):int64;
var
  mid:longint;
begin
  if (x^.l=l)and(x^.r=r) then exit(x^.sum);
  mid:=(x^.l+x^.r)div 2;
  if r<=mid then exit(ask(x^.ls,l,r));
  if l>mid then exit(ask(x^.rs,l,r));
  exit(ask(x^.ls,l,mid)+ask(x^.rs,mid+1,r));
end;
procedure change(x:tree;l,r:longint);
var
  mid:longint;
begin
  if (x^.max<=1)and(x^.min>=0) then exit;
  if x^.l=x^.r then begin x^.sum:=trunc(sqrt(x^.sum)); x^.max:=x^.sum; x^.min:=x^.sum; exit; end;
  mid:=(x^.l+x^.r)div 2;
  if r<=mid then change(x^.ls,l,r)
  else if l>mid then change(x^.rs,l,r)
    else
    begin
      change(x^.ls,l,mid);
      change(x^.rs,mid+1,r);
    end;
  updata(x);
end;
begin
  readln(n);
  for i:=1 to n do
    read(delta[i]);
  new(xtr);
  build(xtr,1,n);
  readln(q);
  for i:=1 to q do
  begin
    readln(opt,l,r);
    if opt=1 then writeln(ask(xtr,l,r))
    else change(xtr,l,r);
  end;
end.