洛谷 Codeforces 根号分治真是妙啊. 思路 考虑对于单独的一个\(k\)如何计算答案. 与"赛道修建"非常相似,但那题要求边,这题要求点,所以更加简单. 在每一个点贪心地把子树升上来的两条最长的链拼在一起,能组就组,否则把最长链往上送,复杂度\(O(n)\). 那么多个\(k\)怎么办呢? 分析一波,\(k<\sqrt{n}\)时可以暴力计算,而\(k>\sqrt{n}\)时\(ans_k\leq \lfloor \frac{n}{k}\rfloor\),只有\(

题目链接:http://codeforces.com/problemset/problem/444/C 题意:给定一个长度为n的序列a[].起初a[i]=i,然后还有一个色度的序列b[],起初b[i]=0.现在有2种操作: 1 l r x:区间染色,a[l],a[l+1]...a[r]变成x.同时b[l],b[l+1]...b[r]加上对应的|x-a[i]|值. 2 l r:统计区间和,统计区间b[l],b[l+1]...b[r]的和. 思路:线段树是比较常见的做法.考虑分块.每块维护一个laz

题目链接:http://codeforces.com/problemset/problem/455/D 题意:给定一个长度为n的序列a[]. m次操作.共有两种操作 1 l r:将序列的a[l].a[l+1]...a[r]变成a[r].a[l].a[l+1]...a[r-1]:2 l r k:求序列a[l].a[l+1]...a[r]中有多少个值为k. 输入的l,r,k都是加密过的.所以要解密一下.规则为 l=(l+ans-1)%n+1  r=(r+ans-1)%n+1 k=(k+ans-1)%

题目链接:http://codeforces.com/problemset/problem/551/E 题意:给定一个长度为N的序列. 有2个操作 1 l r v:序列第l项到第r项加v(区间加),  2 v:求整个序列中值为v的数的位置的差值最大是多少.不存在输出-1. 思路:分块. 每块维护该块序列排序后的序列. 对于区间修改,我们定义一个lazy标记.对于整块的修改我们只修改lazy, 其他情况暴力修改.然后情况该块后重新加入修改后的块然后排序. 对于查询操作.查询每块时v应该减去该块的l

题目链接:http://codeforces.com/problemset/problem/103/D 题意:给定一个长度为n的序列.然后q个询问.每个询问为(a,b),表示从序列第a项开始每b项的加和. 思路:2014集训队论文中的<<根号算法--不只是分块>>中提到这题. 传统的数据结构比较擅长处理连续区间的询问.但是不擅长处理间隔位置的询问.考虑到分块. 对于b>sqrt(n)的询问.我们暴力计算.可以发现b越大我们扫描的位置就会越小.最大扫描次数为O(n/sqrt(n

BZOJ \(\mathbb{mod}\)一个数\(y\)的最小值,可以考虑枚举剩余系,也就是枚举区间\([0,y),[y,2y),[2y,3y)...\)中的最小值(求后缀最小值也一样)更新答案,复杂度是\(O(\frac ny)\)的.注意到\(y>\sqrt n\)时,枚举次数\(<\sqrt n\). 我们可以对\(y\)根号分治,设\(m=\sqrt{V}\)(\(V\)是值域). 当\(y\leq m\)时,可以维护一个大小为\(m\)的桶\(s_i\)(表示模数为\(i\)时的\

Everyone knows that DNA strands consist of nucleotides. There are four types of nucleotides: "A", "T", "G", "C". A DNA strand is a sequence of nucleotides. Scientists decided to track evolution of a rare species, wh

题意 给你 \(n\) 个串 \(s_{1\cdots n}\) ,每次询问给出 \(l,r,k\) ,问在 \(s_{l\cdots r}\) 中出现了多少次 \(s_k\) . \(n,q,\sum|s|\le 10^5\) 分析 先建AC自动机的 \(fail\) 树, 我们考虑两种暴力: 将 \(l​\) 到 \(r​\) 中的每个串的末尾节点子树标记,查询 \(s_k​\) 的所有节点 \(fail​\) 树到根的路径和. 将 \(s_k\) 的每个节点的子树标记,查询 \(l\) 到

题目链接:http://codeforces.com/problemset/problem/13/E 题意:给定n个弹簧和每个弹簧初始的弹力a[].当球落在第i个位置.则球会被弹到i+a[i]的位置. 现在有2种操作: 1 a b:把第a个弹簧的弹力修改为b. 2 a:当球初始放入的位置为a时,需要弹几次才会弹出n.弹出前的最后一个位置是多少. 输出位置和次数. 思路:和BZOJ 2002一样. 然后记录一个最后弹出去的位置preidx.每次弹出当前块的时候记录当前的位置即可.然后最后再暴力模拟

题意 给定两个长度为 \(n\) 的序列 \(\{a_i\}\) 与 \(\{b_i\}\),你需要求出它们的相似度.,我们定义这两个序列的相似度为将其中一个序列转化为另一个序列所需的最小操作次数.一次操作定义如下: - 选择序列中的一个长度为 \(k\) 的子段,将子段内的所有元素异或上一个相同的值 \(x\),\(x\) 可以任意决定.特殊地,若其中一个序列无论如何都不能转化到另一个序列,那么这两个序列的相似度为 \(-1\). 这之后,将会有 \(q\) 次修改操作,单次操作格式如下: s

大意:给定n元素序列, 2种操作 将区间$[l,r]$循环右移1位 询问$[l,r]$中有多少个等于k的元素 现在给定q个操作, 输出操作2的询问结果, 强制在线 思路1: 分块 每个块内维护一个链表, 循环右移相当于删除一个元素, 再插入一个元素, 每个块内再维护一个桶统计元素个数即可 分块好久没写过了, 先放个分块大致流程 void init() { //sqn是分块数, blo[i]是位置i所属块的编号 //L[i], R[i]是位置i所属块的左右边界 sqn = sqrt(n); REP

Description 某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏.游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞.绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞.为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数. Input 第一行

https://cn.vjudge.net/contest/148706 A #include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int read(){ ,f=;char ch=getchar(); ;ch=getchar();} +c

题意: 给定一个长度为 N 的序列两种操作1 l r 将[l,r]的数向右循环移位 2 l r 询问[l,r]内有多少个数等于 k其中 N,Q≤105,ai≤N 强制在线 思路: 1. 每块用一个链表维护一下 位移的话由于是链表,操作速度很快然后每个数都不超过 N,所以用一个数组记录一下每块每个数的个数 总的复杂度就是 O(Qsqrt(N)) 2. 如果不考虑那个奇怪的询问的话,可以简单地用splay树维护序列.但是splay上显然不能维护每种颜色的个数,这样在每个节点上时间和空间都是O(n)的

洛谷 Codeforces 分治的题目,或者说分治的思想,是非常灵活多变的. 所以对我这种智商低的选手特别不友好 脑子不好使怎么办?多做题吧-- 前置知识 线性基是你必须会的,不然这题不可做. 推荐再去看看洛谷P4151. 思路 看到异或最短路,显然线性基. 做题多一些的同学想必已经想到了"洛谷P4151 [WC2011]最大XOR和路径"了. 先考虑没有加边删边的做法: 做出原图的任意一棵生成树: 把每个非树边和树边形成的环丢进线性基里: 询问时把两点在树上的路径异或和丢进线性基里求

(这篇我就不信有网站来扣) 这个暑假打算刷刷题啥的 但是写博客好累啊  堆一起算了 隔一段更新一下.  7月27号之前刷的的就不写了 , 写的累 代码不贴了,可以找我要啊.. 2017.8.27update : 开学了终于搞到了550  可还行 *数据结构 *可持久化线段树/主席树 *bzoj3932 [CQOI2015] 任务查询系统 : 比较裸的主席树,任务查分一下就好了  cqoi真良心 *bzoj4026 dC Loves Number Theory :  数论个头啊,对每个数分解质因数

内容提要 贪心 分治 分块 搜索 接着昨天的讲 过河问题 考虑AB是最快的人,CD是最慢的人,要把CD两个人送过河,只有两种方案,牵扯到四个人,并且n个规模的原问题化成了n-2个规模的子问题 那么最后有两个情况,四个人和三个人,如果是四个人就直接按刚才的方法搞一搞就好了,如果是三个人的话,就有两个方案,一个是A来回送,一个是AB一起操作,就是在两个之间取min就好了 贪心算法在骗分时的运用主要集中在两点: 1.贪心算法失效时该如何补救? 2.如何利用贪心算法来提升自己的一个暴力算法? 1.贪心算

洛谷 Codeforces 思路 一开始想到莫队+bitset,发现要T. 再想到分块+bitset,脑子一抽竟然直接开始写了,当然也T了. 最后发现这就是个裸的CDQ分治-- 发现\(a\)不变,可以处理出每个数在\(a\)中的位置\(pos\). 然后处理出\(aa_i=pos_{b_i}\),交换时就是\(swap(aa_x,aa_y)\). 把每个位置看成\((i,aa_i)\)的点,查询\(l1,r1,l2,r2\)时就是查以\((l2,l1)\)为左下角,\((r2,r1)\)为右上

Description 给定平面上的 \(n\) 个圆,用三个参数 \((x, y, R)\) 表示圆心坐标和半径. 每次选取最大的一个尚未被删除的圆删除,并同时删除所有与其相切或相交的圆. 最后输出每个圆分别是被那个圆所删除的. Hint \(1\le n\le 3\times 10^5\) \(0\le |x|, |y|, R \le 10^9\) Solution 1 后来在 Codeforces 上找到的官方题解 Link here.如果对题解中某些说明无法理解可以参考上述内容.做法参考

题目链接: http://codeforces.com/contest/103/problem/D D. Time to Raid Cowavans time limit per test:4 secondsmemory limit per test:70 megabytes 问题描述 As you know, the most intelligent beings on the Earth are, of course, cows. This conclusion was reached lo

E. Ciel the Commander Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.codeforces.com/contest/322/problem/E Description Now Fox Ciel becomes a commander of Tree Land. Tree Land, like its name said, has n cities connected by n - 1 undirected ro