制作网站学什么,新浪云 wordpress,厦门市同安区建设工程质量安全监督站网站,关键词做网站标题是什么意思P2146 [NOI2015] 软件包管理器
题意#xff1a;
如果软件包 a 依赖软件包 b#xff0c;那么安装软件包 a 以前#xff0c;必须先安装软件包 b。同时#xff0c;如果想要卸载软件包 b#xff0c;则必须卸载软件包 a。 软件包之间存在依赖关系#xff0c;除了0号软件包以…P2146 [NOI2015] 软件包管理器
题意
如果软件包 a 依赖软件包 b那么安装软件包 a 以前必须先安装软件包 b。同时如果想要卸载软件包 b则必须卸载软件包 a。 软件包之间存在依赖关系除了0号软件包以外其他软件包都会依赖一个且仅一个软件包。不会存在环的情况 现在对某个软件包进行安装和卸载问这个操作实际上会改变多少个软件包的安装状态
题解
本质就两个操作安装是询问节点x到根节点的操作卸载是查询x的子树的操作。但是题目中问的是每一步操作会改变多少状态所以我们需要记录上一次的状态然后操作完后得到现在的状态差的绝对值就是本次操作的答案
代码
#includebits/stdc.h
using namespace std;
#define INF 0x3f3f3f3f
#define full(a,b) memset(a,b,sizeof a)
#define N 100005
int n,q;
int head[N],ecnt,nxt[N],to[N];
int dad[N],son[N],dep[N],size[N];
int top[N],id[N],rev[N];
int last,s[4*N],lazy[4*N];
void init()//初始化
{full(head,-1);full(lazy,-1);
}
int read()//快读
{int x0,f1;char chgetchar();while(ch0||ch9) fch-?-1:1,chgetchar();while(ch0ch9) x10*xch-0,chgetchar();return x*f;
}
void add(int u,int v)//增加结点
{to[ecnt]v;nxt[ecnt]head[u];head[u]ecnt;
}
void pre(int u,int fa)//求深度子结点等
{dep[u]dep[fa]1;dad[u]fa;size[u]1;for(int ihead[u]; i!-1; inxt[i]){int vto[i];if(vfa) continue;pre(v,u);size[u]size[v];if(size[v]size[son[u]]) son[u]v;}
}
void dfsx(int u)//求链
{int vson[u];if(v){id[v]id[0];rev[id[0]]v;top[v]top[u];dfsx(v);}for(int ihead[u]; i!-1; inxt[i]){vto[i];if(top[v]) continue;id[v]id[0];rev[id[0]]v;top[v]v;dfsx(v);}
}
void pushdown(int k,int l,int r)//传递lazy标记
{if(lazy[k]-1) return;int mid(lr)1;lazy[2*k]lazy[2*k1]lazy[k];s[2*k](mid-l1)*lazy[k];s[2*k1](r-mid)*lazy[k];lazy[k]-1;
}
void update(int k,int l,int r,int x,int y,int v)//区间修改模板
{if(xr||yl) return;if(xlry){s[k]v*(r-l1);lazy[k]v;return;}int mid(lr)1;pushdown(k,l,r);update(k*2,l,mid,x,y,v);update(k*21,mid1,r,x,y,v);s[k]s[2*k]s[2*k1];
}
void query(int u,int v)//询问u-v的路径
{int futop[u],fvtop[v];while(fu!fv){if(dep[fu]dep[fv]) swap(u,v),swap(fu,fv);update(1,1,n,id[fu],id[u],1);udad[fu];futop[u];}if(dep[u]dep[v]) swap(u,v);update(1,1,n,id[u],id[v],1);
}
int main()
{init();nread();for(int i2; in; i){int xread()1;//下标从1开始 add(x,i);}pre(1,0);id[1]id[0];rev[1]1;top[1]1;dfsx(1);///造链 qread();for(int i1; iq; i){char flag[15];scanf(\n%s,flag);int xread()1;//下标从1开始 if(flag[0]i) query(1,x);//询问x到根节点 else update(1,1,n,id[x],id[x]size[x]-1,0);//删除子树 printf(%d\n,abs(last-s[1]));//输出差的绝对值 lasts[1];//更新结点数 }return 0;
}
重温一遍每次修改完值与上一次进行比较
#includecstdio
#includecstring
#includealgorithm
const int maxn200005;
int n,k0,x,head[maxn],q,deep[maxn],father[maxn],size[maxn];
int tid[maxn],top[maxn],son[maxn],tidnum0,pos[maxn];char s[15];
struct node
{int to,next;
} edge[maxn1];
struct Node
{int left,right,flag,sum;
} tree[maxn2];
void add(int u,int v)
{edge[k].tov;edge[k].nexthead[u];head[u]k;
}
int read()
{int x0;char chgetchar();while(ch48||ch57) chgetchar();while(ch48ch57) xx*10ch-48,chgetchar();return x;
}
void dfs1(int x,int fa,int depth)
{size[x]1;father[x]fa;deep[x]depth;for(int ihead[x];i;iedge[i].next){if(edge[i].tofa) continue;dfs1(edge[i].to,x,depth1);size[x]size[edge[i].to];if(!son[x]||size[edge[i].to]size[son[x]]) son[x]edge[i].to;}
}
void dfs2(int x,int tp)
{tid[x]tidnum;pos[tid[x]]x;top[x]tp;if(!son[x]) return;dfs2(son[x],tp);for(int ihead[x];i;iedge[i].next){if(edge[i].to!son[x]edge[i].to!father[x])dfs2(edge[i].to,edge[i].to);}
}
void build(int id,int l,int r)
{tree[id].leftl;tree[id].rightr;tree[id].sum0;tree[id].flag-1;if(lr) return;int mid(lr)1;build(id1,l,mid);build(id1|1,mid1,r);return;
}
void downdata(int id)
{tree[id1].sum(tree[id1].right-tree[id1].left1)*tree[id].flag;tree[id1|1].sum(tree[id1|1].right-tree[id1|1].left1)*tree[id].flag;tree[id1].flagtree[id1|1].flagtree[id].flag;tree[id].flag-1;
}
int get(int id,int l,int r)
{if(tree[id].rightl||tree[id].leftr) return 0;if(tree[id].rightrtree[id].leftl) return tree[id].sum;if(tree[id].flag!-1) downdata(id);return get(id1,l,r)get(id1|1,l,r);
}
void update(int id,int l,int r,int val)
{if(tree[id].rightl||tree[id].leftr) return;if(tree[id].rightrtree[id].leftl){tree[id].sum(tree[id].right-tree[id].left1)*val;tree[id].flagval;return;}if(tree[id].flag!-1) downdata(id);update(id1,l,r,val);update(id1|1,l,r,val);tree[id].sumtree[id1].sumtree[id1|1].sum;return;
}
void change(int u,int v,int val)
{while(top[u]!top[v]){if(deep[top[u]]deep[top[v]]) std::swap(u,v);update(1,tid[top[u]],tid[u],val);ufather[top[u]];}if(deep[u]deep[v]) std::swap(u,v);update(1,tid[u],tid[v],val);return;
}
int main()
{nread();for(int i2;in;i){xread();x;add(x,i);}dfs1(1,1,1);dfs2(1,1);qread();build(1,1,tidnum);for(int i1;iq;i){scanf(%s,s);xread();x;int t1tree[1].sum;if(s[0]i){change(1,x,1);//1到x权值变成1 int t2tree[1].sum;printf(%d\n,abs(t2-t1));}if(s[0]u){update(1,tid[x],tid[x]size[x]-1,0);//1到x权值变成0 int t2tree[1].sum;printf(%d\n,abs(t1-t2));}}return 0;
}
