题目描述小强要在个孤立的星球上建立起一套通信系统。这套通信系统就是连接个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。 离线在查询的时候，如果我们把这条边删掉，那么答案就很好求观察到有删、加边，用线段树分治即可具体而言，对于每一个查询，时间为，和上一次查询（若没有则是添加它的时间），在加入这条边最后一次查询加入到可撤销并查集即可 #include <bits/stdc++.h> #define ri register int #...

题目描述给定长度为的序列：，记为。类似地，是指序列：。若，则称是的子序列。现在有个询问，每个询问给定两个数和，，求的不同子序列的最小值之和。例如，给定序列，询问给定的两个数为和，那么有个子序列，这个子序列的最小值之和为。 一个技巧：取最小数先取区间的最小值，设下标为首先对于左端点，右端点的区间，最小值都是，所以先加上然后考虑左端点、右端点的区间和左端点、右端点的区间我们处理一个数组 _ 表示以为右端点，左端点的区间最小值之和设第一个比第个元素小的数的下标为显然 _ _ 又处理一个 _ 表示 _ 那么，左端点、右端点的区间，贡献为 _ _ _ 想一想，为什么首先 _ _ 很好理解，只算...

问题描述给定一张个顶点条边的无向图（顶点编号为），每条边上带有权值。所有权值都可以分解成的形式。 现在有 个询问，每次询问给定四个参数和，请你求出是否存在一条顶点到之间的路径，使得路径依次经过的边上的权值的最小公倍数为。 注意：路径可以不是简单路径。 注意到不一定是简单路径，所以我们看联通性即可也就是说，我们找到所有的边，用并查集合并，看是否联通以及是否恰好等于考虑对边分块我们将边按排序，询问按排序每一个询问找到最后一个小于它的的边，加入那个块我们处理第块内的询问首先，对于前块的边，我们可以保证它们的第块所有询问的那么我们就对前面的边按再排序一次然后，处理第块每个询问，由于询问的有序，所以以...

