我校是神校，作业竟然选自POJ，难道不知道“珍爱生命 勿刷POJ”么？
所有注明模板题的我都十分傲娇地没有打，于是只打了6道题(其实模板题以前应该打过一部分但懒得找)(不过感觉我模板还是不够溜要找个时间刷一发)。
没注明模板题的都是傻逼题，其实也是模板题。
题目大致按照傻逼程度从大到小排序。
POJ 3264 Balanced Lineup
题意：n个数，m个询问，每次问max[l,r]-min[l,r]。
题解：这道题竟然没标注模板题真是惊讶...
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e4+; int g[maxn][],h[maxn][];
int n,m; void get(){
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<=n;i++)
g[i][j]=min(g[i][j-],g[i+(<<(j-))][j-]),
h[i][j]=max(h[i][j-],h[i+(<<(j-))][j-]);
} int ask(int l,int r){
int k=;
while(<<(k+)<=r-l+) k++;
int Min=min(g[l][k],g[r-(<<k)+][k]);
int Max=max(h[l][k],h[r-(<<k)+][k]);
return Max-Min;
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&h[i][]);
g[i][]=h[i][];
}
get(); int l,r;
for(int i=;i<=m;i++){
scanf("%d%d",&l,&r);
printf("%d\n",ask(l,r));
}
return ;
}
POJ 3368 Frequent values
题意：n个数组成一个不降序列，m个询问，每次问[l,r]出现次数最多的数。
题解：预处理把相同的数变成一块，查询时二分lr所在块，这部分求RMQ，lr不在块内的单独处理。
这种划分块的细节及边界一定要想清了，手一抖就会错。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+; int a[maxn],b[maxn],c[maxn],t[maxn],tot;
int h[maxn][];
int n,m; void clear(){
memset(h,,sizeof(h));
memset(a,,sizeof(a));
memset(b,,sizeof(b));
memset(c,,sizeof(c));
memset(t,,sizeof(t));
tot=;
} void get(){
for(int i=;i<=tot;i++) h[i][]=t[i];
for(int j=;(<<j)<=tot;j++)
for(int i=;i+(<<j)-<=tot;i++)
h[i][j]=max(h[i][j-],h[i+(<<(j-))][j-]);
} int ask(int l,int r){
if(l>r) return ;
int k=;
while(<<(k+)<=r-l+) k++;
return max(h[l][k],h[r-(<<k)+][k]);
} int main(){ while(scanf("%d%d",&n,&m)!=EOF){
if(n==) break;
clear(); for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(i==||a[i]!=a[i-]){
++tot;
b[tot]=i;
t[tot]=;
c[tot-]=i-;
}
else t[tot]++;
}
c[tot]=n;
b[tot+]=n+;
get(); int ll,rr,l,r;
for(int i=;i<=m;i++){
scanf("%d%d",&ll,&rr);
l=lower_bound(b+,b+tot+,ll)-b;
r=upper_bound(c+,c+tot+,rr)-c-;
if(r==l-){
printf("%d\n",rr-ll+);
continue;
}
int ans=max(b[l]-ll,rr-c[r]);
ans=max(ans,ask(l,r));
printf("%d\n",ans);
}
}
}
POJ 2763 Housewife Wind
题意：n个节点的树，两个操作，一询问(u,v)距离，二修改某条边边权。
题解：树上的路径长度，很快反应dist[u]+dist[v]-2*dist[lca]，这个就像前缀和表示序列一样。
修改一条边对单点到跟链的影响很好统计，利用dfs序+树状数组即可。
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+,POW=; int p[maxn][POW],pw[maxn],que[maxn],idx[maxn],l[maxn],r[maxn],dep[maxn];
int e[maxn*],w[maxn*],nxt[maxn*],head[maxn],tot;
ll d[maxn],c[maxn];
int n,m,s,clock; void dfs(int u,ll dist){
++clock;
que[clock]=u;
l[u]=clock;
d[u]=dist;
dep[u]=dep[p[u][]]+; for(int i=;i<POW;i++) p[u][i]=p[p[u][i-]][i-]; for(int i=head[u];i;i=nxt[i]){
int v=e[i];
if(v==p[u][]) continue;
p[v][]=u,pw[v]=w[i];
dfs(v,dist+w[i]);
}
r[u]=clock;
} int LCA(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
if(dep[u]<dep[v]){
int del=dep[v]-dep[u];
for(int i=;i<POW&&del;i++)
if(del&(<<i)) v=p[v][i];
}
if(u==v) return u;
for(int i=POW-;i>=;i--)
if(p[u][i]!=p[v][i]) u=p[u][i],v=p[v][i];
u=p[u][];
return u;
} void add(int x,int w){
for(int i=x;i>;i-=(i&-i)) c[i]+=w;
}
ll sum(int x){
ll ret=;
for(int i=x;i<=n;i+=(i&-i)) ret+=c[i];
return ret;
} void adde(int u,int v,int g){
++tot;
e[tot]=v,w[tot]=g;
nxt[tot]=head[u];
head[u]=tot;
} int main(){
scanf("%d%d%d",&n,&m,&s);
int u,v,g;
for(int i=;i<n;i++){
scanf("%d%d%d",&u,&v,&g);
adde(u,v,g);
adde(v,u,g);
} dfs(,);
for(int i=;i<=n;i++) idx[que[i]]=i; int x,num;
for(int i=;i<=m;i++){
scanf("%d",&x);
if(x==){
scanf("%d",&u);
int lca=LCA(s,u);
ll ans=d[u]+d[s]-*d[lca];
ans+=(sum(idx[u])+sum(idx[s])-*sum(idx[lca]));
printf("%lld\n",ans);
s=u;
}
else{
scanf("%d%d",&num,&g);
u=e[num*-],v=e[num*];
if(p[v][]!=u) swap(u,v);
add(l[v]-,pw[v]-g);
add(r[v],-pw[v]+g);
pw[v]=g;
}
}
return ;
}
POJ 3728 The merchant
题意：n个节点带权的树，m个询问，问从x->y的路径上max-min为多少，且路径上max位置必须在min位置之前。
题解：分治的思想，我们怎么合并左右两段路？①maxmin全在路1；②全在路2；③max在路1，min在路二。
保存四个量up[x],down[x],min[x],max[x]。
分别代表x->p最优解，p->x最优解，x-p路径上最小值，x-p路径上最大值。
当然还是要用到LCA，如果用trajan就在并查集合并时处理，倍增就更好处理了。
tarjan要想清，要注意答案在lca处统计，下次再码一发倍增。
听说其他同学写了180+行，十分好奇写了些什么>.<
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e4+; int up[maxn],down[maxn],Min[maxn],Max[maxn];
int n,m; int heade[maxn],e[maxn*],nxte[maxn*];
void adde(int u,int v,int k){
e[k]=v,nxte[k]=heade[u];
heade[u]=k;
} int headq[maxn],q[maxn*],nxtq[maxn*];
void addq(int u,int v,int k){
q[k]=v,nxtq[k]=headq[u];
headq[u]=k;
} int heada[maxn],a[maxn*],nxta[maxn*],tot;
void adda(int u,int num){
++tot;
a[tot]=num,nxta[tot]=heada[u];
heada[u]=tot;
} int p[maxn],vis[maxn],ans[maxn];
void find(int x){
if(p[x]==x) return;
find(p[x]);
up[x]=max(up[x],max(up[p[x]],Max[p[x]]-Min[x]));
down[x]=max(down[x],max(down[p[x]],Max[x]-Min[p[x]]));
Min[x]=min(Min[x],Min[p[x]]);
Max[x]=max(Max[x],Max[p[x]]);
p[x]=p[p[x]];
} void LCA(int u){
vis[u]=;
for(int i=headq[u];i;i=nxtq[i])
if(vis[q[i]]){
int v=q[i];
find(v);
int lca=p[v];
adda(lca,i);
} for(int i=heade[u];i;i=nxte[i])
if(!vis[e[i]]){
int v=e[i];
LCA(v);
p[v]=u;
} for(int i=heada[u];i;i=nxta[i]){
int k=a[i],x,y;
if(k%==) x=q[k+],y=q[k];
else x=q[k],y=q[k-];
find(x),find(y);
k=(k+)/;
ans[k]=max(up[x],max(down[y],Max[y]-Min[x]));
}
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&Min[i]);
Max[i]=Min[i];
p[i]=i;
} int u,v;
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
adde(u,v,i*-);
adde(v,u,i*);
} scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
addq(u,v,i*-);
addq(v,u,i*);
} LCA();
for(int i=;i<=m;i++)
printf("%d\n",ans[i]); return ;
}
POJ 3417 Network
题意：n个节点的树，加入m条新边，现在删除一条旧边一条新边使得新的到的图不再联通，求方案数。
题解：乍一看没什么思路，画个图就很好想了。
加入(u,v)这条边，会形成一个u-v-lca的环。
考虑每一条旧边，如果所在环个数为0，那么另一条边怎么选都可以，贡献为m；如果为1，那么必须删除使它形成环的新边，贡献为1；如果>1，弃疗，贡献为0；
然后是常用技巧，打标记然后树形dp一遍。
f[u]++; f[v]++; f[lca]-=2;
对于统计边是这样，如果是统计点就是f[lca]--, f[p[lca]]--, 如Bzoj 松鼠的新家。
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=1e5+; int vis[maxn],f[maxn],p[maxn];
int e[maxn*],nxte[maxn*],heade[maxn],tote;
int q[maxn*],nxtq[maxn*],headq[maxn],totq;
int n,m; int find(int x){return p[x]==x?x:p[x]=find(p[x]);} void adde(int u,int v){
tote++;
e[tote]=v;
nxte[tote]=heade[u];
heade[u]=tote;
} void addq(int u,int v){
totq++;
q[totq]=v;
nxtq[totq]=headq[u];
headq[u]=totq;
} void tarjan(int u){
vis[u]=;
for(int i=headq[u];i;i=nxtq[i])
if(vis[q[i]]){
int v=q[i],lca=find(v);
f[u]++,f[v]++;
f[lca]-=;
} for(int i=heade[u];i;i=nxte[i])
if(!vis[e[i]]){
int v=e[i];
tarjan(v);
p[v]=u;
}
} void dfs(int fa,int u){
for(int i=heade[u];i;i=nxte[i]){
int v=e[i];
if(v==fa) continue;
dfs(u,v);
f[u]+=f[v];
}
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) p[i]=i; int u,v;
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
adde(u,v),adde(v,u);
} for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
addq(u,v),addq(v,u);
} tarjan();
dfs(,); long long ans=;
for(int i=;i<=n;i++)
if(f[i]==) ans++;
else if(!f[i]) ans+=m; printf("%lld\n",ans);
return ;
}
POJ 2374 Fence Obstacle Course
题意：不好描述自己看。
题解：不知道这道题和LCA&RMQ有基本关系。
网上题解都是dp+线段树。
不过我觉得不用线段树，单调队列就可以(怎么单调很好想)。
然而WA了，不理解，拿标称对拍，拍了一大堆数据都没问题，不知道为何WA
欢迎大神帮我查查错。
//6.4 再想了一下单调队列在某些情况下的确有问题，所以还是要线段树，不过为什么对拍都能过，我不知道。。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=5e4+; int a[maxn],b[maxn],anxt[maxn],bnxt[maxn];
int aque[maxn],bque[maxn],at,bt;
ll f[maxn][];
int n,s; int main(){
scanf("%d%d",&n,&s);
for(int i=;i<=n;i++)
scanf("%d%d",&a[i],&b[i]); for(int i=;i<=n;i++){
while(at&&a[aque[at]]>=a[i]) at--;
anxt[i]=aque[at];
aque[++at]=i; while(bt&&b[bque[bt]]<=b[i]) bt--;
bnxt[i]=bque[bt];
bque[++bt]=i;
} memset(f,,sizeof(f));
f[n][]=abs(a[n]-s),f[n][]=abs(b[n]-s); for(int i=n;i>=;i--){
f[anxt[i]][]=min(f[anxt[i]][],f[i][]+abs(a[i]-a[anxt[i]]));
f[anxt[i]][]=min(f[anxt[i]][],f[i][]+abs(a[i]-b[anxt[i]]));
f[bnxt[i]][]=min(f[bnxt[i]][],f[i][]+abs(b[i]-a[bnxt[i]]));
f[bnxt[i]][]=min(f[bnxt[i]][],f[i][]+abs(b[i]-b[bnxt[i]]));
} printf("%lld\n",min(f[][],f[][]));
return ;
}
WA Code
那么我们来总结一下。
感觉LCA常做的有，处理树上路径长度做减法，判断路径是否包含；特殊一点，就是要你统计路径信息，这个就要在求的过程中合并时下功夫；常用的技巧是，DFS+树状数组辅助统计，打标记+树形dp统计。
RMQ貌似还没看到什么比较特殊的。。有一道论文题还可以。。二维RMQ？找个时间填掉。。