xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共20篇）

2019ICPC上海网络赛 A Lightning Routing I 点分树(动态点分治)+线段树

题意给一颗带边权的树，有两种操作 \(C~e_i~w_i\)，将第\(e_i\)条边的边权改为\(w_i\)。 \(Q~v_i\)，询问距\(v_i\)点最远的点的距离。分析官方题解做法：动态维护直径，然后再支持询问两个点的距离，后者可以 dfs 序 + lca + 树状...

点分树动态点分治线段树

2019-09-25

0 444

2019牛客暑期多校训练营（第七场）E 线段树+离散化区间

题意每次插入区间\([L_i,R_i]\)之间的数，查询中位数。分析把区间离散化为点，就可以用线段树来支持更新和查询了。我们将区间右端点+1，那么一个区间的长度就是右端点减去左端点，然后我们将所有端点离散化一下用线段树维护就行了。例如区间\([1,2],[2,4]\) 区间右端...

线段树

2019-12-24

0 347

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 H-时空栈

题目链接分析将时间\(t\)离散化，按\(t\)建线段树，维护每个时间\(t\)的栈的大小\(s[t]\)。在时间\(t\)入栈一个数即为将区间\([t,n]\)加\(1\) 在时间\(t\)出栈即为将区间\([t,n]\)减\(1\) 查询时间\(t\)的栈顶元素，找到...

线段树

2020-05-13

0 477

codeforces 1373G Pawns 线段树

题意给一个\(n\times n\)的空棋盘，棋盘的第\(k\)列是一个特殊的列，有\(m\)次操作，每次增加一个棋子或者移走一个棋子，如果能使用以下规则将所有棋子移动到第\(k\)列，那么这个棋盘是好的。在格子\((x,y)\)位置的棋子，能移动到\((x,y+1),(x+1,y+1...

线段树

2020-07-02

0 561

codeforces 914 D 线段树+数学

题意给出一个长度为\(n\)的数列\(a\)，两种询问，第一种给出三个数\(l,r,x\)，区间\([l,r]\)的\(gcd\)值是否和\(x\)相似，若最多改变区间\([l,r]\)中的一个数使区间\([l,r]\)的\(gcd\)值等于\(x\)，则相似，第二种给出两个数\(i,y\)，将...

线段树数学 codeforces

2019-04-24

0 501

Comet OJ - Contest #3 D 可爱的菜菜子线段树+线性基

题意给你一个长度为 \(n\) 的整数序列 \(a_1, a_2, \ldots, a_n\)，你需要实现以下两种操作，每个操作都可以用四个整数 \(opt\ l\ r\ v\) 来表示： \(opt=1\) 时，代表把一个区间 \([l, r]\) 内的所有数都 \(xor\) 上 \...

线段树线性基

2019-05-15

0 447

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

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

BZOJ 线段树树链剖分

2019-05-23

0 426

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 1984 月下“毛景树” 树链剖分+线段树

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

树链剖分线段树

2019-05-23

0 427

2019 ACM-ICPC 西安全国邀请赛 E-Tree 树链剖分+线段树

题意给一颗带点权的树，三种操作 \(1~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]|t\) \(2~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]\&t\) \(3~s~t\) 询问将1到s的路径上的所有点作为石头堆，再加上一个个数...

线段树树链剖分

2019-05-29

0 402