2020牛客暑期多校训练营(第七场)C A National Pandemic —— 树链剖分(下次不要再忘了初始化了)

This way

题意:

现在有一棵大小为n的树,有m个操作,每次有三种操作:
定义dis(x,y)为从x到y的边数
1 x w 位置x上的权值+w,同时所有位置的权值加上w-dis(x,y)
2 x 将x位置的权值对0取个最小值
3 x 问x位置的权值是多少

题解:

树链剖分忘记初始化son数组了,一直T还找不出原因。还好这次不是ICPC,就当给自己一个教训吧,下次再出现这个问题就,我nm就,我就冷静冷静
那么很明显我们对于1操作是不能每次直接更新所有点的,然后这又是一棵树…那么缩小范围到:主席树,树链剖分,离线dfs。那么三种我都想了一会,最终确定是树链剖分区间更新,区间查询。
不要忘了初始化
对于位置x上加了w,我们都可以看成根(默认根为1)上加了w-dis(x,1)。然后再对1到x的路径上所有边的值+1,这里我将存边变为存儿子节点。但是我们还需要考虑一个距离的问题,那么我用num存当前有几次1操作,由于它的权值是可以小于0的,所以我们就不需要去特殊考虑负权的位置。那么当前点的答案就是val1-dep[x]2020牛客暑期多校训练营(第七场)C A National Pandemic —— 树链剖分(下次不要再忘了初始化了)
假设红点加了w,那么根的权值就是w-3,蓝点的值就是w-3-2.
不要忘了初始化
但是红点到根的路径上的点怎么办,那么我们将这个路径上的所有边权+1,这样子就可以表示距离++了。
那么最终对于红点到根的路径上的每个边权就是+2。
还有2操作,那么我们每次就只需要找
不要忘了初始化
val1+query(1,x)-1ll*(dep[x]-1)*num;
然后再比较这个点上次一2操作时候的值和这个值的大小,我们每次2操作完了之后,如果值变大,就以这个为零点就行了。
不要忘了初始化
最后的答案就是val1+query(1,x)-1ll*(dep[x]-1)*num-ad[x]。
不要忘了初始化
最后这道题就愉悦地结束了,下次出问题的时候记得再仔细检查不要忘了初始化就行了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pa pair<int,int>
namespace Fast_IO { //orz laofu
const int MAXL((1 << 18) + 1); int iof, iotp;
char ioif[MAXL], * ioiS, * ioiT, ioof[MAXL], * iooS = ioof, * iooT = ioof + MAXL - 1, ioc, iost[55];
char Getchar() {
if (ioiS == ioiT) {
ioiS = ioif; ioiT = ioiS + fread(ioif, 1, MAXL, stdin); return (ioiS == ioiT ? EOF : *ioiS++);
}
else return (*ioiS++);
}
void Write() { fwrite(ioof, 1, iooS - ioof, stdout); iooS = ioof; }
void Putchar(char x) { *iooS++ = x; if (iooS == iooT)Write(); }
inline int read() {
int x = 0; for (iof = 1, ioc = Getchar(); ioc<'0' || ioc>'9';)iof = ioc == '-' ? -1 : 1, ioc = Getchar();
for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48); return x * iof;
}
inline long long read_ll() {
long long x = 0; for (iof = 1, ioc = Getchar(); ioc<'0' || ioc>'9';)iof = ioc == '-' ? -1 : 1, ioc = Getchar();
for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48); return x * iof;
}
template <class Int>void Print(Int x, char ch = '\0') {
if (!x)Putchar('0'); if (x < 0)Putchar('-'), x = -x; while (x)iost[++iotp] = x % 10 + '0', x /= 10;
while (iotp)Putchar(iost[iotp--]); if (ch)Putchar(ch);
}
void Getstr(char* s, int& l) {
for (ioc = Getchar(); ioc <'a' || ioc>'z';)ioc = Getchar();
for (l = 0; ioc <= 'z' && ioc >= 'a'; ioc = Getchar())s[l++] = ioc; s[l] = 0;
}
void Putstr(const char* s) { for (int i = 0, n = strlen(s); i < n; ++i)Putchar(s[i]); }
} // namespace Fast_IO
using namespace Fast_IO;
const int N=1e5+5;
const int inf=1e9;
struct node
{
int to,next;
}e[N*2];
int head[N],cnt,tim,fa[N][21],son[N],dep[N],top[N],en[N],siz[N],pos[N];
ll f[N*4],sum[N*4];
int n,m;
inline void add(int x,int y)
{
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
}
inline void dfs1(int u)
{
siz[u]=1;
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa[u][0])
{
fa[v][0]=u;
dep[v]=dep[u]+1;
dfs1(v);
siz[u]+=siz[v];
if (son[u]==0||siz[v]>siz[son[u]])
son[u]=v;
}
}
}
inline void dfs2(int u,int f)
{
tim++;
top[u]=f;
pos[u]=tim;
if (son[u]) dfs2(son[u],f);
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa[u][0]&&v!=son[u])
{
dfs2(v,v);
}
}
en[u]=tim;
}
inline void pushdown(int l,int r,int root)
{
if(!f[root])return ;
int mid=l+r>>1;
sum[root<<1]+=f[root]*(mid-l+1);
sum[root<<1|1]+=f[root]*(r-mid);
f[root<<1]+=f[root];
f[root<<1|1]+=f[root];
f[root]=0;
}
inline void add(int l,int r,int root,int ql,int qr,ll val)
{
if(l>=ql&&r<=qr)
{
sum[root]+=val*(r-l+1);
f[root]+=val;
return ;
}
pushdown(l,r,root);
int mid=l+r>>1;
if(mid>=ql)
add(l,mid,root<<1,ql,qr,val);
if(mid<qr)
add(mid+1,r,root<<1|1,ql,qr,val);
sum[root]=sum[root<<1]+sum[root<<1|1];
}
inline ll ask(int l,int r,int root,int ql,int qr)
{
if(l>=ql&&r<=qr)
return sum[root];
int mid=l+r>>1;
pushdown(l,r,root);
ll ans=0;
if(mid>=ql)
ans=ask(l,mid,root<<1,ql,qr);
if(mid<qr)
ans+=ask(mid+1,r,root<<1|1,ql,qr);
return ans;
}
inline ll query(int x,int y)
{
ll ans=0;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=ask(1,n,1,pos[top[x]],pos[x]);
x=fa[top[x]][0];
}
if (pos[x]>pos[y]) swap(x,y);
ans+=ask(1,n,1,pos[x],pos[y]);
return ans;
}
inline void update(int x,int y,ll val)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
add(1,n,1,pos[top[x]],pos[x],val);
x=fa[top[x]][0];
}
if (pos[x]>pos[y]) swap(x,y);
add(1,n,1,pos[x],pos[y],val);
}
inline void deal(){
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
ll ad[N];
int main()
{
int t;
t=read();
while(t--){
int x,y;
n=read(),m=read();
for(int i=0;i<=n;i++)ad[i]=son[i]=0,head[i]=-1;
memset(sum,0,sizeof(sum)),memset(f,0,sizeof(sum));
tim=cnt=0;
for(int i=1;i<n;++i)
x=read(),y=read(),add(x,y),add(y,x);
dep[1]=1;
dfs1(1),dfs2(1,1);
deal();
int num=0;
ll val1=0,v;
int op,firstson;
while(m--){
op=read(),x=read();
if(op==1){
num++;
y=read();
val1+=y-dep[x]+1;
if(x!=1){
firstson=x;
for(register int i=17;i>=0;--i)
if(dep[fa[firstson][i]]>dep[1])
firstson=fa[firstson][i];
update(x,firstson,2);
}
}
else if(op==2){
v=val1+query(1,x)-1ll*(dep[x]-1)*num;
if(v>ad[x])ad[x]=v;
}
else
printf("%lld\n",val1+query(1,x)-1ll*(dep[x]-1)*num-ad[x]);
}
}
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

2020牛客暑期多校训练营(第七场)C A National Pandemic —— 树链剖分(下次不要再忘了初始化了)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 2020牛客暑期多校训练营(第七场)C A National Pandemic —— 树链剖分(下次不要再忘了初始化了)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