今天才发现统计的力量很坑爹，同时发现了我写线段树的漏洞。
首先说我自己的问题，线段树最后一层的第一个节点不能用，但我以前用了而且一直没出问题，这次涉及区间修改才出现问题。
然后是统计的力量，里面关于区间修改，区间查询最大值的代码有bug，不但修改上传标记与查询回收标记一个是求最小值的，一个是最大值的，而且标记上传也不完全，查询时不能改开区间等等问题，幸亏有奥特曼的程序，否则我一直调不出。
值得一提的是，zkw这种标记上传，差分思想确实很厉害。
ps:网上几乎找不到这种zkw线段树做动态修改的rmq问题的程序
{$M 1000000000}
uses math;
var m1,n,ans,s,ss,m:longint;
l,r,tail:array[1..1000000]of longint;
t:array[0..2621440]of longint;
next,sora:array[1..6000000]of longint;
procedure inf;
begin
assign(input,'river.in');reset(input);
assign(output,'river.out');rewrite(output)
end;
procedure ouf;
begin
close(input);close(output)
end;
procedure origin;
var i:longint;
begin
m1:=1;
while m1<n<<1+3 do m1:=m1<<1;
for i:=1 to n do tail[i]:=i;ss:=n
end;
procedure link(x,y:longint);
begin
inc(ss);next[tail[x]]:=ss;tail[x]:=ss;sora[ss]:=y;
inc(ss);next[tail[y]]:=ss;tail[y]:=ss;sora[ss]:=x
end;
procedure dfs(x,y:longint);
var i,ne:longint;
begin
inc(s);l[x]:=s;
i:=x;
while next[i]<>0 do begin
i:=next[i];ne:=sora[i];
if ne<>y then dfs(ne,x)
end;
inc(s);r[x]:=s
end;
procedure change(l,r,x:longint);
var a:longint;
begin
l:=l+m1-1;r:=r+m1+1;
while not(l xor r=1) do begin
if l and 1=0 then inc(t[l+1],x);
if r and 1=1 then inc(t[r-1],x);
a:=max(t[l],t[l xor 1]);dec(t[l],a);dec(t[l xor 1],a);inc(t[l>>1],a);
a:=max(t[r],t[r xor 1]);dec(t[r],a);dec(t[r xor 1],a);inc(t[r>>1],a);
l:=l>>1;r:=r>>1
end;
while l<>1 do begin
a:=max(t[l],t[l xor 1]);
if a<>0 then begin dec(t[l],a);dec(t[l xor 1],a);inc(t[l>>1],a) end
else l:=2;
l:=l>>1;
end;
end;
function ask(l,r:longint):longint;
var lans,rans:longint;
begin
// if l=r then exit(t[l+m1]);
l:=l+m1;r:=r+m1;lans:=0;rans:=0;
while not(l xor r=1) do begin
inc(lans,t[l]);inc(rans,t[r]);
if l and 1=0 then lans:=max(lans,t[l+1]);
if r and 1=1 then rans:=max(rans,t[r-1]);
l:=l>>1;r:=r>>1
end;
ask:=max(lans+t[l],rans+t[r]);
l:=l>>1;
while l>0 do begin
ask:=ask+t[l];
l:=l>>1;
end
end;
procedure init;
var i,j,k,x,y:longint;
ch:char;
begin
readln(n,m);
origin;
for i:=1 to n do begin
read(x,j);
for j:=1 to j do begin
read(k);
link(x,k)
end;
readln
end;
fillchar(t,sizeof(t),0);s:=0;
dfs(1,0);
for i:=1 to m do begin
read(ch);
if ch='P' then begin
readln(x);
ans:=ask(l[x],r[x]);
writeln(max(ans,0))
end
else if ch='A' then begin
readln(x,y);
change(l[x],r[x],y)
end
else if ch='D' then begin
readln(x,y);
change(l[x],r[x],-y)
end
end
end;
begin
inf;
init;
ouf
end.
c++版
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int oo=1073741819;
long long n,m,ss,m1,len,ans;
long long b[1048576+5],tail[500000+5],next[500000+5],sora[500000+5],l[500000+5],r[500000+5];
//int b[524+5],tail[100+5],next[200+5],sora[200+5],l[100+5],r[100+5];
void origin()
{
int i;
ss=n;
for (i=1;i<=n;i++)
tail[i]=i;
m1=1;
for (;m1<=(n<<1)+2;)
m1<<=1;
}
void link(int x,int y)
{
ss++;next[tail[x]]=ss;tail[x]=ss;sora[ss]=y;
// ss++;next[tail[y]]=ss;tail[y]=ss;sora[ss]=x;
}
void dfs(int x)
{
int i,ne;
len++;l[x]=len;
for (i=x;next[i]!=0;)
{
i=next[i],ne=sora[i];
dfs(ne);
}
len++;r[x]=len;
}
int max(long long x,long long y)
{
return (x>y) ? x : y;
}
void add(int l,int r,long long w)
{
int k=0;
for (l +=m1-1,r +=m1+1;!((l^r)==1);l>>=1,r>>=1)
{
if ((l&1)==0) b[l+1]+=w;
if ((r&1)==1) b[r-1]+=w;
k=max(b[l],b[l^1]);b[l]-=k;b[l^1]-=k;b[l>>1]+=k;
k=max(b[r],b[r^1]);b[r]-=k;b[r^1]-=k;b[r>>1]+=k;
}
for (;l!=1;l>>=1)
{
k=max(b[l],b[l^1]);b[l]-=k;b[l^1]-=k;b[l>>1]+=k;
}
}
int ask(int l,int r)
{
long long ans=-oo,lans=0,rans=0;
for (l+=m1,r+=m1;!((l^r)==1);l>>=1,r>>=1)
{
lans+=b[l],rans+=b[r];
if ((l&1)==0) lans=max(lans,b[l+1]);
if ((r&1)==1) rans=max(rans,b[r-1]);
}
ans=max(lans+b[l],rans+b[r]);
for (l>>=1;l;l>>=1)
ans+=b[l];
return ans;
}
void init()
{
int i,j,x,k,y;
char ch,ch1;
scanf("%d%d",&n,&m);
origin();
for (i=1;i<=n;i++)
{
scanf("%d%d",&x,&k);
for (j=1;j<=k;j++)
{
scanf("%d",&y);
link(x,y);
}
scanf("\n");
}
memset(b,0,sizeof(b));
len=0;
dfs(1);
for (i=1;i<=m;)
{
scanf("%c",&ch);
if (ch=='A')
{
scanf("%d%d\n",&x,&k);
add(l[x],r[x],k);
}
else if (ch=='D')
{
scanf("%d%d\n",&x,&k);
add(l[x],r[x],-k);
}
else if (ch=='P')
{
scanf("%d\n",&x);
ans=ask(l[x],r[x]);
printf("%d\n",max(ans,0));
}
i++;
}
}
int main()
{
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
init();
return 0;
}