xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共20篇）

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 280

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 280

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

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

BZOJ 线段树树链剖分

2019-05-23

0 298

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

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

线段树树链剖分

2019-05-23

0 269

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

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

树链剖分线段树

2019-05-23

0 271

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 276

2019牛客暑期多校训练营（第二场）E 线段树维护dp转移矩阵

题意给一个\(n\times m\)的01矩阵，1代表有墙，否则没有，每一步可以从\(b[i][j]\)走到\(b[i+1][j]\),\(b[i][j-1]\),\(b[i][j+1]\)，有两种询问： \(q=1\),将\(b[x][y]\)的状态反转 \(q=2\),计算从\(...

线段树 DP 矩阵

2019-08-16

0 294

2019牛客暑期多校训练营（第一场）I dp+线段树

题意给出n个点，每个点有a，b两个属性，让你从左下角到右上角划一条线，线的左边每个点的贡献是\(a_i\)，线的右边每个点的贡献是\(b_i\)，使得两部分的总和最大。分析找一条折线将点分割开，使总和最大。把y离散化，然后点按x排序，设\(dp[i]\)为经过第\(i\)个点(该...

DP 线段树

2019-08-20

0 316

“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学) E 小花梨的数组线段树

题意分析预处理出每个数的最小素因子，首先可以知道\(minprime(x*minprime(x))=minprime(x)\)，我们用线段树维护区间最大值\(mx[p]\)，注意这里的最大值并不是实际的最大值，同时维护区间\(a[i]\)乘\(minprime(a[i])\)的次数的最小...

线段树

2019-09-05

0 324

HFUUOJ1024 动态开点线段树+标记永久化

题意分析动态加点线段树，标记永久化好写常数小 Code #include<bits/stdc++.h> #define fi first #define se second #define lson l,mid,p<<1 #define rson mid+1,...

线段树

2019-09-12

0 377