Qtree3题解(树链剖分(伪)+线段树+set)

外话:最近洛谷加了好多好题啊...原题入口 这题好像是SPOJ的题,挺不错的。看没有题解还是来一篇...

题意

很易懂吧。。

题解

我的做法十分的暴力:树链剖分(伪)+线段树+ std :: set ...

首先,我们可以考虑每次修改一个点的颜色的影响。

易知,翻转一个点颜色,只会对于他的子树产生影响,对于别的点就毫无意义了。

然后,只要学过一点树链剖分的就知道,我们可以将整棵树按它的\(dfs\)序进行标号,

每个点的序号就是\(dfn\),

然后记下它的子树大小\(size\),然后对于每个点\(u\)所在的子树区间就是\([dfn[u], dfn[u]+size[u]-1]\)。

所以每次操作的时候,只要对于那一段区间进行修改就行了。

然后我们要修改和查询什么呢?不就是查询包含这个点,且深度最小的黑点吗?(需要把\(1\)作为根)

所以,我们每次记下一个区间中,包含这个点的所有黑色标号以及他们的深度,用\(pair\)记录一下(因为这个可以

自动按照第一关键字排序),再用\(set\)维护一下区间最值就行了。

每次更新的时候只要在\(set\)里面\(insert\)和\(erase\)。

查询就是从根节点一直向下跑,不断取一个深度更小的\(ans\)。

具体有些实现在程序中会体现的……

总时间复杂度\(O(q \log \ n \log q)\) 空间复杂度也是\(O(q \log \ n \log \ q)\)。(所以说很暴力嘛……)

代码

#include <bits/stdc++.h>
#define For(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define Fordown(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std; bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;} inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
return x * fh;
} void File() {
#ifdef zjp_shadow
freopen ("P4116.in", "r", stdin);
freopen ("P4116.out", "w", stdout);
#endif
} const int N = 1e5 + 1e3, M = N << 1;
int n, q;
int sz[N], dfn[N], dep[N]; int to[M], Next[M], Head[N], e = 0; void add(int u, int v) {
to[++e] = v;
Next[e] = Head[u];
Head[u] = e;
} void Dfs(int u, int fa) {
static int clk = 0;
sz[u] = 1;
dfn[u] = ++ clk;
dep[u] = dep[fa] + 1;
for (register int i = Head[u]; i; i = Next[i]) {
register int v = to[i];
if (v == fa) continue ;
Dfs(v, u); sz[u] += sz[v];
}
}//就是树链剖分的第一个dfs,求出size,dep,dfn typedef pair<int, int> PII;
#define mp make_pair
#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r
set<PII> S[N << 2]; bool col[N];//因为不知道是变啥颜色,所以要记一下原来的颜色
bool uopt; int ul, ur; PII uv;
void Update(int o, int l, int r) {
if (ul <= l && r <= ur) {
if (uopt) S[o].erase(uv);
else S[o].insert(uv);
//erase可以直接调用那个值.
return ;
}
int mid = (l + r) >> 1;
if (ul <= mid) Update(lson);
if (ur > mid) Update(rson);
} PII ans; int up;
void Query(int o, int l, int r) {
if ((bool)S[o].size() )
ans = min(ans, *S[o].begin() );
//begin就是这个set中最小的那一个,即这里面深度最小的那个点
if (l == r) return ;
int mid = (l + r) >> 1;
if (up <= mid) Query(lson);
else Query(rson);
} const int inf = 0x3f3f3f3f; int main () {
n = read(); q = read();
For (i, 1, n - 1) {
int u, v;
scanf ("%d%d", &u, &v);
//int u = read(), v = read();
add(u, v); add(v, u);
}
Dfs(1, 0); For (i, 1, q) {
int opt, pos;
scanf ("%d%d", &opt, &pos);
//int opt = read(), pos = read();
if (opt == 0) {
uopt = col[pos];
col[pos] ^= true;
ul = dfn[pos];
ur = dfn[pos] + sz[pos] - 1;
uv = mp(dep[pos], pos);
Update(1, 1, n);
} else {
ans = mp(inf, inf);
up = dfn[pos];
Query(1, 1, n);
printf ("%d\n", ans.second == inf ? -1 : ans.second);
}
}
//cerr << clock() << endl;
return 0;
}

后记:看到很多dalao都是用啥 主席树,倍增,和不用\(set\)的线段树做过去的。跑得都比我快,希望后面有人能讲一讲QAQ。

上一篇:Android调试错误-No resource identifier found for attribute 'showAsAction'


下一篇:chown 命令