题目链接 题意:给出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=3289
题意:中文题目,简单来说就是求某一区间内的逆序对数。
思路:逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。
阅读更多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=5145 题意:有n个女孩,编号1..n,第i个女孩在第a[i]个教室,m次访问,每次访问编号[L,R]的女孩,处于同一个教室的女孩一次只能访问一个,问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。
阅读更多http://codeforces.com/contest/617/problem/E
题意:给出n个数,m个查询,每个查询给定l,r,问在区间【l,r】内,有多少对i,j,满足i^(i+1)^(i+2)^...^j的值为给定的常数k.
阅读更多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,他有多 …
阅读更多