【UOJ228】基础数据结构练习题（线段树）

题意：在一个序列中支持以下操作：

1.区间加

2.区间开根向下取整

3.区间求和

n,m<=100000

思路：因为有区间开根的存在暴力更改会导致O(n)的时间复杂度

所以我们要特判两种情况（别问我我不知道为什么）

1.sqrt(max)=sqrt(min)

这种情况说明开根后这段区间都是一个数，等价于区间赋值

2.sqrt(max)-sqrt(min)=1 & max-min=1

这种情况下这段区间开根后减少的值相同，等价于区间减

加上这两个转化优化后就能过了，也许是前人的经验吧

  1 var t:array[1..500000]of record
  2                           a,b,s,mx,mn:int64;
  3                          end;
  4     a:array[1..200000]of longint;
  5     n,m,i,x,y,z,p:longint;
  6 
  7 function max(x,y:int64):int64;
  8 begin
  9  if x>y then exit(x);
 10  exit(y);
 11 end;
 12 
 13 function min(x,y:int64):int64;
 14 begin
 15  if x<y then exit(x);
 16  exit(y);
 17 end;
 18 
 19 procedure pushup(x:longint);
 20 var l,r:longint;
 21 begin
 22  l:=x<<1; r:=l+1;
 23  t[x].mx:=max(t[l].mx,t[r].mx);
 24  t[x].mn:=min(t[l].mn,t[r].mn);
 25  t[x].s:=t[l].s+t[r].s;
 26 end;
 27 
 28 procedure add2(l,r:longint;v:int64;x:longint);
 29 begin
 30  t[x].mx:=t[x].mx+v;
 31  t[x].mn:=t[x].mn+v;
 32  t[x].s:=t[x].s+v*(r-l+1);
 33  t[x].a:=t[x].a+v;
 34 end;
 35 
 36 procedure set1(l,r:longint;v:int64;x:longint);
 37 begin
 38  t[x].mx:=v;
 39  t[x].mn:=v;
 40  t[x].s:=v*(r-l+1);
 41  t[x].b:=v;
 42  t[x].a:=0;
 43 end;
 44 
 45 procedure pushdown(l,r,x:longint);
 46 var mid:longint;
 47 begin
 48  if l=r then
 49  begin
 50   t[x].a:=0;
 51   exit;
 52  end;
 53  if t[x].b<>0 then
 54  begin
 55   mid:=(l+r)>>1;
 56   set1(l,mid,t[x].b,x<<1);
 57   set1(mid+1,r,t[x].b,x<<1+1);
 58   t[x].b:=0;
 59  end;
 60  if t[x].a<>0 then
 61  begin
 62   mid:=(l+r)>>1;
 63   add2(l,mid,t[x].a,x<<1);
 64   add2(mid+1,r,t[x].a,x<<1+1);
 65   t[x].a:=0;
 66  end;
 67 end;
 68 
 69 procedure build(l,r,p:longint);
 70 var mid:longint;
 71 begin
 72  if l=r then
 73  begin
 74   t[p].s:=a[l]; t[p].mx:=a[l]; t[p].mn:=a[l];
 75   exit;
 76  end;
 77  mid:=(l+r)>>1;
 78  build(l,mid,p<<1);
 79  build(mid+1,r,p<<1+1);
 80  pushup(p);
 81 end;
 82 
 83 procedure add1(l,r,x,y:longint;v:int64;p:longint);
 84 var mid:longint;
 85 begin
 86  pushdown(l,r,p);
 87  if (l>=x)and(r<=y) then
 88  begin
 89   add2(l,r,v,p);
 90   exit;
 91  end;
 92  mid:=(l+r)>>1;
 93  if x<=mid then add1(l,mid,x,y,v,p<<1);
 94  if y>mid then add1(mid+1,r,x,y,v,p<<1+1);
 95  pushup(p);
 96 end;
 97 
 98 procedure sqrt1(l,r,x,y,p:longint);
 99 var mid:longint;
100     s1,s2:int64;
101 begin
102  pushdown(l,r,p);
103  mid:=(l+r)>>1;
104  if (l>=x)and(r<=y) then
105  begin
106   s1:=trunc(sqrt(t[p].mx));
107   s2:=trunc(sqrt(t[p].mn));
108   if s1=s2 then set1(l,r,s1,p)
109    else if (s1-s2=1)and(t[p].mx-t[p].mn=1) then add2(l,r,s1-t[p].mx,p)
110     else
111     begin
112      sqrt1(l,mid,x,y,p<<1);
113      sqrt1(mid+1,r,x,y,p<<1+1);
114      pushup(p);
115     end;
116   exit;
117  end;
118  if x<=mid then sqrt1(l,mid,x,y,p<<1);
119  if y>mid then sqrt1(mid+1,r,x,y,p<<1+1);
120  pushup(p);
121 end;
122 
123 function query(l,r,x,y,p:longint):int64;
124 var mid:longint;
125 begin
126  pushdown(l,r,p);
127  if (l>=x)and(r<=y) then exit(t[p].s);
128  mid:=(l+r)>>1;
129  query:=0;
130  if x<=mid then query:=query+query(l,mid,x,y,p<<1);
131  if y>mid then query:=query+query(mid+1,r,x,y,p<<1+1);
132  pushup(p);
133 end;
134 
135 begin
136  assign(input,'uoj228.in'); reset(input);
137  assign(output,'uoj228.out'); rewrite(output);
138  readln(n,m);
139  for i:=1 to n do read(a[i]);
140  build(1,n,1);
141  for i:=1 to m do
142  begin
143   read(p);
144   case p of
145    1:
146    begin
147     read(x,y,z);
148     add1(1,n,x,y,z,1);
149    end;
150    2:
151    begin
152     read(x,y);
153     sqrt1(1,n,x,y,1);
154    end;
155    3:
156    begin
157     read(x,y);
158     writeln(query(1,n,x,y,1));
159    end;
160   end;
161  end;
162 
163  close(input);
164  close(output);
165 end.