列表

详情

NC50486. 软件包管理器

描述

Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的Homebrew都是优秀的软件包管理器。
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有个软件包，其中A_1依赖A_2，A_2依赖A_3，A_3依赖A_4，……，依赖A_m，而A_m依赖A_1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入描述

输入文件的第1行包含1个正整数n，表示软件包的总数。软件包从0开始编号。
随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示号软件包依赖的软件包的编号。
接下来一行包含一个正整数q，表示询问的总数。
之后q行，每行一个询问。询问分为两种：
install x：表示安装软件包x
uninstall x：表示卸载软件包x
你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出描述

输出文件包括q行。输出文件的第i行输出一个整数，为第i步操作中改变安装状态的软件包数。

示例1

输入: 

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

输出: 

3
1
3
2
3

说明:

一开始所有的软件包都处于未安装状态。
安装5号软件包，需要安装0,1,5三个软件包。
之后安装6号软件包，只需要安装6号软件包。此时安装了0,1,5,6四个软件包。
卸载1号软件包需要卸载1,5,6三个软件包。此时只有0号软件包还处于安装状态。
之后安装4号软件包，需要安装1,4两个软件包。此时0,1,4处在安装状态。
最后，卸载0号软件包会卸载所有的软件包。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

Java 解法, 执行用时: 1838ms, 内存消耗: 48136K, 提交时间: 2021-09-20 16:13:49 

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String args[]){
       new Main().solve();
    }
    Scanner in;
    PrintWriter out;
    public void solve(){
        in = new Scanner(System.in);
        out = new PrintWriter(System.out);
        go();
    }


    long s[];
    long mx[];
    long f[];

    void build(int id,int left,int right){
        if(left==right){
            s[id] = f[left];
            mx[id] = -1;
            return;
        }
        int mid = (left+right)/2;
        build(id*2,left,mid);
        build(id*2+1,mid+1,right);
        s[id] = s[id*2] + s[id*2+1];

    }

    long qry(int id,int left,int right,int l,int r){
        if(left>=l&&right<=r){
            return s[id];
        }else if(left>r||right<l){
            return 0;
        }
        int mid = (left+right)/2;
        if(mx[id]!=-1){
            mx[id*2] = mx[id];
            mx[id*2+1] = mx[id];
            s[id*2] = mx[id]*(mid-left+1);
            s[id*2+1] = mx[id]*(right-(mid+1)+1);
            mx[id] = -1;
        }

        long v1 = qry(id*2,left,mid,l,r);
        long v2 = qry(id*2+1,mid+1,right,l,r);
        s[id] = s[id*2] + s[id*2+1];
        return v1+v2;
    }

