@wzq
2015-11-15T01:32:02.000000Z
字数 4564
阅读 1428
data_structure
http://acm.hdu.edu.cn/showproblem.php?pid=5468
2015上海网赛
给出一个有n(n<=10^5)个结点的有根树，树上的结点都有一个不大于10^5的正整数权值。询问每一个结点的子树有多少个权值和它互质。
由于权值都不大于10^5，可以把每个权值的质因数分解，用容斥原理来求和它不互质的数的个数。一开始我的想法就是从叶子做起，用一个桶来存储质因子积，求得某个结点的子树答案后，就把它的质因子积状态合并到它到父亲。显然用桶是很费空间的，所以我用map或平衡树来存质因数积，合并的时候用启发式合并。由于每个数最多6个质因子，所以时间复杂度大约是O(64*n*(log(64*n))^2)。
这种做法的时间复杂度很大，怎么做都是TLE的。题解的做法是按照dfs序列的顺序来加入权值，用一个桶来存已经加入的权值的质因子积，保证每次计算的时候，该结点的子树已经在入桶了。但是非这棵子树的权值也会入桶，直接用容斥原理算是不对的。我想到这里就想不下去了。然而，dfs序列还有一个性质，那就是在遍历子树的根前，这棵子树的其它结点都不会遍历到。所以我们只需要在遍历这棵子树前，先计算有多少不互质的，遍历完这棵子树后再计算不互质的个数，相减就可以得到子树中不互质的个数了。时间复杂度是O(2*64*n)。比合并的算法优很多。
由于问题是求整棵树的所有结点的子树，所以我们可以巧妙地用dfs序列来进行整体处理。虽然前面的子问题会影响后面的子问题，但是这个影响可以提前计算出来，是可以消除的。
再者，dfs序列的一些性质，都是子树题目的钥匙。
http://acm.hdu.edu.cn/showproblem.php?pid=5458
2015沈阳网赛
给出n个点，m条无向边的图，q次操作(1<=n<=3*10^4, 1<=m,q<=10^5)。q次操作分两类，一类是删除图中的某一条边，一类是询问图中的两个点a和b之间有多少条桥使a和b不连通。输入数据保证删的边一定存在，并且图始终是连通的。
先从原图中选n-1条边可以构成一棵树。如果没有其它边，那对于每次询问操作，a和b之间的最短路径上的所有边都是能使a和b不连通的桥。如果有一条非树边连通了a和b，那a和b到lca的路径上的所有边都不会是桥，而那个非树边也不会成为桥。所以，我们可以对a和b间的最短路径上的边打个标记。树上的链标记，我们可以用树链剖分+改一段问一段的线段树做，或者用lct。
对于删除操作，我们可以用离线处理，倒过来加边来做。由于图始终是连通的，所以不会出现树的合并现象，也就是不用lct。
我做这题的时候，只听了别人的题目描述，没有自己看题，漏了“图始终是连通”的条件，写lct没写出来。所以，即便英文不好，也要认真看看题。
图的连通性多可以借用树来做，总结下桥的条件
割点问题较复杂，以后再总结
http://acm.hdu.edu.cn/showproblem.php?pid=5452
2015沈阳网赛
给出一棵n个结点的树(n<=20000)，还有一些非树边（不属于树边，但连接树里的结点），总边数不超过200000。现在要在某一规则下删边，使剩下的树边和非树边不能连通这个图，问最小需要删掉几条边。删边规则是：一定而且只能删掉树边中的一条，非树边可以任意删多条。
树边一定删一条，所以我们可以枚举要删哪条树边，树边删了后，有可能有非树边代替这条树边连通这棵树，所以要把能代替这条树边的非树边也删了。问题就转化为每条树边能被多少条非树边代替，最小代替数是多少？
一条非树边能代替的树边，就在这条非树边两个端点到它们lca的路径上。显然可以用树链剖分，统计每条树边被非数边覆盖了多少次（覆盖指和某条非树边形成了环）。由于是改一段问一点，所以可以不用线段树（会TLE），输出答案在最后（非动态查询），所以可以在起始端点+1，末尾端点后一位-1，最后再扫一遍。
还有一种方法，不用树链剖分，直接求lca，每次在非树边上的端点处各+1，在lca处-2，最后从叶子结点网根上扫。
如果用离线tarjan，就可以做到O(N+M)。
http://acm.hdu.edu.cn/showproblem.php?pid=4777
2013杭州区域赛
给出n个数和m次询问，每次询问一个区间[L,R]，问区间内有多少个数，满足和区间内除本身外的所有数都互质。n,m和所有的数都不超过2*10^5。
首先我们可以预处理每个数xi往左往右最近一个和它不互质的位置。这个问题分别从左往右，从右往左地扫，分解质因数用桶纪录就可以解决了。将求出的不互质的位置再往右(左)移一个位置，就可得到一个区间[AL,AR]，这个区间的所有数除xi本身外都与xi互质。
对n个数，我们都可以得到一个区间[AL,AR]。如果询问区间[L,R]被[AL,AR]包含了，xi就有可能是询问[L,R]的一个答案了。为什么是有可能呢？因为i有可能不属于[L,R]，只有当i在[L,R]区间内且xi对应的区间[AL,AR]包含[L,R]时，xi才是[L,R]的一个答案。
这种情况该怎么办呢？我们可以把i不在[L,R]区间的答案减去。对每个xi重新构造两个区间[AL,i-1]和[i+1,AR]，如果i属于[L,R]，那[AL,i-1]和[i+1,AR]一定都不会包含[L,R]；否则，[AL,i-1]和[i+1,AR]有且仅有一个区间包含[L,R]。
显然，此题要用离线处理（在线得用可持久化，但空间不允许）。以上两个问题，都转化为求解询问区间被构造区间覆盖了多少次，两个问题的答案相减就是最后答案。我的做法是分别对询问区间和构造区间按右端点离散化。下标i从右往左扫，遇到一个右端点为i的构造区间，记构造区间的左端点是j，在树状数组的j位置+1(j-n)，然后处理右端点为i的询问区间，记询问区间的左端点为k，求树状数组k位置的和(1-k)。
这题有个坑点就是空间限制是32M，我用vector记预处理的每个数的质因子就不断MLE。后来预处理质数表，直接质因数分解，质因数不存下来才过了。MLE大概是因为质因数最多有7*n个，vector每次push_back不止是开1个数的空间，空间消耗较大。
http://poj.openjudge.cn/practice/C15C?lang=en_US
2015北京大学校赛
给出一个N个结点，M条无向边的图，还有一个时间K，代表共有K天(0<=N,K<=10^5, 0<=M<=2*10^5)。M条边都有一个特性，会在第ki天关闭，其余时候都可以通过(ki有可能大于K)。我们要计算的就是1到K天，每天有多少对点可以互相到达。
这题我不会做，在网上搜到一篇别人解答。
http://blog.csdn.net/u013368721/article/details/45725181
发现是cdq分治+并查集。cdq分治有个人做了一个不错到总结，链接如下：
http://blog.csdn.net/greatwall1995/article/details/8789394
这个题，一开始我写了一个双连通分支，tarjan缩点。错误的认为缩点后剩下的树边才能影响连通性。后面还想了如何按照树的深度从大到小用树状数组统计答案。写到最后的时候，发现了算法错误。
后来想可持久化的并查集，做第i天的时候，能不能先预处理了1到i-1和i+1到K的并查集情况，但发现这两个并查集难以快速整理到一个，比本文的第一题hdu5468的状态合并更加难以实现。
http://www.lydsy.com/JudgeOnline/problem.php?id=4026
某神犇orz Loidc
给出N个正整数，Q次询问(N<=5*10^4,Q<=10^5)。每个正整数Ai不大于10^6。每次询问一个区间[L,R]内所有数的积的欧拉函数mod (10^6+777)。数据强制在线。
第一个子问题，我们可以预处理前缀积，记为prefix[i]。逆元记为IVS[]。第一个子问题就是prefix[R]*IVS[prefix[L-1]]。
第二个子问题，假设可以离线，我们按右端点离散化。对于相同右端点的区间，我们询问[L,R]
对于强制在线，我们只要可持久化一下就行了。每个数最多有7个质因数，时间复杂度是O(Q*2*7*log(N))，空间复杂度是O(4*N+2*7*log(N))。
这一题虽然要用在线算法，但基本思想还是离线操作。将问题划分为有共通处的子问题来做，这部分的子问题可以利用前一部分的子问题的大部分状态。
对于区间内的两个点，对区间有等价影响或部分等价影响对时候，这个时候可以按照某一顺序保留一个。如本题中因为求解按右端点离散化，所以保留最右边的那一个。
魏子卿
2015年11月14日