Inner World

题目链接

题意

有$n$棵树，每棵树开始只有根节点，现有$q$次操作，每次在$(L_{i}, R_{i})$树上的$u_{i},v_{i}$间连一条边，或者询问$(L_{i}, R_{i})$间所有树上$u_{i}$节点的子树大小之和是多少。

思路

每次加边都不同，可以把这些树都并到一棵树上去，因为实质上他们可以长得都一样，只不过我给每个树上节点标记一个作用范围。
关于子树大小问题，我们很容易想到借助$dfs$序转到序列上去做。相当于，我每次给一个位置的区间加一，或者询问任意两个位置区间差。
主席树裸题。于是传说中的$dfs$序建可持久化线段树就出现了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=312345;
struct node {
    int l,r;
    long long sum,add;
} seg[maxn*62];
vector<int> G[maxn];
int n,m,q,L[maxn],R[maxn],st[maxn],ed[maxn],rid[maxn],tot,root[maxn],cnt;
void update(int &x,int y,int L,int R,int l,int r) {
    x=++cnt;
    seg[x]=seg[y];
    seg[x].sum+=r-l+1;
    if (l==L&&r==R) {
        ++seg[x].add;
        return;
    }
    int m=(L+R)>>1;
    if (m>=l) update(seg[x].l,seg[y].l,L,m,l,min(m,r));
    if (m<r) update(seg[x].r,seg[y].r,m+1,R,max(m+1,l),r);
}
long long query(int x,int y,int L,int R,int l,int r,long long add) {
    if (l<=L&&r>=R) return add*(R-L+1)+seg[x].sum-seg[y].sum;
    int m=(L+R)>>1;
    long long ret=0;
    if (m>=l) ret+=query(seg[x].l,seg[y].l,L,m,l,r,add+seg[x].add-seg[y].add);
    if (m<r) ret+=query(seg[x].r,seg[y].r,m+1,R,l,r,add+seg[x].add-seg[y].add);
    return ret;
}
void dfs(int u) {
    st[u]=++tot;
    rid[tot]=u;
    for (int i=0;i<(int)G[u].size();++i) {
        int v=G[u][i];
        dfs(v);
    }
    ed[u]=tot;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i) {
        int u,v,l,r;scanf("%d%d%d%d",&u,&v,&l,&r);
        G[u].push_back(v);
        L[v]=l;
        R[v]=r;
    }
    dfs(1);
    L[1]=1;
    R[1]=n;
    for (int i=1;i<=tot;++i) update(root[i],root[i-1],1,n,L[rid[i]],R[rid[i]]);
    scanf("%d",&q);
    while (q--) {
        int x,l,r;scanf("%d%d%d",&x,&l,&r);
        printf("%lld\n",query(root[ed[x]],root[st[x]-1],1,n,l,r,0));
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
 
const int N = 3e5 + 5;
vector<int> G[N];
 
struct oper
{
    int type, l, r, u, v;
    int id;
    bool operator < (const oper& oth) const
    {
        return id < oth.id;
    }
}op[N];
int st[N], ed[N];
int dfn;
int fa[N];
void dfs(int u, int f)
{
    st[u] = ++dfn;
    dbg(u, st[u]);
    fa[u] = f;
    for (auto &v : G[u])
    {
        if (v == f)
            continue;
        dfs(v, u);
    }
    ed[u] = dfn;
}
 
struct que
{
    int type, l, r, pos;
    int bel, sign;
    bool operator < (const que& u) const
    {
        if (pos == u.pos)
            return type < u.type;
        return pos < u.pos;
    }
}arr[N * 3];
ll ans[N];
 
#define lson rt << 1
#define rson rt << 1 | 1
#define Lson L, mid, lson
#define Rson mid + 1, R, rson
 
ll sum[N << 2], lazy[N << 2];
void push_up(int rt)
{
    sum[rt] = sum[lson] + sum[rson];
}
 
void build(int L, int R, int rt)
{
    lazy[rt] = 0;
    if (L == R)
    {
        sum[rt] = 0;
        return;
    }
    int mid = (L + R) >> 1;
    build(Lson);
    build(Rson);
    push_up(rt);
}
 
void push_down(int rt, int len)
{
    if (lazy[rt])
    {
        lazy[lson] += lazy[rt];
        lazy[rson] += lazy[rt];
        sum[lson] += (len - (len >> 1)) * lazy[lson];
        sum[rson] += (len >> 1) * lazy[rt];
        lazy[rt] = 0;
    }
}
 
void update(int l, int r, int v, int L, int R, int rt)
{
    if (l <= L && r >= R)
    {
        lazy[rt] += v;
        sum[rt] += (R - L + 1) * v;
        return;
    }
    push_down(rt, R - L + 1);
    int mid = (L + R) >> 1;
    if (l <= mid)
        update(l, r, v, Lson);
    if (r > mid)
        update(l, r, v, Rson);
    push_up(rt);
}
 
ll query(int l, int r, int L, int R, int rt)
{
    if (l <= L && r >= R)
        return sum[rt];
    push_down(rt, R - L + 1);
    int mid = (L + R) >> 1;
    ll ans = 0;
    if (l <= mid)
        ans += query(l, r, Lson);
    if (r > mid)
        ans += query(l, r, Rson);
    return ans;
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int tot = 0;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d%d", &op[i].u, &op[i].v, &op[i].l, &op[i].r);
        op[i].type = 1;
        op[i].id = i;
        G[op[i].u].push_back(op[i].v);
    }
    dfn = 0;
    dbg("dfs begin");
    dfs(1, 0);
    dbg("dfs end");
    for (int i = 1; i <= m; i++)
    {
        tot++;
        arr[tot].type = 1;
        arr[tot].pos = st[op[i].v];
        arr[tot].l = op[i].l;
        arr[tot].r = op[i].r;
    }
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        int u, l, r;
        scanf("%d%d%d", &u, &l, &r);
        tot++;
        arr[tot].type = 2;
        arr[tot].l = l;
        arr[tot].r = r;
        arr[tot].pos = st[u] - 1;
        arr[tot].bel = i;
        arr[tot].sign = -1;
 
        tot++;
        arr[tot].type = 2;
        arr[tot].l = l;
        arr[tot].r = r;
        arr[tot].pos = ed[u];
        arr[tot].bel = i;
        arr[tot].sign = 1;
    }
    tot++;
    arr[tot].type = 1;
    arr[tot].l = 1;
    arr[tot].r = n;
    arr[tot].pos = 1;
    sort(arr + 1, arr + tot + 1);
    build(1, n, 1);
    for (int i = 1; i <= tot; i++)
    {
        dbg(arr[i].type, arr[i].l, arr[i].r, arr[i].pos, arr[i].bel, arr[i].sign);
        if (arr[i].type == 1)
        {
            update(arr[i].l, arr[i].r, 1, 1, n, 1);
        }
        else
        {
            ll ret = arr[i].sign * query(arr[i].l, arr[i].r, 1, n, 1);
            dbg(ret);
            ans[arr[i].bel] += ret;
        }
    }
    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
    return 0;
     
}