//    void update(int id,int left,int right,int l,long val){
//        if(left>l||right<l){
//            return;
//        }else if(left==right){
//            s[id] += val;
//            return;
//        }
//        int mid = (left+right)/2;
//        if(mx[id]!=0){
//            mx[id*2] += mx[id];
//            mx[id*2+1] += mx[id];
//
//            s[id*2] += mx[id]*(mid-left+1);
//            s[id*2+1] += mx[id]*(right-(mid+1)+1);
//
//
//            mx[id] = 0;
//        }
//
//        update(id*2,left,mid,l,val);
//        update(id*2+1,mid+1,right,l,val);
//        s[id] = s[id*2] + s[id*2+1];
//
//    }

    void update(int id,int left,int right,int l,int r,long val){
        if(left>r||right<l){
            return;
        }else if(left>=l&&right<=r){
            mx[id]  = val;
            s[id] = (right-left+1)*val;
            return;
        }
        int mid = (left+right)/2;
        if(mx[id]!=-1){
            mx[id*2] = mx[id];
            mx[id*2+1] = mx[id];
            s[id*2] = mx[id]*(mid-left+1);
            s[id*2+1] = mx[id]*(right-(mid+1)+1);
            mx[id] = -1;
        }

        update(id*2,left,mid,l,r,val);
        update(id*2+1,mid+1,right,l,r,val);
        s[id] = s[id*2] + s[id*2+1];

    }



    int h[],ne[],to[],wt[];
    int ct = 0;
    void add(int u,int v){
        to[ct] = v;
        ne[ct] = h[u];
        h[u] = ct++;
    }
    int n;
    void go(){
        n = in.nextInt();

        h = new int[n];
        Arrays.fill(h,-1);
        ne = new int[2*(n-1)];
        to = new int[2*(n-1)];
        wt = new int[n];

        fa = new int[n];
        dep = new int[n];
        top = new int[n];
        son = new int[n];
        sz = new int[n];
        Arrays.fill(sz,1);
        dfn = new int[n];
        pt = new int[n];
        gpt = new int[n];
        stk = new int[n];

//        for(int i= 0;i<n;++i){
//            wt[i] = in.nextInt();
//        }


        for(int i=1;i<=n-1;++i){
        //    int u = in.nextInt()-1;
            int u = i;
            int v = in.nextInt();
            add(u,v);
            add(v,u);
        }
        int q = in.nextInt();



    //    dfs1(0);
    //    dfs2(0);
        treeLink(0);
        f = new long[n];
//        for(int i=0;i<n;++i){
//            f[i] = wt[pt[i]];
//        }
        s = new long[n*4];
        mx = new long[n*4];
        build(1,0,n-1);

        for(int i=0;i<q;++i){
            String c = in.next();

            if("install".equals(c)){
                int uu = in.nextInt();
                int u  = uu;
                long r = 0;
                int tot = dep[u]+1;
                while(top[u]!=0){
                    long p = qry(1,0,n-1,dfn[top[u]],dfn[u]);
                    r+= p;
                    u = fa[top[u]];
                }

                long p = qry(1,0,n-1,dfn[0],dfn[u]);
                r += p;

                out.println(tot-r);

                u  = uu;
                while(top[u]!=0){
                    update(1,0,n-1,dfn[top[u]],dfn[u],1);
                    u = fa[top[u]];
                }

                update(1,0,n-1,dfn[0],dfn[u],1);

            }else{
                int u = in.nextInt();
                //int tot = sz[u];
                long r = qry(1,0,n-1,dfn[u], dfn[u]+sz[u]-1);
                out.println(r);

                update(1,0,n-1,dfn[u], dfn[u]+sz[u]-1, 0);

            }
        }
        out.close();

    }

    int fa[],dep[],top[],son[],sz[],dfn[],pt[],gpt[],stk[];
    void dfs1(int rt){
        sz[rt] = 1;
        for(int i=h[rt];i!=-1;i=ne[i]){
            int v = to[i];
            if(v==fa[rt]) continue;
            fa[v] = rt;
            dep[v] = dep[rt] + 1;
            dfs1(v);
            sz[rt] += sz[v];
            if(son[rt]==0||sz[son[rt]]<sz[v]){
                son[rt] = v;
            }
        }
    }
    int id = 0;
    void dfs2(int rt){
        dfn[rt] = id;
        pt[id++] = rt;
        if(son[rt]!=0){
            top[son[rt]] = top[rt];
            dfs2(son[rt]);
        }
        for(int i=h[rt];i!=-1;i=ne[i]){
            int v = to[i];
            if(v==fa[rt]||v==son[rt]) continue;
            top[v] = v;
            dfs2(v);
        }
    }

    public void treeLink(int ort){
        int p = 0;
        stk[p++] = ort;
        int clock = 0;
        int rt = -1;
        while(p>0) {
            rt = stk[--p];
            gpt[clock++] = rt;
            for (int i = h[rt]; i != -1; i = ne[i]) {
                int v = to[i];
                if (fa[rt] == v) continue;
                fa[v] = rt;
                dep[v] = dep[rt] + 1;
                stk[p++] = v;
            }
        }
        for(int i=n-1;i>0;--i){
            int cur = gpt[i];
            int fat = fa[cur];
            sz[fat] += sz[cur];
            if (son[fat]== 0 || sz[cur] > sz[son[fat]]) {
                son[fat] = cur;
            }
        }
        for (int i = 1; i < n; i++) top[gpt[i]] = gpt[i] == son[fa[gpt[i]]] ? top[fa[gpt[i]]] : gpt[i];
        p = 0;
        stk[p++] = ort;
        while(p>0) {
            rt = stk[--p];
            dfn[rt] = id;
            pt[id++] = rt;
            for (int i = h[rt]; i != -1; i = ne[i]) {
                int v = to[i];
                if (fa[rt] == v || v == son[rt]) continue;
                stk[p++] = v;
            }
            if(son[rt]!=0) {
                stk[p++] = son[rt];
            }
        }


    }


}

