莫队超时 改了半天块的大小没xx用
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
const int N = 2e5+10, M = 4e5+10;
int n, m, len, tot;
int h[N], e[M], nxt[M], idx;
int res[N];
set<int> id;
int dfn[N], rdfn[N], tim;
struct Query{
int id, l, r;
}q[N];
int dep[N], fa[N][20];
int getid(int x)
{
return x / len;
}
void add(int a,int b)
{
e[idx] = b, nxt[idx] = h[a], h[a] = idx ++;
}
bool cmp(Query &a, Query &b)
{
int x = getid(a.l), y = getid(b.l);
if(x != y) return x < y;
if(x % 2) return a.r < b.r;
return a.r > b.r;
}
void dfs(int u,int f)
{
dfn[u] = ++ tim; rdfn[tim] = u;
for(int i = h[u]; ~i; i = nxt[i])
{
int to = e[i];
if(to == f || dfn[to]) continue;
dfs(to, u);
}
}
void bfs(int s)
{
queue<int> q;
memset(dep, 0x3f, sizeof dep);
dep[0] = 0, dep[s] = 1;
q.push(s);
while(q.size())
{
int u = q.front(); q.pop();
for(int i = h[u]; ~i; i = nxt[i])
{
int to = e[i];
if(dep[to] > dep[u] + 1)
{
dep[to] = dep[u] + 1;
q.push(to);
fa[to][0] = u;
for(int k = 1; k < 20; ++ k)
fa[to][k] = fa[fa[to][k - 1]][k - 1];
}
}
}
}
int lca(int a, int b)
{
if(dep[a] < dep[b]) swap(a, b);
for(int k = 19; k >= 0; k --)
if(dep[fa[a][k]] >= dep[b]) a = fa[a][k];
if(a == b) return a;
for(int k = 19; k >= 0; k --)
if(fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
void del(int tree_id)
{
int dfn_id = dfn[tree_id];
if(!dfn_id) return;
if(id.empty())
{
id.insert(dfn_id);
return;
}
auto r = id.upper_bound(dfn_id);
if(r == id.end()) r = id.begin();
auto l = --id.upper_bound(dfn_id);
if(l == id.begin()) l = --id.end();
else l --;
int x = rdfn[*r], y = rdfn[*l], z = rdfn[dfn_id];
tot -= 2 * dep[z] - 2 * dep[lca(x, z)] - 2 * dep[(lca(y, z))] + 2 * dep[lca(x, y)];
id.erase(id.lower_bound(dfn_id));
}
void add(int tree_id)
{
int dfn_id = dfn[tree_id];
if(!dfn_id) return;
if(id.empty())
{
id.insert(dfn_id);
return;
}
auto r = id.upper_bound(dfn_id);
if(r == id.end()) r = id.begin();
auto l = id.upper_bound(dfn_id);
if(l == id.begin()) l = --id.end();
else l --;
int x = rdfn[*r], y = rdfn[*l], z = rdfn[dfn_id];
tot += 2 * dep[z] - 2 * dep[lca(x, z)] - 2 * dep[(lca(y, z))] + 2 * dep[lca(x, y)];
id.insert(dfn_id);
}
void print()
{
auto r = id.upper_bound(2);
if(r == id.end()) r = id.begin();
auto l = id.upper_bound(2);
if(l == id.begin()) l = --id.end();
else l --;
printf("%d %d\n", *r, *l);
}
int dis(int a, int b)
{
int p = lca(a, b);
return dep[a] + dep[b] - 2 * dep[p];
}
int main()
{
// id.insert(0);
// id.insert(1e9);
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
len = sqrt(n * n / m);
for(int i = 0; i < n - 1; ++ i)
{
int a, b; scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
dfs(1, -1);
bfs(1);
for(int i = 0; i < n; ++ i)
{
int l, r; scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q, q + m, cmp);
int i = 1, j = 0;
//print(2);
for(int k = 0; k < m; ++k)
{
int id = q[k].id, l = q[k].l, r = q[k].r;
//printf("%d %d %d\n", id, l, r);
while(i > l) add(i - 1), i --;
while(j < r) add(j + 1), j ++;
while(i < l) del(i), i ++;
while(j > r) del(j), j --;
res[id] = tot / 2;
}
for(int i = 0; i < m; ++ i) printf("%d\n", res[i]);
}LCT
难的东西唯一的缺点就是难...
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n, ans[N];
struct Query{
int id, l, r;
bool operator <(Query &b)const
{
return r <b.r;
}
}querys[N];
int h[N], e[N], nxt[N], idx;
void add(int a,int b)
{
e[idx] = b, nxt[idx] = h[a], h[a] = idx ++;
}
namespace LCA{
int lca(int ,int);
}
namespace treeArray{
#define lowbit(x) (-x & x)
int s[N];
void add(int x, int p)
{
x ++;
for(int i = x; i <= n + 1; i += lowbit(i)) s[i] += p;
}
int sum(int x)
{
x ++;
int ans = 0;
for(; x; x -= lowbit(x) ) ans += s[x];
return ans;
}
}
namespace segTree{
#define ls u << 1
#define rs u << 1 | 1
#define mid (L + R >> 1)
int t[N];
void pushup(int u)
{
t[u] = LCA::lca(t[ls], t[rs]);
}
void build(int u, int L, int R)
{
t[u] = L;
if(L == R) return;
build(ls, L, mid); build(rs, mid +1, R);
pushup(u);
}
int query(int l, int r,int u, int L, int R)
{
if(l <= L && R <= r) return t[u];
if(r <= mid) return query(l, r, ls, L, mid);
if(l > mid) return query(l, r, rs, mid + 1, R);
return LCA::lca(query(l, r, ls, L, mid), query(l, r, rs, mid +1, R));
}
}
namespace LCA{
const int K = 20;
int fa[N][K], dep[N];
void dfs(int u, int father)
{
dep[u] = dep[father] + 1; fa[u][0] = father;
for(int k = 1; k < K; ++ k) fa[u][k] = fa[fa[u][k - 1]][k - 1];
for(int i = h[u]; ~i; i = nxt[i])
{
int to = e[i];
if(to == father) continue;
dfs(to, u);
}
}
int lca(int a,int b)
{
if(dep[a] < dep[b]) swap(a, b);
for(int k = K - 1; k >= 0; k --)
if(dep[fa[a][k]] >= dep[b]) a = fa[a][k];
if(a == b) return a;
for(int k = K - 1; k >= 0; k --) if(fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
return fa[a][0];
}
int deplca(int l, int r)
{
return dep[segTree::query(l, r, 1, 1, n)];
}
}
namespace LCT{
struct Node{int s[2], p, v, siz, tag;} t[N];
int stk[N], top;
void dfs(int u, int father)
{
t[u].p = father;
for(int i = h[u]; ~i; i = nxt[i])
{
int to = e[i];
if(to == father) continue;
dfs(to, u);
}
}
void pushup(int u)
{
t[u].siz = t[t[u].s[0]].siz + t[t[u].s[1]].siz + 1;
}
void addtag(int u,int v)
{
t[u].tag = t[u].v = v;
}
void pushdown(int u)
{
if(t[u].tag)
{
addtag(t[u].s[0], t[u].tag); addtag(t[u].s[1], t[u].tag);
t[u].tag = 0;
}
}
bool isroot(int x)
{
return t[t[x].p].s[0] != x && t[t[x].p].s[1] != x;
}
void rotate(int x)
{
int y = t[x].p, z = t[y].p, k = t[y].s[1] == x;
if(!isroot(y)) t[z].s[t[z].s[1] == y] = x; t[x].p = z;
t[y].s[k] = t[x].s[k ^ 1]; t[t[x].s[k ^ 1]].p = y;
t[x].s[k ^ 1] = y; t[y].p = x;
pushup(y); pushup(x);
}
void splay(int x)
{
int bak = x; stk[top = 1] = x;
while(!isroot(bak)) stk[++ top] = bak = t[bak].p;
while(top) pushdown(stk[top --]);
while(!isroot(x))
{
int y = t[x].p, z = t[y].p;
if(!isroot(y))
if(t[y].s[1] == x ^ t[z].s[1] == y) rotate(x);
else rotate(y);
rotate(x);
}
}
void access(int x)
{
int col = x, y = 0;
for(; x; y = x, x = t[x].p)
{
splay(x);
treeArray::add(t[x].v, -(t[t[x].s[0]].siz + 1));
t[x].s[1] = y; pushup(x);
}
treeArray::add(col, t[y].siz);
addtag(y, col);
}
}
using treeArray::sum;
using LCT::access;
using LCA::deplca;
int main()
{
//freopen("1.txt", "r", stdin);
memset(h, -1, sizeof h);
int m; scanf("%d%d", &n, &m);
for(int i = 1; i < n; ++i)
{
int a, b; scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
for(int i = 0; i < m; ++i)
{
int l, r; scanf("%d%d", &l, &r);
querys[i] = {i, l, r};
}
LCA::dfs(1, 0); segTree:: build(1, 1, n);
LCT::dfs(1, 0);
sort(querys, querys + m);
int j = 0;
treeArray::add(0, n);
for(int i = 1; i <= n; ++ i)
{
access(i);
for(; j < m && querys[j].r == i; ++ j)
ans[querys[j].id] = n - sum(querys[j].l - 1) - deplca(querys[j].l, querys[j].r);
}
for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
}
京公网安备 11010502036488号