分块

离散对数（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 <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=3E4+7; 32const int M=2E5+7; 33int n,Q; 34int a[N]; 35int tree[N<<2]; 36map<int,int>mp; 37struct node 38{ 39 int l,r; 40 int id; 41 bool operator < (node b)const 42 { 43 if (r==b.r) return l<b.l; 44 return r<b.r; 45 } 46}q[M]; 47void PushUp( int rt) 48{ 49 tree[rt] = tree[rt<<1] + tree[rt<<1|1]; 50} 51void update( int p,int sc,int l,int r ,int rt) 52{ 53 if (l==r) 54 { 55 tree[rt]+=sc; 56 return; 57 } 58 int m = (l+r)>>1; 59 if (p<=m) update(p,sc,lson); 60 else update(p,sc,rson); 61 PushUp(rt); 62} 63int query(int L,int R,int l,int r,int rt) 64{ 65 if (L<=l&&r<=R) return tree[rt]; 66 int m = (l+r)>>1; 67 int ret = 0 ; 68 if (L<=m) ret += query(L,R,lson); 69 if (R>=m+1) ret+=query(L,R,rson); 70 return ret; 71} 72int ans[M]; 73int main() 74{ 75 #ifndef ONLINE_JUDGE 76 freopen("code/in.txt","r",stdin); 77 #endif 78 cin>>n; 79 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); 80 cin>>Q; 81 for ( int i = 1 ; i <= Q ; i++) scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i ; 82 sort(q+1,q+Q+1); 83 int cur = 1; 84 for ( int i = 1 ; i <= Q ; i++) 85 { 86 for ( ; cur <= q[i].r ; cur++) 87 { 88 if (mp[a[cur]]) update(mp[a[cur]],-1,1,n,1); 89 mp[a[cur]] = cur; 90 update(mp[a[cur]],1,1,n,1); 91 } 92 ans[q[i].id] = query(q[i].l,q[i].r,1,n,1); 93 } 94 for ( int i = 1 ; i <= Q ; i++) printf("%d\n",ans[i]); 95 #ifndef ONLINE_JUDGE 96 fclose(stdin); 97 #endif 98 return 0; 99} 之后补一个主席树的做法

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个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来 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大小的布尔数组即可（我竟然傻逼得去用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 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

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. Let’s calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we’re passing 1000 rectangles from0 to 106, 109 in total. By x-coordinate we’re spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 109 + 2000000 in total, which perfectly fits.