这题的坑开了很久了，3305大概是在NOIP之前学线段树的时候AC的，3306也是当时学完LCA后不断提交不断WA，当时基本已弃坑。。。
最近学了树链剖分之后似乎觉得这俩题可做，于是搞了一个晚上，终于搞完了（蒟蒻就是蒟蒻）。。。。。。
3305 这个题是链上的裸线段树，分类讨论比较蛋疼，code：#include<iostream>#include<cstdio>#include<cstring>using namespace std;struct hp{int maxn,minn,cha1,cha2;}node[800001];int a[200001],n,m;void updata(int i){int c,t;node[i].maxn=max(node[i*2].maxn,node[i*2+1].maxn);node[i].minn=min(node[i*2].minn,node[i*2+1].minn);t=node[i*2+1].maxn-node[i*2].minn; c=node[i*2].maxn-node[i*2+1].minn;node[i].cha1=max(t,max(node[i*2].cha1,node[i*2+1].cha1));node[i].cha2=max(c,max(node[i*2+1].cha2,node[i*2].cha2));}void build(int i,int l,int r){ int mid; mid=(l+r)/2;if (l==r){node[i].maxn=node[i].minn=a[l];node[i].cha1=node[i].cha2=0;return;}build(i*2,l,mid);build(i*2+1,mid+1,r);updata(i);}hp queryx(int i,int l,int r,int x,int y){ int mid=(l+r)/2; if (y<l||x>r) return (hp){-1,100000001,-1,-1}; if ((x<=l)&&(y>=r)) return node[i];hp tmp1=queryx(i*2,l,mid,x,y),tmp2=queryx(i*2+1,mid+1,r,x,y),tmp;tmp.cha1=max(tmp1.cha1,max(tmp2.cha1,tmp2.maxn-tmp1.minn));tmp.cha2=max(tmp1.cha2,max(tmp2.cha2,tmp1.maxn-tmp2.minn));tmp.minn=min(tmp1.minn,tmp2.minn);tmp.maxn=max(tmp1.maxn,tmp2.maxn);return tmp;}int main(){int i,l,r;scanf("%d",&n);for (i=1;i<=n;++i)scanf("%d",&a[i]);build(1,1,n);scanf("%d",&m);for (i=1;i<=m;++i){scanf("%d%d",&l,&r);if (l<=r)printf("%d\n",queryx(1,1,n,l,r).cha1);if (r<l)printf("%d\n",queryx(1,1,n,r,l).cha2);}return 0;} 3306 3307 这俩题是一个题，一个带修改，一个不带修改，，这里以3306为例，链上的分类讨论比上一道题还蛋疼。
在x链上，用新max和原min更新左边的差；在y链，用原max和新min更新右边的差。code（附一坨调试信息）：#include<iostream>#include<cstdio>#include<cstring>#define inf 2100000000#define mid (l+r)/2#define lch i<<1,l,mid#define rch i<<1|1,mid+1,rusing namespace std;struct hp{int top,fat,size,wson,dep;}tree[200001];struct hq{int maxn,minn,cl/*左买右卖*/,cr/*右买左卖*/;}seg[800001],ans;struct ht{int u,v;}a[400001];int point[200001],next[800001];int val[200001],plc[200001],f[200001];int n,m,totw=0,e=0;void add(int x,int y){e++; a[e].u=x; a[e].v=y; next[e]=point[x]; point[x]=e;e++; a[e].u=y; a[e].v=x; next[e]=point[y]; point[y]=e;}void build_tree(int last,int x,int depth){int i;tree[x].fat=last;tree[x].dep=depth;tree[x].size=1;tree[x].wson=0;for (i=point[x];i;i=next[i]) if (a[i].v!=last){build_tree(x,a[i].v,depth+1);tree[x].size+=tree[a[i].v].size;if (tree[tree[x].wson].size<tree[a[i].v].size)tree[x].wson=a[i].v;}}void build_seg(int now,int tp){int i;tree[now].top=tp;plc[now]=++totw; f[totw]=now;if (tree[now].wson!=0) build_seg(tree[now].wson,tp);for (i=point[now];i;i=next[i]) if (a[i].v!=tree[now].wson&&a[i].v!=tree[now].fat)build_seg(a[i].v,a[i].v);}void updata(int i){seg[i].maxn=max(seg[i<<1].maxn,seg[i<<1|1].maxn);seg[i].minn=min(seg[i<<1].minn,seg[i<<1|1].minn);seg[i].cl=max(seg[i<<1].cl,max(seg[i<<1|1].cl,seg[i<<1|1].maxn-seg[i<<1].minn));seg[i].cr=max(seg[i<<1].cr,max(seg[i<<1|1].cr,seg[i<<1].maxn-seg[i<<1|1].minn));}void build(int i,int l,int r){if (l==r) {seg[i].maxn=seg[i].minn=val[f[l]];seg[i].cl=seg[i].cr=0;return; }build(lch); build(rch);updata(i);}void insert(int i,int l,int r,int x,int a){if (l==x&&l==r) {seg[i].maxn=seg[i].minn=a; seg[i].cl=seg[i].cr=0;return; }if (x<=mid) insert(lch,x,a);else insert(rch,x,a);updata(i);}hq query_seg(int i,int l,int r,int x,int y){hq t,tl,tr;if (y<l||x>r) return (hq){-1,inf,-1,-1};if (x<=l&&y>=r) {/*cout<<i<<" "<<seg[i].cl<<endl;*/return seg[i];}tl=query_seg(lch,x,y); tr=query_seg(rch,x,y);t.maxn=max(tl.maxn,tr.maxn); t.minn=min(tl.minn,tr.minn);t.cl=max(tl.cl,max(tr.cl,tr.maxn-tl.minn));t.cr=max(tl.cr,max(tr.cr,tl.maxn-tr.minn));/*cout<<i<<' '<<t.cr<<' '<<tl.cl<<' '<<tr.cl<<' '<<tl.minn<<' '<<tr.maxn<<' '<<l<<" "<<r<<endl;*/return t;}void query(int x,int y){int f1=tree[x].top,f2=tree[y].top;int lfmax=-inf,rtmin=inf,lfmin=inf,rtmax=-inf,lfc=-inf,rtc=-inf,ansi;while (f1!=f2) {if (tree[f1].dep>tree[f2].dep){ans=query_seg(1,1,n,plc[f1],plc[x]);//cout<<'x'<<':'<<endl;//cout<<plc[f1]<<' '<<plc[x]<<endl;lfc=max(lfc,ans.cr);lfmax=max(lfmax,ans.maxn); lfc=max(lfc,ans.maxn-lfmin);lfmin=min(lfmin,ans.minn);//cout<<lfc<<' '<<lfmax<<' '<<lfmin<<endl<<"————————"<<endl;x=tree[f1].fat; f1=tree[x].top;}else{ans=query_seg(1,1,n,plc[f2],plc[y]);//cout<<'y'<<':'<<endl;//cout<<plc[f2]<<' '<<plc[y]<<endl;rtc=max(rtc,ans.cl);rtmin=min(rtmin,ans.minn); rtc=max(rtc,rtmax-ans.minn);rtmax=max(rtmax,ans.maxn);//cout<<rtc<<' '<<rtmax<<' '<<rtmin<<endl<<"————————"<<endl;y=tree[f2].fat; f2=tree[y].top;} }if (tree[x].dep>tree[y].dep) {ans=query_seg(1,1,n,plc[y],plc[x]);//cout<<'x'<<':'<<endl;//cout<<plc[f1]<<' '<<plc[x]<<endl;lfc=max(lfc,ans.cr); lfmax=max(lfmax,ans.maxn); lfc=max(lfc,ans.maxn-lfmin);lfmin=min(lfmin,ans.minn);//cout<<lfc<<' '<<lfmax<<' '<<lfmin<<endl<<"————————"<<endl; }else {ans=query_seg(1,1,n,plc[x],plc[y]);//cout<<'y'<<':'<<endl;//cout<<plc[x]<<' '<<plc[y]<<endl;rtc=max(rtc,ans.cl); rtmin=min(rtmin,ans.minn); rtc=max(rtc,rtmax-ans.minn);rtmax=max(rtmax,ans.maxn); //cout<<rtc<<' '<<rtmax<<' '<<rtmin<<endl<<"————————"<<endl; }ansi=max(lfc,max(rtc,rtmax-lfmin));printf("%d\n",ansi); }int main(){int i,x,y,opt;scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&val[i]);for (i=1;i<=n-1;++i) {scanf("%d%d",&x,&y);add(x,y); }build_tree(0,1,0);build_seg(1,1);build(1,1,n);scanf("%d",&m);for (i=1;i<=m;++i) {scanf("%d%d%d",&opt,&x,&y);if (opt==0)insert(1,1,n,plc[x],y);if (opt==1)query(x,y); }}
不敢接受失败的人，往往是那些追求完美的人，
