CSP模拟3 <反思>
t3：不要随便用 map
t4: 代码转移要删全
首先考虑暴力，类似线段树，首先你要先dfs出每个节点子树的左右节点，然后修改查询时要考虑左儿子右边界是否大于查询左边界，右儿子左边界是否小于查询有边界，进行 \(dfs\) \(（46pts）\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2*1e5+5;
int tr[N*4][3];
struct asd{
int l,r,data;
}tree[N*4];
int n,m;
void dfs(int x){
if(x<=n){
tree[x].l=tree[x].r=x;
return;
}
dfs(tr[x][0]),dfs(tr[x][1]);
if(tree[tr[x][0]].l>=tree[tr[x][1]].l){
swap(tr[x][1],tr[x][0]);
}
tree[x].l=tree[tr[x][0]].l;
tree[x].r=tree[tr[x][1]].r;
}
void change(int p,int l,int r,int d){
if(tree[p].l>=l && tree[p].r<=r){
tree[p].data+=(tree[p].r-tree[p].l+1)*d;
return;
}
if(tree[tr[p][0]].r>=l) change(tr[p][0],l,r,d);
if(tree[tr[p][1]].l<=r) change(tr[p][1],l,r,d);
}
int ask(int p,int l,int r){
if(tree[p].l>=l && tree[p].r<=r){
return tree[p].data;
}
int ans=0;
if(tree[tr[p][0]].r>=l) ans+=ask(tr[p][0],l,r);
if(tree[tr[p][1]].l<=r) ans+=ask(tr[p][1],l,r);
return ans;
}
bool flat[N*2];
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<n;i++){
int x,y;
scanf("%lld%lld",&x,&y);
tr[n+i][0]=x,tr[n+i][1]=y;
flat[x]=flat[y]=1;
}
int root;
for(int i=1;i<=n*2-1;i++){
if(flat[i]==0){
root=i;
break;
}
}
dfs(root);
for(int i=1;i<=m;i++){
int op;
scanf("%lld",&op);
if(op==1){
int l,r,d;
scanf("%lld%lld%lld",&l,&r,&d);
change(root,l,r,d);
}
else{
int l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",ask(root,l,r));
}
}
}
定义 isa 表示 a 是否是它父亲的左儿子
定义 ffa 表示 a的真祖先中第一个和 a is 值不同的祖先的兄弟节点
连接 a,ffa ，显然仍能得到一颗以原来根为根的树（以后就说现树）。
如何建：
查询两个点 \(l,r\),求出它们 \(lca\) 以此为界限将其一分为二，先只考虑左边。
首先由左节点出发向右上走到头为 \(u\) ,则 \(u\) 为符合的节点
开个栈，每次先将当前点的左儿子与栈顶元素相连，然后将当前点左儿子压入栈，遍历当前点右子树，再将左儿子弹出栈，再遍历左子树，如此得到。可以在 \(dfs\) 时直接开一个变量表示栈顶，省掉栈。
点击查看代码
void Do(int th,int x){
if(!ch[th][0]) return;
add(x,ch[th][0]);
Do(ch[th][1],ch[th][0]);
Do(ch[th][0],x);
}
void Do1(int th,int x){
if(!ch[th][0]) return;
add(x,ch[th][1]);
Do1(ch[th][0],ch[th][1]);
Do1(ch[th][1],x);
}
Do(root,root);
Do1(root,root);
先对于节点 \(l\) ，我们找到 \(l\) 在原树上一直向右上跳的最远位置（设其为 \(u\)）
那么从 \(u\) 开始在现树上往上跳，发现一定能跳到 \(lca\) 的右儿子,但是右儿子又不会和左边的操作相关,所以跳的时候判停。
考虑三种情况：
1：\(l\) 和 \(r\) 的 \(u\) 深度均比 \(lca\) 小， 则此时需操作的就是 \(lca\) 这个点
2：\(l\) 的 \(u\) 深度比 \(lca\) 小，则左侧操作的应该为 \(lca\) 的左儿子节点。
3：\(r\) 的 \(u\) 深度比 \(lca\) 小，方法与 2 相同。
因此可以用树剖+线段树维护。
线段树维护节点状态之和，可以打延迟标记。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4*1e5+5;
int n,m,root;
int ch[N*2][3];
struct asd{
int l,r,data;
}t[N*2];
struct qwe{
int l,r,data,num,lazy;
}tr[1600010];
int ll[N*2],rr[N*2];
int head[N*2],ver[N*2],nex[N*2],tot=0;
int fa[N*2],size[N*2],son[N*2],top[N*2],d[N*2];
int _fa[N*2],_size[N*2],_son[N*2],_top[N*2],_d[N*2],_id[N*2],_rk[N*2],cnt=0;
void add(int x,int y){
ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}
void dfs(int x){
if(x<=n){
t[x].l=t[x].r=x;
return;
}
dfs(ch[x][0]);
dfs(ch[x][1]);
if(t[ch[x][0]].l>=t[ch[x][1]].l){
swap(ch[x][1],ch[x][0]);
}
t[x].l=t[ch[x][0]].l;
t[x].r=t[ch[x][1]].r;
}
void dfs1(int x){
if(x<=n) return;
rr[ch[x][0]]=rr[x],ll[ch[x][0]]=ch[x][0];
dfs1(ch[x][0]);
ll[ch[x][1]]=ll[x],rr[ch[x][1]]=ch[x][1];
dfs1(ch[x][1]);
}
void dfs_y1(int x,int f){
if(!x) return;
d[x]=d[f]+1;
fa[x]=f;
size[x]=1;
dfs_y1(ch[x][0],x); size[x]+=size[ch[x][0]];
dfs_y1(ch[x][1],x); size[x]+=size[ch[x][1]];
if(size[ch[x][0]]<size[ch[x][1]]) son[x]=ch[x][1];
else son[x]=ch[x][0];
}
void dfs_y2(int x,int tp){
if(!x) return;
top[x]=tp;
if(son[x]) dfs_y2(son[x],tp);
if(ch[x][0]!=son[x]) dfs_y2(ch[x][0],ch[x][0]);
else dfs_y2(ch[x][1],ch[x][1]);
}
int ask_lca(int x,int y){//原树lca
int fx=top[x],fy=top[y];
while(fx!=fy){
if(d[fx]>d[fy]) x=fa[fx],fx=top[x];
else y=fa[fy],fy=top[y];
}
if(d[x]<d[y]) return x;
else return y;
}
void dfs_x1(int x,int f){
_d[x]=_d[_fa[x]]+1;
_size[x]=1;
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
_fa[y]=x;
dfs_x1(y,x);
_size[x]+=_size[y];
if(_size[_son[x]]<_size[y]){
_son[x]=y;
}
}
}
void dfs_x2(int x,int tp){
_id[x]=++cnt;
_rk[cnt]=x;
_top[x]=tp;
if(_son[x]) dfs_x2(_son[x],tp);
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==_fa[x]) continue;
if(y!=_son[x]){
dfs_x2(y,y);
}
}
}
void Do(int th,int x){
if(!ch[th][0]) return;
add(x,ch[th][0]);
Do(ch[th][1],ch[th][0]);
Do(ch[th][0],x);
}
void Do1(int th,int x){
if(!ch[th][0]) return;
add(x,ch[th][1]);
Do1(ch[th][0],ch[th][1]);
Do1(ch[th][1],x);
}
void build(int p,int l,int r){
tr[p].l=l,tr[p].r=r;
if(l==r){
int id=_rk[l];
tr[p].num=(t[id].r-t[id].l+1);
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tr[p].num=tr[p*2].num+tr[p*2+1].num;
}
void pushdown(int p){
if(tr[p].lazy){
tr[p*2].data+=tr[p*2].num*tr[p].lazy;
tr[p*2].lazy+=tr[p].lazy;
tr[p*2+1].data+=tr[p*2+1].num*tr[p].lazy;
tr[p*2+1].lazy+=tr[p].lazy;
tr[p].lazy=0;
}
}
void change(int p,int l,int r,int w){
if(tr[p].l>=l && tr[p].r<=r){
tr[p].data+=tr[p].num*w;
tr[p].lazy+=w;
return;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid) change(p*2,l,r,w);
if(r>mid) change(p*2+1,l,r,w);
tr[p].data=tr[p*2].data+tr[p*2+1].data;
return;
}
int ask(int p,int l,int r){
if(tr[p].l>=l && tr[p].r<=r){
return tr[p].data;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
int ans=0;
if(l<=mid) ans+=ask(p*2,l,r);
if(r>mid) ans+=ask(p*2+1,l,r);
return ans;
}
void chan(int l,int r,int w){
int lca=ask_lca(l,r),ans=0;
l=rr[l],r=ll[r];
if(d[l]<=d[lca] && d[r]<=d[lca]){
change(1,_id[lca],_id[lca],w);
return;
}
if(d[l]<=d[lca]){
l=ch[lca][0];
change(1,_id[l],_id[l],w);
}
else{
int fx=_top[l];
while(_d[fx]>_d[ch[lca][1]]){
change(1,_id[fx],_id[l],w);
l=_fa[fx],fx=_top[l];
}
change(1,_id[ch[lca][1]]+1,_id[l],w);
}
if(d[r]<=d[lca]){
r=ch[lca][1];
change(1,_id[r],_id[r],w);
}
else{
int fx=_top[r];
while(_d[fx]>_d[ch[lca][0]]){
change(1,_id[fx],_id[r],w);
r=_fa[fx],fx=_top[r];
}
change(1,_id[ch[lca][0]]+1,_id[r],w);
}
}
int askk(int l,int r){
int lca=ask_lca(l,r),ans=0;
l=rr[l],r=ll[r];
if(d[l]<=d[lca] && d[r]<=d[lca]){
ans+=ask(1,_id[lca],_id[lca]);
return ans;
}
if(d[l]<=d[lca]){
l=ch[lca][0];
ans+=ask(1,_id[l],_id[l]);
}
else{
int fx=_top[l];
while(_d[fx]>_d[ch[lca][1]]){
ans+=ask(1,_id[fx],_id[l]);
l=_fa[fx],fx=_top[l];
}
ans+=ask(1,_id[ch[lca][1]]+1,_id[l]);
}
if(d[r]<=d[lca]){
r=ch[lca][1];
ans+=ask(1,_id[r],_id[r]);
}
else{
int fx=_top[r];
while(_d[fx]>_d[ch[lca][0]]){
ans+=ask(1,_id[fx],_id[r]);
r=_fa[fx],fx=_top[r];
}
ans+=ask(1,_id[ch[lca][0]]+1,_id[r]);
}
return ans;
}
bool flat[N*2];
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<n;i++){
int x,y;
scanf("%lld%lld",&x,&y);
ch[n+i][0]=x,ch[n+i][1]=y;
flat[x]=flat[y]=1;
}
for(int i=1;i<=n*2-1;i++){
if(flat[i]==0){
root=i;
break;
}
}
dfs(root);
ll[root]=root,rr[root]=root;
dfs1(root);
Do(root,root);
Do1(root,root);
dfs_y1(root,0);
dfs_y2(root,root);
dfs_x1(root,0);
dfs_x2(root,root);
build(1,1,cnt);
for(int i=1;i<=m;i++){
int op;
scanf("%lld",&op);
if(op==1){
int l,r,d;
scanf("%lld%lld%lld",&l,&r,&d);
chan(l,r,d);
}
else{
int l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",askk(l,r));
}
}
}