题目链接 题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。
思路:离线处理+线段树的做法不多说了:
1/* *********************************************** 2Author :111qqz 3Created Time :Fri 16 Sep 2016 11:34:32 PM CST 4File Name :code/spoj/dquery.cpp 5************************************************ */ 6#include <cstdio> 7#include …
阅读更多http://www.lydsy.com/JudgeOnline/problem.php?id=2002
题意+思路: 同codeforces 13 E holes.
/* *********************************************** Author :111qqz Created Time :2016年02月21日 星期日 02时29分39秒 File Name :code/bzoj/2002.cpp ************************************************ */
1#include <cstdio> 2#include …
阅读更多http://codeforces.com/problemset/problem/13/E 题意:给你n个洞,进入某个洞后会跑到另一个洞,到了另一个洞之后又可能会继续到下一个洞,问你从一个洞进去,钻了几个洞才会出来,在哪个洞出来
n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i]....
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意:给定一个序列,序列由1-N个元素全排列而成,求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。 思路:增加一个元素,如果它两边的元素都出现了,那么段数-1(相当于把两段连接起来合并成了一段),如果两边元素都没有出现,那么段数+1.反过来,减少一个元素时,如果两边元素都出现了,俺么段数+1(相当于把完整的一段断开成两段),如果两边元素都没有出现,那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000,所以判断某个元素是否出现开一个100000大小的布尔数组即可(我竟然傻逼 …
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=5213 题意:n个数,m个查询,每个查询由4个数l1,r1,l2,r2构成,询问分别从[l1,r1]和[l2,r2]中各取一个数,和为给定的常数k的方案数。
阅读更多http://codeforces.com/contest/220/problem/B
题意:n个数,m个查询区间,对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。
思路:首先,a[i]很大。。。但是n最大才1e5...每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次,上莫队算法。
阅读更多http://codeforces.com/problemset/problem/86/D
题意:Ks为区间内s的数目,求区间[L,R]之间所有KsKss的和
思路:莫队算法,和小z的袜子差不多。
不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多==
/* *********************************************** Author :111qqz Created Time :2016年02月13日 星期六 23时17分58秒 File Name …
阅读更多2038: [2009国家集训队]小Z的袜子(hose)
Time Limit: 20 Sec Memory Limit: 259 MB Submit: 5327 Solved: 2461 [Submit][Status][Discuss] Description
作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z,他有多 …
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=4391 题意:有 n 个点,每个点有一种颜色(可能相同),两种操作:1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。 思路:因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。
阅读更多