BZOJ3307 雨天的尾巴

首先考虑序列怎么做。。。

只要把操作差分了,记录在每个点上

然后维护一棵权值线段树,表示每个颜色出现的次数,支持单点修改和查询最大值操作

只要把序列扫一遍就好了,时间复杂度$O(n + m*logZ)$,其中$n$表述序列长度,$m$表示操作次数,$Z$表示颜色集合大小

于是树形的时候,先树链剖分,然后把操作离线,对每一条链都扫一遍就好了,时间复杂度$O(n + m*logn*logZ)$

 /**************************************************************
Problem: 3307
User: rausen
Language: C++
Result: Accepted
Time:5120 ms
Memory:86068 kb
****************************************************************/ #include <cstdio>
#include <algorithm> using namespace std;
const int N = 1e5 + ;
const int Z = 1e9 + ; inline int read(); struct seg {
seg *ls, *rs;
int mx, wmx;
int tag; seg() {} #define Len (1 << 16)
inline void* operator new(size_t) {
static seg *mempool, *c;
if (mempool == c)
mempool = (c = new seg[Len]) + Len;
return c++;
}
#undef Len
inline void operator = (const seg &s) {
mx = s.mx, wmx = s.wmx;
} inline void update() {
if (!ls && !rs) this -> mx = ;
else if (!ls || !rs) *this = (ls ? *ls : *rs);
else if (ls -> mx >= rs -> mx) *this = *ls;
else *this = *rs;
}
inline void clear() {
tag = , mx = ;
}
inline void push() {
if (tag) {
if (ls) ls -> clear();
if (rs) rs -> clear();
tag = ;
}
} #define mid (l + r >> 1)
void modify(int l, int r, int pos, int d) {
if (l == r) {
mx += d, wmx = l;
return;
}
push();
if (pos <= mid) {
if (!ls) ls = new()seg;
ls -> modify(l, mid, pos, d);
} else {
if (!rs) rs = new()seg;
rs -> modify(mid + , r, pos, d);
}
update();
}
#undef mid
} *T; struct edge {
int next, to;
edge(int _n = , int _t = ) : next(_n), to(_t) {}
} e[N << ];
int first[N], tot; struct oper {
int next, z, d;
oper(int _n = , int _z = , int _d = ) : next(_n), z(_z), d(_d) {}
} op[N << ];
int First[N], tot_op; struct tree_node {
int fa, son, top;
int sz, dep;
} tr[N]; int n, m;
int ans[N]; inline void Add_Edges(int x, int y) {
e[++tot] = edge(first[x], y), first[x] = tot;
e[++tot] = edge(first[y], x), first[y] = tot;
} #define y e[x].to
void dfs(int p) {
int x;
tr[p].sz = ;
for (x = first[p]; x; x = e[x].next)
if (y != tr[p].fa) {
tr[y].fa = p, tr[y].dep = tr[p].dep + ;
dfs(y);
tr[p].sz += tr[y].sz;
if (tr[tr[p].son].sz < tr[y].sz) tr[p].son = y;
}
} void DFS(int p) {
int x;
if (!tr[p].son) return;
tr[tr[p].son].top = tr[p].top, DFS(tr[p].son);
for (x = first[p]; x; x = e[x].next)
if (y != tr[p].fa && y != tr[p].son)
tr[y].top = y, DFS(y);
}
#undef y inline void Add_oper(int x, int y, int z) {
y = tr[y].son;
op[++tot_op] = oper(First[x], z, ), First[x] = tot_op;
op[++tot_op] = oper(First[y], z, -), First[y] = tot_op;
} inline void work(int x, int y, int z) {
while (tr[x].top != tr[y].top) {
if (tr[tr[x].top].dep < tr[tr[y].top].dep) swap(x, y);
Add_oper(tr[x].top, x, z);
x = tr[tr[x].top].fa;
}
if (tr[x].dep < tr[y].dep) swap(x, y);
Add_oper(y, x, z);
} void get_ans(int p) {
int x;
for (x = First[p]; x; x = op[x].next)
T -> modify(, Z, op[x].z, op[x].d);
ans[p] = T -> mx == ? : T -> wmx;
if (tr[p].son) get_ans(tr[p].son);
} int main() {
int i, x, y, z;
n = read(), m = read();
for (i = ; i < n; ++i) Add_Edges(read(), read());
dfs();
tr[].top = , DFS();
for (i = ; i <= m; ++i) {
x = read(), y = read(), z = read();
work(x, y, z);
}
T = new()seg;
for (i = ; i <= n; ++i)
if (tr[i].top == i) {
T -> clear();
get_ans(i);
}
for (i = ; i <= n; ++i)
printf("%d\n", ans[i]);
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}

(p.s. 窝比较懒,所以没有把颜色离散化,直接搞了动态开点线段树)

上一篇:创建Maven web项目时 出现 web.xml is missing and is set to true错误 pox.xml编译错误


下一篇:JAVA缓存技术之EhCache(转)