为公司建立网站,网站建设和维护公司,wordpress 顶部空白,广州腾虎网络网站建设G-Yu Ling(Ling YueZheng) and Colorful Tree
HOWARLI题解
大致做法就是首先考虑哪些修改可能影响询问#xff0c;当修改点权是询问的倍数时才可能影响询问。于是考虑把他们放在一起。
首先每次枚举每种询问的倍数#xff0c;把这些修改和当前询问放在一起#xff0c;由于…G-Yu Ling(Ling YueZheng) and Colorful Tree
HOWARLI题解
大致做法就是首先考虑哪些修改可能影响询问当修改点权是询问的倍数时才可能影响询问。于是考虑把他们放在一起。
首先每次枚举每种询问的倍数把这些修改和当前询问放在一起由于每次考虑的是该点到根节点路径上的点对于每个点的点权的修改仅仅影响的子树节点的询问。于是将单点修改→\to→子树修改链询问→\to→单点询问。
于是每次修改转化成[dfnu,dfnuszu−1][\text{dfn}_u,\text{dfn}_u\text{sz}_u-1][dfnu,dfnuszu−1]添加一个[x,disu][x,\text{dis}_u][x,disu]即可以表示成插入{id,dfnu→dfnuszu−1,x}disu\{\text{id},\text{dfn}_u \to \text{dfn}_u\text{sz}_u-1,x\} \text{dis}_u{id,dfnu→dfnuszu−1,x}disu
于是询问的问题转化成dfnu\text{dfn}_udfnu处询问[[l,r],max{disu}][[l,r],\max\{\text{dis}_u\}][[l,r],max{disu}]可以表示成询问max{{id,dfnu,l→r}dis}\max\{\{\text{id},\text{dfn}_u,l\to r\}\text{dis}\}max{{id,dfnu,l→r}dis}
现在相当于有三维[id,dfn,val][\text{id},\text{dfn},\text{val}][id,dfn,val]即空间上的一个点点权是dis\text{dis}dis显然可以树套树或者cdq分治。
分析一下就可以知道上述求的maxdis\max \text{dis}maxdis一定是离uuu最近的。 下面代码用cdq分治。不过wtcl还没调出来~~
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N110005;
int h[N],e[2*N],ne[2*N],idx;
ll w[2*N];
void add(int a,int b,ll c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;}int n,m;
struct node1
{int op,u,x;int l,r;
}q[N];
struct node2
{int op,id;int t,l,r;ll x;
}q0[N1];
int dfn[N],timestamp;
ll dis[N];
int sz[N];
void dfs(int u,int fa)
{dfn[u]timestamp;sz[u]1;for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;dis[v]dis[u]w[i];dfs(v,u);sz[u]sz[v];}
}
vectorint V0[N],V1[N];
ll v[N2];
ll ans[N];
void modify(int u,int l,int r,int pos,ll x)
{if(lr) return v[u]x,void();int midlr1;if(posmid) modify(u1,l,mid,pos,x);else modify(u1|1,mid1,r,pos,x);v[u]max(v[u1],v[u1|1]);
}
ll query(int u,int l,int r,int L,int R)
{if(LlrR) return v[u];int midlr1;ll c-1;if(Lmid) cmax(c,query(u1,l,mid,L,R));if(Rmid)cmax(c,query(u1|1,mid1,r,L,R));return c;
}
void solve(int l,int r)
{if(lr) return;int midlr1;solve(l,mid),solve(mid1,r);int il;for(int jmid1;jr;j){while(imidq0[i].tq0[j].t){if(q0[i].op0) modify(1,1,n,q0[i].l,q0[i].x);i;}if(q0[j].op1) ans[q0[j].id]max(ans[q0[j].id],query(1,1,n,q0[j].l,q0[j].r));}while(il) {--i;if(q0[i].op0) modify(1,1,n,q0[i].l,-1);}inplace_merge(q0l,q0mid1,q0r1,[](const node2a,const node2b){return a.tb.t;});
}
int main()
{nrd(),mrd();memset(h,-1,sizeof h);memset(v,-1,sizeof v);memset(ans,-1,sizeof ans);for(int i1;in;i) {int urd(),vrd(),crd();add(u,v,c),add(v,u,c);}for(int i1;im;i){q[i].oprd();q[i].urd();if(q[i].op) {q[i].lrd(),q[i].rrd(),q[i].xrd();V1[q[i].x].push_back(i);}else {q[i].xrd();V0[q[i].x].push_back(i);}}dfs(1,0);int cnt;for(int i1;in;i){if(V1[i].empty()) continue;cnt0;for(int ji;jn;ji){for(int k:V0[j]){int uq[k].u;q0[cnt]{0,k,dfn[u],j,j,dis[u]};q0[cnt]{0,k,dfn[u]sz[u],j,j,-1};}}if(!cnt) continue;for(int k:V1[i]){int uq[k].u,lq[k].l,rq[k].r;q0[cnt]{1,k,dfn[u],l,r};}sort(q01,q01cnt,[](const node2 a,const node2 b){return a.idb.id||a.idb.ida.opb.op;});solve(1,cnt);}for(int i1;im;i){if(q[i].op0) continue;if(ans[i]-1)puts(Impossible!);elseprintf(%lld\n,dis[q[i].u]-ans[i]);}
}上面代码有大问题
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N110005;
int h[N],e[2*N],ne[2*N],idx;
ll w[2*N];
void add(int a,int b,ll c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;}int n,m;
struct node1
{int op,u,x;int l,r;
}q[N];
struct node2
{int op,id;int t,l,r;ll x;
}q0[N1];
int dfn[N],timestamp;
ll dis[N];
int sz[N];
void dfs(int u,int fa)
{dfn[u]timestamp;sz[u]1;for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;dis[v]dis[u]w[i];dfs(v,u);sz[u]sz[v];}
}
vectorint V0[N],V1[N];
ll v[N2];
ll ans[N];
void modify(int u,int l,int r,int pos,ll x)
{if(lr) return v[u]x,void();int midlr1;if(posmid) modify(u1,l,mid,pos,x);else modify(u1|1,mid1,r,pos,x);v[u]max(v[u1],v[u1|1]);
}
ll query(int u,int l,int r,int L,int R)
{if(LlrR) return v[u];int midlr1;ll c-1;if(Lmid) cmax(c,query(u1,l,mid,L,R));if(Rmid)cmax(c,query(u1|1,mid1,r,L,R));return c;
}struct node3
{int id;ll v;node3(){}node3(int id,ll v):id(id),v(v){}bool operator(const node3o)const{return vo.v||vo.vido.id;}
};
multisetnode3 mp[N];
multisetnode3::iterator it;
void solve(int l,int r)
{if(lr) return;int midlr1;solve(l,mid),solve(mid1,r);int il;for(int jmid1;jr;j){while(imidq0[i].tq0[j].t){if(q0[i].op0) {if(q0[i].x0) {itmp[q0[i].r].find(node3(q0[i].t-q0[i].l,-q0[i].x));if(it!mp[q0[i].r].end()) mp[q0[i].r].erase(it);}elsemp[q0[i].r].insert(node3(q0[i].t,q0[i].x));if(mp[q0[i].r].size()) modify(1,1,n,q0[i].r,mp[q0[i].r].begin()-v);elsemodify(1,1,n,q0[i].r,-1);}i;}if(q0[j].op1) ans[q0[j].id]max(ans[q0[j].id],query(1,1,n,q0[j].l,q0[j].r));}while(il) {--i;if(q0[i].op0){modify(1,1,n,q0[i].r,-1);mp[q0[i].r].clear();}}inplace_merge(q0l,q0mid1,q0r1,[](const node2a,const node2b){return a.tb.t;});
}
int main()
{nrd(),mrd();memset(h,-1,sizeof h);memset(v,-1,sizeof v);memset(ans,-1,sizeof ans);for(int i1;in;i) {int urd(),vrd(),crd();add(u,v,c),add(v,u,c);}for(int i1;im;i){q[i].oprd();q[i].urd();if(q[i].op) {q[i].lrd(),q[i].rrd(),q[i].xrd();V1[q[i].x].push_back(i);}else {q[i].xrd();V0[q[i].x].push_back(i);}}dis[1]1;dfs(1,0);int cnt;for(int i1;in;i){if(V1[i].empty()) continue;cnt0;for(int ji;jn;ji){for(int k:V0[j]){int uq[k].u;q0[cnt]{0,k,dfn[u],j,j,dis[u]};q0[cnt]{0,k,dfn[u]sz[u],sz[u],j,-dis[u]};}}for(int k:V1[i]){int uq[k].u,lq[k].l,rq[k].r;q0[cnt]{1,k,dfn[u],l,r};}sort(q01,q01cnt,[](const node2 a,const node2 b){return a.idb.id||a.idb.ida.tb.t;});solve(1,cnt);}for(int i1;im;i){if(q[i].op0) continue;if(ans[i]-1)puts(Impossible!);elseprintf(%lld\n,dis[q[i].u]-ans[i]);}
}调了一天了现在感觉这样写不太行wwwcdq分治必须贡献能够分开计算显然最大值不能贡献累加导致上面写法可能不太行草一种植物一天没了~
