离散对数（Discrete Logarithm）问题是这样一个问题，它是对于模方程

a^x=b(mod prime)，求满足条件的X，或者得出不存在这样的X

最暴力的思路，那么就是枚举x? 根据费马小定理，只需要枚举[0,p-1)

题目链接 题意：给出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 的点有多少个。 思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。