bzoj2482

还是像以前那样维护下次出现位置，计算影响
其实不难，思维盲点，受到做最大子段和的影响
其实这里可以直接维护当前每个位置的子段和，再记录一个历史最大和
当然tag也需要记录当前tag和历史（距离上次push）最大累加
  1 type node=record
  2        x,y,id:longint;
  3      end;
  4 
  5 var lazy,tree:array[0..100010*4,0..1] of longint;
  6     ans,next,a:array[0..100010] of longint;
  7     last:array[-100010..100010] of longint;
  8     q:array[0..100010] of node;
  9     i,j,n,m:longint;
 10 
 11 function max(a,b:longint):longint;
 12   begin
 13     if a>b then exit(a) else exit(b);
 14   end;
 15 
 16 procedure swap(var a,b:node);
 17   var c:node;
 18   begin
 19     c:=a;
 20     a:=b;
 21     b:=c;
 22   end;
 23 
 24 procedure sort(l,r:longint);
 25   var i,j,x:longint;
 26   begin
 27     i:=l;
 28     j:=r;
 29     x:=q[(l+r) shr 1].x;
 30     repeat
 31       while q[i].x>x do inc(i);
 32       while x>q[j].x do dec(j);
 33       if i<=j then
 34       begin
 35         swap(q[i],q[j]);
 36         inc(i);
 37         dec(j);
 38       end;
 39     until i>j;
 40     if l<j then sort(l,j);
 41     if i<r then sort(i,r);
 42   end;
 43 
 44 procedure get(i,x0,x1:longint);
 45   begin
 46     tree[i,0]:=max(tree[i,0],tree[i,1]+max(x0,x1));
 47     lazy[i,0]:=max(lazy[i,0],lazy[i,1]+max(x0,x1));
 48     inc(lazy[i,1],x1);
 49     inc(tree[i,1],x1);
 50   end;
 51 
 52 procedure update(i:longint);
 53   begin
 54     tree[i,0]:=max(tree[i*2,0],tree[i*2+1,0]);
 55     tree[i,1]:=max(tree[i*2,1],tree[i*2+1,1]);
 56   end;
 57 
 58 procedure push(i:longint);
 59   begin
 60     if (lazy[i,1]=0) and (lazy[i,0]=0) then exit;
 61     get(i*2,lazy[i,0],lazy[i,1]);
 62     get(i*2+1,lazy[i,0],lazy[i,1]);
 63     lazy[i,0]:=0;
 64     lazy[i,1]:=0;
 65   end;
 66 
 67 procedure add(i,l,r,x,y,z:longint);
 68   var m:longint;
 69   begin
 70     if (x<=l) and (y>=r) then get(i,0,z)
 71     else begin
 72       m:=(l+r) shr 1;
 73       push(i);
 74       if x<=m then add(i*2,l,m,x,y,z);
 75       if y>m then add(i*2+1,m+1,r,x,y,z);
 76       update(i);
 77     end;
 78   end;
 79 
 80 function ask(i,l,r,x:longint):longint;
 81   var m:longint;
 82   begin
 83     if l=r then exit(tree[i,0])
 84     else begin
 85       m:=(l+r) shr 1;
 86       push(i);
 87       if x<=m then exit(ask(i*2,l,m,x))
 88       else exit(max(tree[i*2,0],ask(i*2+1,m+1,r,x)));
 89     end;
 90   end;
 91 
 92 begin
 93   readln(n);
 94   for i:=1 to n do
 95     read(a[i]);
 96   for i:=n downto 1 do
 97   begin
 98     next[i]:=last[a[i]];
 99     last[a[i]]:=i;
100   end;
101   readln(m);
102   for i:=1 to m do
103   begin
104     readln(q[i].x,q[i].y);
105     q[i].id:=i;
106   end;
107   sort(1,m); 
108   j:=1;
109   for i:=n downto 1 do
110   begin
111     if next[i]=0 then next[i]:=n+1;
112     add(1,1,n,i,next[i]-1,a[i]);
113     while (j<=m) and (q[j].x=i) do
114     begin
115       ans[q[j].id]:=ask(1,1,n,q[j].y);
116       inc(j);
117     end;
118     if j=m+1 then break;
119   end;
120   for i:=1 to m do
121     writeln(ans[i]);
122 end.
View Code