xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共101篇）

BZOJ 1984 月下“毛景树” 树链剖分+线段树

题意 bzoj好像把这题删了，在洛谷里找的毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，...

树链剖分线段树

2019-05-23

0 389

BZOJ 2243 [SDOI2011]染色树链剖分+线段树

题意给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。请你写一个程序依次完成这m个操作。分析用...

线段树树链剖分

2019-05-23

0 498

BZOJ 2243 [SDOI2011]染色树链剖分+线段树

题意给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。请你写一个程序依次完成这m个操作。分析用...

线段树树链剖分

2019-05-23

0 384

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 386

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 412

BZOJ 4034 [HAOI2015]树上操作线段树+树剖或dfs

题意直接照搬原题面有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。 ...

BZOJ 线段树树链剖分

2019-05-23

0 426

BZOJ 4034 [HAOI2015]树上操作线段树+树剖或dfs

题意直接照搬原题面有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。 ...

BZOJ 线段树树链剖分

2019-05-23

0 410

Codeforces 1054D Changing Array 贪心+异或和

题意给一个长度为\(n\)的位数为\(k\)的整数数列\(a\)，一次操作可将任意\(a_i\)取反，问经过任意次操作后最多有多少个区间异或和不为\(0\) 分析求出前缀异或和，区间异或和为\(0\)的区间数转化为求有多少对前缀异或和相等，然后用总区间数减一下，对一个\(a_i\)...

codeforces 贪心异或

2019-05-17

0 548

Codeforces 1054D Changing Array 贪心+异或和

题意给一个长度为\(n\)的位数为\(k\)的整数数列\(a\)，一次操作可将任意\(a_i\)取反，问经过任意次操作后最多有多少个区间异或和不为\(0\) 分析求出前缀异或和，区间异或和为\(0\)的区间数转化为求有多少对前缀异或和相等，然后用总区间数减一下，对一个\(a_i\)...

贪心异或

2019-05-17

0 537

Codeforces 1167 F Scalar Queries 计算贡献+树状数组

题意给一个数列\(a\),定义\(f(l,r)\)为\(b_1, b_2, \dots, b_{r - l + 1}\),\(b_i = a_{l - 1 + i}\),将\(b\)排序,\(f(l,r)\)=\(\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot...

codeforces 计算贡献树状数组

2019-05-16

0 563