JZOJ 5699 「GDOI2018」涛涛摘苹果

发表于 | 分类于 | 5

如果在第 t 天早上有一个对结点 q 的询问，在第 s(s<t) 天晚上出现的结点 x 对其有贡献（初始的视为在第 0 天晚上）当且仅当其满足以下两个条件： 1. x 在 q 的子树中。 2. 这段时间内 x 没有因为脱落酸或者涛涛离开这棵子树。

对于 1，可以转化为 idx∈[idq,idq+sizeq)。其中 idx 表示 x 的 DFS 时间戳，sizex 表示 x 的子树大小。
对于 2，可以转化为 depx−depq≥t−s−1。其中 depx 表示 x 的深度。

第二个式子，我们进行移项，变为 depx+s+1≥depq+t，这样左边只跟 x 有关，右边只跟 q 有关。

然后呢？
显然地，这样就把在第 t 天询问 q 转化成了同时满足 idx∈[idq,idq+sizeq) 和 depx+s+1≥depq+t 的在第 s(s<t) 天晚上出现结点 x 的个数。
所以就离线之后（按时间排序）上树套树辣！
有一个细节，第 s 天晚上可以转化成第 s+1 天早上查询之前，更易理解。
这次吸取了教训，没有手痒敲 FHQ Treap，敲了个树状数组套权值线段树，一遍过掉了。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <algorithm> 
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
#define lowbit(x) ((x) & -(x))
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 1e5;
const int M = 1e5;
const int Q = 1e5;
const int T = 1e5;
int n,m,q;
long long a[N + 5];
int id[N + 5],sz[N + 5],dep[N + 5];
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v;
    pre[tot] = first[u];
    first[u] = tot;
}
struct segnode
{
    long long sum;
    int lson,rson;
} seg[(N << 7) + 10];
int rt[N + T + 5],seg_tot;
void insert(int x,long long k,int &p,int tl,int tr)
{
    if(!p)
        p = ++seg_tot;
    seg[p].sum += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    if(x <= mid)
        insert(x,k,ls(p),tl,mid);
    else
        insert(x,k,rs(p),mid + 1,tr);
}
long long query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    long long ret = 0;
    if(l <= mid)
        ret += query(l,r,ls(p),tl,mid);
    if(r > mid)
        ret += query(l,r,rs(p),mid + 1,tr);
    return ret;
}
inline void update(int x,int y,long long k)
{
    for(register int i = x;i;i -= lowbit(i))
        insert(y,k,rt[i],1,n);
}
inline long long answer(int x,int l,int r)
{
    long long ret = 0;
    for(register int i = x;i <= n + T;i += lowbit(i))
        ret += query(l,r,rt[i],1,n);
    return ret;
}
void dfs(int p,int fa)
{
    static int tot = 0;
    id[p] = ++tot,sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa)
        {
            dep[to[i]] = dep[p] + 1;
            dfs(to[i],p);
            sz[p] += sz[to[i]];
        }
}
struct s_change
{
    int t,x;
    long long w;
    inline bool operator<(const s_change &o) const
    {
        return t < o.t;
    }
} chg[M + 5];
struct s_query
{
    int t,x,id;
    inline bool operator<(const s_query &o) const
    {
        return t < o.t;
    }
} qry[Q + 5];
long long ans[Q + 5];
int main()
{
    freopen("appletree.in","r",stdin);
    freopen("appletree.out","w",stdout);
    read(n),read(m),read(q);
    for(register int i = 1;i <= n;++i)
        read(a[i]);
    int u,v;
    for(register int i = 1;i < n;++i)
        read(u),read(v),add(u,v),add(v,u);
    dep[1] = 1,dfs(1,0);
    for(register int i = 1;i <= n;++i)
        update(dep[i] + 1,id[i],a[i]);
    for(register int i = 1;i <= m;++i)
        read(chg[i].t),read(chg[i].x),read(chg[i].w);
    for(register int i = 1;i <= q;++i)
        read(qry[i].t),read(qry[i].x),qry[i].id = i;
    sort(chg + 1,chg + m + 1),sort(qry + 1,qry + q + 1);
    for(register int i = 1,j = 1;i <= q;++i)
    {
        for(;chg[j].t < qry[i].t && j <= m;++j)
            update(dep[chg[j].x] + chg[j].t + 1,id[chg[j].x],chg[j].w);
        ans[qry[i].id] = answer(dep[qry[i].x] + qry[i].t,id[qry[i].x],id[qry[i].x] + sz[qry[i].x] - 1);
    }
    for(register int i = 1;i <= q;++i)
        printf("%lld\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment