分块

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

题目链接 题意：给出n个数，然后m个询问，每个询问一个区间[l,r],问该区间中不同的数有多少个。

http://www.lydsy.com/JudgeOnline/problem.php?id=2002 题意+思路： 同codeforces 13 E holes. 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月21日 星期日 02时29分39秒 4File Name :code/bzoj/2002.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E5+7; 34int n,m; 35int siz = 450; //sqrt(2E5) 36int a[N]; 37int pos[N]; 38int cnt[N]; 39int nxt[N]; 40int end[N]; 41 42 43void go( int x) 44{ 45 int ans = 0 ; 46 while (1) 47 { 48 if (x>=n) 49 { 50 printf("%d\n",ans); 51 break; 52 } 53 ans +=cnt[x]; 54 x = nxt[x]; 55// cout<<"nxt[x]:"<<nxt[x]<<endl; 56 } 57} 58void update ( int i,int j) 59{ 60 if (j>=n) 61 { 62 cnt[i]=1; 63 nxt[i]=n; 64 end[i]=i; 65 } 66 else 67 { 68 if (pos[i]==pos[j]) 69 { 70 cnt[i] = cnt[j] + 1; 71 nxt[i] = nxt[j]; 72 end[i]=end[j]; 73 } 74 else 75 { 76 cnt[i] = 1; 77 nxt[i] = j; 78 end[i] = end[j]; 79 } 80 } 81} 82int main() 83{ 84 #ifndef ONLINE_JUDGE 85 freopen("code/in.txt","r",stdin); 86 #endif 87 88 scanf("%d",&n); 89 for ( int i = 0 ; i < n ;i++) 90 { 91 scanf("%d",&a[i]); 92 pos[i] = i/siz; 93 } 94 95 for ( int i = n - 1 ; i >= 0 ; i--) update(i,i+a[i]); 96 97 scanf("%d",&m); 98 while (m--) 99 { 100 int opt; 101 scanf("%d",&opt); 102 if (opt==1) 103 { 104 int x; 105 scanf("%d",&x); 106 go(x); 107 } 108 else 109 { 110 int x,y; 111 scanf("%d %d",&x,&y); 112 a[x]=y; 113 update(x,x+a[x]); 114 int p = pos[x]*siz; 115 for ( int i = x-1 ; i >= p ; i--) update(i,i+a[i]); 116 } 117 } 118 119 #ifndef ONLINE_JUDGE 120 fclose(stdin); 121 #endif 122 return 0; 123}

http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来

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大小的布尔数组即可（我竟然傻逼得去用set….然后华丽丽得TLE了2333）

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要块很多==

2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Submit: 5327 Solved: 2461 [Submit][Status][Discuss] Description

http://acm.hdu.edu.cn/showproblem.php?pid=4391 题意：有 n 个点，每个点有一种颜色（可能相同），两种操作：1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。 思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。

http://acm.hdu.edu.cn/showproblem.php?pid=1754 题意：给定一个区间，有m组操作，操作可以是改变单点，或者查询区间最大值。对于每组查询，输出。 思路：分块。这篇博客说得很不错。http://www.cnblogs.com/sweetsc/archive/2012/08/15/2639395.html

初识分快. 引一段题解： Let’s split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let’s number them from left to right. We’re going to pass through points rectangle by rectangle. Inside the rectangle we’re going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it’s odd.