UOJ128 NOI2015 软件包管理器 【树链剖分】

tonyfang posted @ 2016年10月03日 22:04 in NOI with tags c++ OI , 1339 阅读

题目大意:给出一棵树,每个节点代表一个软件包,安装这个软件包要安装他所有祖先,卸载要卸载他的子树,每次操作后问操作了多少个软件包。

【题解】

树链剖分裸题啊。

 

# include <stdio.h>
using namespace std;

const int N = 200010, M = 600010;
int n;
int tot=0, next[M], to[M], head[N];
int dfn[N], dfnlast[N], DFN = 0, sz[N], top[N], son[N];
int dep[N], pos[N], father[N];
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int fa=0) {
	dep[x] = dep[fa] + 1; father[x] = fa; 
	sz[x]=1; son[x]=-1;	
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dfs(to[i], x);
		sz[x] += sz[to[i]];
		if(son[x] == -1 || sz[to[i]] > sz[son[x]])
			son[x] = to[i];
	}
}

inline void dfs2(int x, int tp, int fa=0) {
	dfn[x]=pos[x]=++DFN; top[x]=tp;
	if(son[x] != -1) dfs2(son[x], tp, x);
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa || to[i] == son[x]) continue;
		dfs2(to[i], to[i], x);
	}
	dfnlast[x] = DFN;
}


int w[N<<2], lazy[N<<2];
 
inline void pushdown(int x, int l, int r) {
    if(lazy[x] == -1) return;
    int mid = l+r >> 1;
    w[x<<1] = lazy[x] * (mid - l + 1);
    w[x<<1|1] = lazy[x] * (r - (mid+1) + 1);
    lazy[x<<1] = lazy[x];
    lazy[x<<1|1] = lazy[x];
    lazy[x] = -1;
}
 
inline void change(int x, int l, int r, int L, int R, int delta) {
    if(L <= l && r <= R) {
        w[x] = delta*(r - l + 1);
        lazy[x] = delta;
        return ;
    }
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) change(x<<1|1, mid+1, r, L, R, delta);
    else if(R <= mid) change(x<<1, l, mid, L, R, delta);
    else {
        change(x<<1, l, mid, L, mid, delta);
        change(x<<1|1, mid+1, r, mid+1, R, delta);
    }
    w[x] = w[x<<1] + w[x<<1|1];
}
 
inline int query(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) return w[x];
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) return query(x<<1|1, mid+1, r, L, R);
    else if(R <= mid) return query(x<<1, l, mid, L, R);
    else return query(x<<1, l, mid, L, mid) + query(x<<1|1, mid+1, r, mid+1, R);
}

inline int get(int fr, int to) {
	int ret = 0;
	while(top[fr] != top[to]) {
		ret += query(1, 1, n, pos[top[fr]], pos[fr]);
		change(1, 1, n, pos[top[fr]], pos[fr], 1);
		fr = father[top[fr]];
	}
	if(pos[fr] >= pos[to]) {
		ret += query(1, 1, n, pos[to], pos[fr]);
		change(1, 1, n, pos[to], pos[fr], 1);
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i=2, t; i<=n; ++i) {
		scanf("%d", &t); ++t;
		add(t, i); add(i, t);
	}
	dfs(1); dfs2(1,1);
	int tsz = n<<2;
	for (int i=1; i<=tsz; ++i) lazy[i] = -1;
	int q; scanf("%d", &q);
	while(q--) {
		int x; char str[12];
		scanf("%s%d", str, &x); ++x;
		if(str[0] == 'i') {
			printf("%d\n", dep[x] - get(x, 1));
		} else {
			printf("%d\n", query(1, 1, n, dfn[x], dfnlast[x]));
			change(1, 1, n, dfn[x], dfnlast[x], 0);
		}
	}
	return 0;
}

 

感觉dfs序也能做?

但是线段树好像要维护一些奇奇怪怪的东西

比如只更新符号为负的,而且好像lazy多了就当一个用??

奇怪的东西。。感觉不可写弃坑了。

 

Grade 5 Result Comil 说:
2022年9月06日 22:09

Right now there is a press announcement issued by Education Ministry Bangladesh for PSC Exam Result Date 2022, based on the announcement the PSC Result 2022 will be announced on 30th or 31st December 2022 in case of any early announcement the Grade-5 exam result announced on 24th December 2022 respectively for all education boards and all divisions in the country.According to the previous reports, Grade 5 Result Comilla Board the PSC Result Date 2022 Comilla Board is also last week of December, however, we will update the official result date here after the official announcement by DPE, as per DPE previous five years result from the announcement of this year result will be announced likely on 30th or 31st December 2022.

boardmodelpaper.com 说:
2024年1月12日 22:21

Board Model Papers 2024 provide all states of 6th to 10th text books 2024 Candidates who are Searching for 6th to 10th and 11th to 12th text books and syllabus, sample questions, exam pattern, and Co-Curricular Subject textbooks can refer to this entire article. boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course. Here, we have gathered all subjects of Board textbooks for all Class along with the direct download links.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter