laekov

BZOJ3626 LCA

比较神奇的一道树的题。


做法是离线。想了好久的在线啊。


把询问拆成0~l-1和0~r。挨个从0开始加点。加点就是把从根到这个点的所有点权+1,询问就是询问这个点到根的点权和。好机智的做法。


代码还比较舒服。dfs+树链剖分+树状数组。

#include <cstdio>

#include <memory.h>

#include <algorithm>


using namespace std;


struct edge {

int t;

edge *next;

};

struct query {

int p, v, n, c;

inline query(int p0 = 0, int v0 = 0, int n0 = 0, int c0 = 0) {

p = p0, v = v0, n = n0, c = c0;

}

};


const int maxn = 50009;

const int mod = 201314;


void btChg(int* t, int p, int v) {

while (p < maxn)

(t[p] += v) %= mod, p += (p & -p);

}


int btQry(int* t, int p) {

int s = 0;

while (p)

(s += t[p]) %= mod, p -= (p & -p);

return s;

}


inline bool cmpQuery(const query& a, const query& b) {

return a. p < b. p;

}


edge *head[maxn], *ep;

query q[maxn * 2];

int n, m, fa[maxn], ans[maxn];

int tc, sz[maxn], fc[maxn], ch[maxn], fs[maxn];

int dfo[maxn], dfb[maxn];

int t[maxn], s[maxn];


inline void addEdge(int u, int v) {

ep-> t = v;

ep-> next = head[u];

head[u] = ep ++;

}


void dfs() {

static int stc[maxn];

int tstc = 1, dfn = 0;

stc[1] = 0;

while (tstc) {

int p = stc[tstc --];

dfo[++ dfn] = p;

dfb[p] = dfn;

for (edge* e = head[p]; e; e = e-> next)

if (!dfb[e-> t])

stc[++ tstc] = e-> t;

}

tc = 0;

for (int i = n; i; -- i) {

int p = dfo[i], x = -1;

sz[p] = 1;

for (edge* e = head[p]; e; e = e-> next)

if (dfb[e-> t] > dfb[p]) {

sz[p] += sz[e-> t];

if (x == -1 || sz[e-> t] > sz[x])

x = e-> t;

}

fs[p] = x;

if (x == -1) {

fc[p] = ++ tc;

ch[fc[p]] = p;

}

else {

fc[p] = fc[x];

ch[fc[p]] = p;

}

}

tstc = 1;

stc[1] = 0;

dfn = 0;

memset(dfb, 0, sizeof(dfb));

while (tstc) {

int p = stc[tstc --];

dfo[++ dfn] = p;

dfb[p] = dfn;

for (edge* e = head[p]; e; e = e-> next)

if (e-> t ^ fs[p])

stc[++ tstc] = e-> t;

if (fs[p] > -1)

stc[++ tstc] = fs[p];

}

}


void segChg(int l, int r, int v) {

btChg(t, l, v);

btChg(s, l, l * v % mod);

btChg(t, r + 1, mod - v);

btChg(s, r + 1, mod - (r + 1) * v % mod);

}


int segQry(int l, int r) {

return ((btQry(t, r) * (r + 1) % mod - btQry(s, r)\

- btQry(t, l - 1) * l % mod + btQry(s, l - 1)) % mod + mod) % mod;

}


void ins(int p) {

while (p ^ -1) {

segChg(dfb[ch[fc[p]]], dfb[p], 1);

p = fa[ch[fc[p]]];

}

}


int qry(int p) {

int s = 0;

while (p ^ -1) {

(s += segQry(dfb[ch[fc[p]]], dfb[p])) %= mod;

p = fa[ch[fc[p]]];

}

return s;

}


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


memset(head, 0, sizeof(head));

ep = new edge[maxn * 2];

scanf("%d%d", &n, &m);

fa[0] = -1;

for (int i = 1; i < n; ++ i) {

scanf("%d", fa + i);

addEdge(fa[i], i);

}

for (int i = 0; i < m; ++ i) {

int l, r, p;

scanf("%d%d%d", &l, &r, &p);

q[i << 1] = query(l - 1, p, i, -1);

q[(i << 1) | 1] = query(r, p, i, 1);

}

sort(q, q + m * 2, cmpQuery);

dfs();

for (int i = 0, j = 0; j < m * 2;) {

for (; i <= q[j]. p; ++ i)

ins(i);

for (; j < m * 2 && q[j]. p == i - 1; ++ j)

ans[q[j]. n] += q[j]. c * qry(q[j]. v);

}

for (int i = 0; i < m; ++ i)

printf("%d\n", (ans[i] % mod + mod) % mod);

}


评论

© laekov | Powered by LOFTER