C++14(g++5.4) 解法, 执行用时: 667ms, 内存消耗: 12012K, 提交时间: 2020-01-28 17:38:19 

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+1;
int N;
vector<int> G[MAXN];
int fa[MAXN];
int siz[MAXN];
int dep[MAXN];
int top[MAXN];
int son[MAXN];
int dfn[MAXN];
int dfe[MAXN];
int rnk[MAXN];
int clk;
void dfs1(int s, int f) {
  // cout << s << " " << f << endl;
  if (f!=-1) dep[s] = dep[f]+1;
  siz[s] = 1;
  fa[s] = f;
  for (auto t: G[s]) if (t != f) {
    dfs1(t, s);
    siz[s] += siz[t];
    if (son[s] == -1 || siz[son[s]] < siz[t]) son[s] = t;
  }
}
void dfs2(int s, int f, int tp) {
  top[s] = tp;
  dfn[s] = ++clk;
  rnk[clk] = s;
  if (son[s] != -1) dfs2(son[s], s, tp);
  for (auto t:G[s]) if (t != f && t != son[s]) dfs2(t, s, t);
  dfe[s] = clk; 
}
int sum[MAXN*4];
bool is_delay[MAXN*4];
int delay[MAXN*4];
void change(int o, int l, int r, int L, int R, int v);
void push_down(int o, int l, int m, int r) {
  if (!is_delay[o]) return;
  is_delay[o] = false;
  change(o*2, l, m, l, m, delay[o]);
  change(o*2+1, m+1, r, m+1,r, delay[o]);
}
void change(int o, int l, int r, int L, int R, int v) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) {
    sum[o] = v * (r - l + 1);
    is_delay[o] = true;
    delay[o] = v;
    return;
  }
  int m = (l+r)/2;
  push_down(o, l, m, r);
  change(o*2, l, m, L, R, v);
  change(o*2+1, m+1, r, L, R, v);
  sum[o] = sum[o*2] + sum[o*2+1];
}
int query(int o, int l, int r, int L, int R) {
  if (R < l || r < L) return 0;
  if (L <= l && r <= R) return sum[o];
  int m = (l+r)/2;
  push_down(o, l, m, r);
  return query(o*2, l, m, L, R) + query(o*2+1, m+1, r, L, R);
}
int main() {
  cin >> N;
  for (int i = 1; i < N; i++) {
    int u; cin >> u;
    G[u].push_back(i);
  }
  memset(son, -1, sizeof(son));
  dfs1(0, -1);
  dfs2(0, -1, 0);
  // cout << "init done: " << clk << endl;
  int M; cin >> M;
  while (M--) {
    string op; int x; cin >> op >> x;
    if (op == "install") {
      int pre = query(1, 1, clk, 1, clk);
      while (x != -1) {
        change(1, 1, clk, dfn[top[x]], dfn[x], 1);
        x = fa[top[x]];
      }
      int pos = query(1, 1, clk, 1, clk);
      cout << pos - pre << endl;
    } else {
      int pre = query(1, 1, clk, 1, clk);
      change(1, 1, clk, dfn[x], dfe[x], 0);
      int pos = query(1, 1, clk, 1, clk);
      cout << pre - pos << endl;
    }
  }
}

C++11(clang++ 3.9) 解法, 执行用时: 354ms, 内存消耗: 11244K, 提交时间: 2020-05-30 22:09:04 

#include<bits/stdc++.h>
using namespace std;
const int NN=100004;
int tim,dep[NN],dfn[NN],tp[NN],fa[NN],sz[NN],h[NN],s[NN<<2],tg[NN<<2];
vector<int> g[NN];
void dfs1(int x)
{
	dep[x]=dep[fa[x]]+1;
	sz[x]=1;
	for(int i=0,y;i<g[x].size();i++)
	{
		fa[y=g[x][i]]=x;
		dfs1(y);
		sz[x]+=sz[y];
		h[x]=sz[y]>sz[h[x]]?y:h[x];
	}
 } 
 void dfs2(int x)
 {
 	dfn[x]=++tim;
 	if(h[x])
 	{
 		tp[h[x]]=tp[x];
 		dfs2(h[x]);
	 }
	 for(int i=0;i<g[x].size();i++)
	 if(g[x][i]!=h[x])
	 {
	 	tp[g[x][i]]=g[x][i];
	 	dfs2(g[x][i]);
	 }
 }
 void segtree(int x,int l,int r,int L,int R,int v)
 {
 	if(L<=l&&r<=R)
 	{
 		s[x]=v?r-l+1:0;
 		tg[x]=v;
 		return;
	 }
	 int mid=l+r>>1;
	 if(~tg[x])
	 {
	 	tg[x<<1]=tg[x<<1|1]=tg[x];
	 	s[x<<1]=tg[x]?mid-l+1:0;
	 	s[x<<1|1]=tg[x]?r-mid:0;
	 	tg[x]=-1;
	 }
	 if(L<=mid)
	 segtree(x<<1,l,mid,L,R,v);
	 if(R>mid)
	 segtree(x<<1|1,mid+1,r,L,R,v);
	 s[x]=s[x<<1]+s[x<<1|1];
 }
 int main()
 {
 	ios::sync_with_stdio(false),cin.tie(0);
 	int n;
 	cin>>n;
 	for(int i=2;i<=n;i++)
 	{
 		int u;
 		cin>>u;
 		u++;
 		g[u].push_back(i);
	 }
	 tp[1]=1;
	 dfs1(1);
	 dfs2(1);
	 memset(tg,-1,sizeof(tg));
	 int t;
	 cin>>t;
	 while(t--)
	 {
	 	char opt[15];
	 	int x,st;
	 	cin>>opt>>x;
	 	x++;
	 	st=s[1];
	 	if(opt[0]=='i')
	 	for(;x;x=fa[tp[x]])
	 	segtree(1,1,n,dfn[tp[x]],dfn[x],1);
	 	else
	 	segtree(1,1,n,dfn[x],dfn[x]+sz[x]-1,0);
	 	cout<<abs(st-s[1])<<endl;
	 }
	 return 0;
 }

上一题

© 2024 nowcoder.com