洛谷P3241 开店

题意：紫妹和幽香是17岁的少女，喜欢可爱的东西。

给定一棵树，有点权，边权。每次求所有权值在[l, r]范围内的点到点x的距离和。强制在线。

解：动态点分治怎么搞啊......

一开始想的是权值的限制直接外层权值线段树就行了，关键是怎么批量求距离。

jxl想的是树上莫队的方法，括号序列。然后发现当x和y在不同子树的时候，x -> lca的距离是负的。

然后考虑lca。距离是d[x] + d[y] - 2d[lca]，前面两个都好求，主要是第三项。

稍稍思考一下，lca只可能是x到根路径上的点。每个点作为lca的次数就是siz - siz[son]

所以可以转为计算每条边的贡献。每条边的贡献就是它下面的子树大小。这样就可以做了。

具体来说，d[x] * cnt和∑d[y]可以用两个前缀和数组求出。以离散化后的权值为下标。

然后建一个以权值为版本的主席树，线段树上维护的是DFS序的该点的父边的计算次数。

可以发现，按照权值我们每插入一个点，就要对它到根的路径进行修改。查询的时候也是查询x到根的路径。所以我们必须写树剖了>_<

主席树区间加区间查，使用标记永久化。

然后发现我之前以为的标记永久化都是假的......

具体来说，给一个区间加的时候，它途中经过的区间都要加上相应的值，而标记只打在最后的区间。

查询的时候，沿途记录标记数量。到终点的时候，用终点的sum + 区间Val * 标记数量即可。

如果修改在查询上面，那么你会把标记记录下来，最后在终点区间加上。

如果修改在下，那么你终点区间的sum已经加了那一次修改的影响。

然后这道毒瘤SB题就这样A了...时间复杂度nlog²n。

 #include <cstdio>

 #include <algorithm>

 typedef long long LL;

 const int N = , lm = 1e9, M = ;

 struct Edge {

     int nex, v, len;

 }edge[N << ]; int tp;

 struct Node {

     int val, p;

     inline bool operator <(const Node &w) const {

         return val < w.val;

     }

 }node[N];

 int e[N], n, top[N], son[N], fa[N], pos[N], num, siz[N], X[N], deep[N], Sum[N], id[N], val2[N], tot, rt[N], val[N];

 LL Val[M], d[N], exVal[N];

 int ls[M], rs[M], exsum[N], tag[M];

 inline void add(int x, int y, int z) {

     tp++;

     edge[tp].v = y;

     edge[tp].len = z;

     edge[tp].nex = e[x];

     e[x] = tp;

     return;

 }

 void DFS_1(int x, int f) { // siz fa d son

     fa[x] = f;

     siz[x] = ;

     deep[x] = deep[f] + ;

     for(int i = e[x]; i; i = edge[i].nex) {

         int y = edge[i].v;

         if(y == f) {

             continue;

         }

         d[y] = d[x] + edge[i].len;

         val2[y] = edge[i].len;

         DFS_1(y, x);

         siz[x] += siz[y];

         if(siz[y] > siz[son[x]]) {

             son[x] = y;

         }

     }

     return;

 }

 void DFS_2(int x, int f) { // pos top

     top[x] = f;

     pos[x] = ++num;

     id[num] = x;

     if(son[x]) {

         DFS_2(son[x], f);

     }

     for(int i = e[x]; i; i = edge[i].nex) {

         int y = edge[i].v;

         if(y == fa[x] || y == son[x]) {

             continue;

         }

         DFS_2(y, y);

     }

     return;

 }

 void Add(int x, int &y, int L, int R, int l, int r) {

     if(!y || y == x) {

         y = ++tot;

         Val[y] = Val[x];

         tag[y] = tag[x];

         ls[y] = ls[x];

         rs[y] = rs[x];

         //printf("new %d [%d %d] val = %lld \n", y, l, r, Val[y]);

     }

     Val[y] += Sum[std::min(R, r)] - Sum[std::max(L, l) - ];

     //printf("val %d = %lld  += (%d %d) %d \n", y, Val[y], std::min(R, r), std::max(L, l) - 1, Sum[std::min(R, r)] - Sum[std::max(L, l) - 1]);

     if(L <= l && r <= R) {

         tag[y]++;

         return;

     }

     int mid = (l + r) >> ;

     if(L <= mid) {

         Add(ls[x], ls[y], L, R, l, mid);

     }

     if(mid < R) {

         Add(rs[x], rs[y], L, R, mid + , r);

     }

     return;

 }

 inline void insert(int x, int id) {

     while(x) {

         //printf("id = %d \n", id);

         Add(rt[id - ], rt[id], pos[top[x]], pos[top[x]] + (deep[x] - deep[top[x]]), , n);

         x = fa[top[x]];

     }

     return;

 }

 LL Ask(int x, int y, int L, int R, int l, int r, int tagx, int tagy) {

     if(L <= l && r <= R) {

         return Val[y] - Val[x] + 1ll * (tagy - tagx) * (Sum[r] - Sum[l - ]);

     }

     tagx += tag[x];

     tagy += tag[y];

     int mid = (l + r) >> ;

     LL ans = ;

     if(L <= mid) {

         ans += Ask(ls[x], ls[y], L, R, l, mid, tagx, tagy);

     }

     if(mid < R) {

         ans += Ask(rs[x], rs[y], L, R, mid + , r, tagx, tagy);

     }

     return ans;

 }

 LL ask(int l, int r, int x) {

     LL ans = ;

     while(x) {

         LL t = Ask(rt[l - ], rt[r], pos[top[x]], pos[top[x]] + (deep[x] - deep[top[x]]), , n, , );

         ans += t;

         x = fa[top[x]];

     }

     return ans;

 }

 int main() {

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

     //freopen("my.out", "w", stdout);

     int q, A;

     scanf("%d%d%d", &n, &q, &A);

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

         scanf("%d", &val[i]);

         val[i]++;

         node[i].p = i;

         X[i] = val[i];

     }

     for(int i = , x, y, z; i < n; i++) {

         scanf("%d%d%d", &x, &y, &z);

         add(x, y, z);

         add(y, x, z);

     }

     // prework

     DFS_1(, );

     DFS_2(, );

     std::sort(X + , X + n + );

     int temp = std::unique(X + , X + n + ) - X - ;

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

         val[i] = std::lower_bound(X + , X + temp + , val[i]) - X;

         node[i].val = val[i];

         exsum[val[i]]++;

         exVal[val[i]] += d[i];

     }

     for(int i = ; i <= temp; i++) {

         exsum[i] += exsum[i - ];

         exVal[i] += exVal[i - ];

     }

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

         Sum[i] = Sum[i - ] + val2[id[i]];

     }

     std::sort(node + , node + n + );

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

         insert(node[i].p, node[i].val);

     }

     LL lastans = ;

     for(int i = , x, y, z; i <= q; i++) {

         scanf("%d%d%d", &x, &y, &z);

         int l = (y + lastans) % A + ;

         int r = (z + lastans) % A + ;

         if(l > r) {

             std::swap(l, r);

         }

         l = std::lower_bound(X + , X + temp + , l) - X;

         r = std::upper_bound(X + , X + temp + , r) - X - ;

         if(l > r) {

             lastans = ;

             printf("%lld\n", lastans);

         }

         else {

             LL t = ask(l, r, x);

             lastans = 1ll * d[x] * (exsum[r] - exsum[l - ]) + (exVal[r] - exVal[l - ]);

             lastans -= t * ;

             printf("%lld\n", lastans);

         }

     }

     return ;

 }

AC代码

巴特西

洛谷P3241 开店

最新文章

热门文章