考虑算法 for(ri i=1;i<=m;i++) { int x=getfather(e[i].x),y=getfather(e[i].y); if(x!=y) { father[y]=x; ans+=e[i].x; } }我们这样做可以求出最小/大生成树如果我们每次合并，都新建一个节点，再与连边，并用并查集合并，就是重构树 void kruskal() { sort(e+1,e+m+1,cmp); for(ri i=1;i<=2*n-1;i++)father[i]=i; now=n; for...

树链剖分，就是把树上的边划分，然后用数据结构维护的算法 重链剖分：轻边与重边 百度百科的图一个节点子树中节点数最多的节点叫做它的重儿子，与它相连的边称为重边多条重边连起来成为重链我们把重链连续标号，用数据结构维护，即把树上问题转化成了序列上问题，每一个对应了一个节点记为的重儿子，为的深度，为所在重链的顶端，为的父亲，为的序（按重儿子优先，即使重链标号连续） 性质 一条根节点到节点路径上重链、轻链数不超过 证明 重链轻链交替每次走轻链，至少减少一半所以轻链数重链数也为 操作 对于修改两点间路径的操作，我们这样做先跳大的节点，避免跳过头把到做修改再将赋值为这样做直到、在同一重链上对于在同一重链的情...

线段树合并，顾名思义就是把两棵线段树合并在一起，将两棵树信息相加复杂度证明：自己想的证明设添加入各棵线段树的总点数为考虑一条链，长度为，那么合并这条链的复杂度为总复杂度=因为等于所以复杂度为 例题 天天爱跑步https://www.luogu.com.cn/problem/P1600小同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。 这个游戏的地图可以看作一棵包含个结点和条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从到的连续正整数。 现在有个玩家，第个玩家的起点为，终点为...

D GCD of an Array 题目描述 你有一个长度为的数组.你需要处理个操作，格式是：输入两个数和，将乘以.每次操作之后，你需要输出数组所有元素的GCD.因为答案可能很大，所以模再输出 输入 第一行由两个整数组成：和第二行由个整数组成 ——操作前的数组的元素接下来q行是操作，每行输入两个整数和 输出 输出行，对于每个操作输出数组元素的GCD模以的值 样例 输入 4 3 1 6 8 12 1 12 2 3 3 3输出 2 2 6注意 第一次操作之后，数组是第二次操作之后，数组是第三次操作之后，数组是这里表示做大公约数

链接：https://ac.nowcoder.com/acm/problem/14731来源：牛客网题面求所有长度为的串中满足如下条件的二元组个数：设第i位和第j位分别位和（），则。 答案对取模。 考虑一对和在多少情况下可以出现，即是这对和的贡献 钦定两个位置，剩下随便选，再考虑钦定哪两个位置， 相乘即得 #include <bits/stdc++.h> #define ri int #define ll long long using namespace std; const ll Mod=1e9+7; inline ll ksm(ll a,ll b) { ll an...

链接：https://ac.nowcoder.com/acm/problem/14247来源：牛客网 题目描述给定一个长度为的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为。 ,。 两个区间异或和为，则分别的异或和相等为了避免重复，我们对于，查询和构成的区间与前所有区间的方案数，并把与组成的区间值添加到里 ```#include <bits stdc++.h>#define ri int#define ll long longusing namespace std;const int Maxn=1e3;map<int,int>cnt;int a[...

链接：https://ac.nowcoder.com/acm/problem/14248来源：牛客网 题目描述给定一棵个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。到与到被视为同一条路径。路径的起点与终点不能相同。 是偶数，所以只要为偶数即可于是预处理所有，即到根的距离最后计算和自己奇偶性相同的数量，加起来即可 : #include <bits/stdc++.h> #define ri int #define ll long long using namespace std; const int Maxn=1e5; int lt[Maxn+5],nt[2*...

CSP2020游记Day 0晚上到了两江，宾馆好高档，碰到了zbw、lzc、yzw等人（看到了xt的WIFI），交流了一波题目，然后去和zbw、yzw到房间里做题颓废。结果晚上宾馆很热，半夜才睡着，睡得也不是很好。Day 1 上午起来还算清醒，吃早餐时感觉谁都认识我，和cwl一起坐的大巴，看他颓皇室战争在门口集合了一下就进去了开题！看到A题题目名称吓死我，以为是NOI，看了一下这不是二进制拆分吗，几分钟写完了看到B，动态第k小，这不是线段树上二分吗，还想了半天不用线段树怎么做，最后写了一个二分+树状数组，杀鸡用牛刀，我本来想到可以开桶做，但想到可能会被卡常，便没有写此时过去了十几分钟看了C题，...

T1第一问是瓶颈路，Kruscal或Prim可以解决在第一问的基础上，跑一边Dij即可 #include <bits/stdc++.h> #define ri register int #define ll long long using namespace std; const ll Maxn=5e5; const ll Maxm=1e6; struct Edge { ll x,y,t,w; }e[Maxm+5]; struct Path { ll u,dis; }; priority_queue<Path>q; ll lt[Maxn+5],nt[2*...

把问题看作，即需要分别求出两项的值，令前一项为sumr，后一项为suml；用指针，确保记录时所有的数均在[1,r]或[1,l-1]范围内，即可对值域查询；于是将问题离线，第一步用左端点升序排序；当指针j==q[i].l时，记录suml[q[i].id]=getsum(x)，否则在值域中添加a[j]；再将问题右端点升序排序，当指针j==q[i].r+1时，记录sumr[q[i].id]=getsum(x)，否则在值域中添加a[j];最后统一输出sumr[i]-suml[i]即可；Code: #include<bits/stdc++.h> using namespace std; st...

做的时候经验不够，没有想到一种类似于差分的思想观察操作：操作一：单点修改，对子树影响：所有子树节点到根路径加a操作二：子树所有节点增加a，可以看作先将所有节点到根的总权值加上a * dep[u],再减去a * (dep[x]-1)，数据结构维护一下即可操作三：直接查询 Code: #include<bits/stdc++.h> #define ll long long using namespace std; struct segmenttree { ll l,r,v,lazy,len; }sgt1[8*100000+5],sgt2[8*100000+5]; ll lt[1...