技巧——离散化

离散化

定义

离散化，就是把无限空间中有限的个体映射到有限的空间中去，以提高算法的时空效率。”

很多算法的复杂度与数据中的最大值有关，比如树状数组和纯用数组实现的一对一标记。时常会遇到这种情况：数据的范围非常大或者其中含有负数，但数据本身的个数并不是很多（远小于数据范围）。在这种情况下，如果每个数据元素的具体值并不重要，重要的是他们之间的大小关系的话，我们可以先对这些数据进行离散化，使数据中的最大值尽可能小且保证所有数据都是正数。

例如，有这样一个长为5的序列：102131511，123，9813186，-611，55。其中有非常大的数以及负数，会给许多算法的实现带来困扰，我们可以把这个序列离散化，使它变成这样：5，3，4，1，2。各个元素间的大小关系没有任何改变，但数据的范围一下子就变得很舒服了。

离散化的原理和实现都很简单。为了确保不出错且尽可能地提高效率，我们希望离散化能实现以下几种功能：1.保证离散化后的数据非负且尽可能的小2.离散化后各数据项之间的大小关系不变，原本相等的也要保持相等。由此，找出数据项在原序列中从小到大排第几就是离散化的关键。

可以通过下面的方法以O(nlong)的时间复杂度完成离散化，n为序列长度。

对原序列进行排序，使其按升序排列。
去掉序列中重复的元素。
此时序列中各位置的值和位置的序号就是离散化的映射方式。

例如：

a[x]值得范围为1-1e9，但其中的数字个数只有1e5个

那么如果我们需要开标记数组就需要1e9的空间，可将其离散化至1e5后，只需要开1e5的空间即可。

代码如下：

 1 int n, a[maxn], t[maxn];
 2 //这里以下标1为序列的起点，一般情况下从0开始也可以
 3 for(int i = 1;i <= n;i++)
 4 {
 5     scanf("%d", &a[i]);
 6     t[i] = a[i];//t是一个临时数组，用来得到离散化的映射关系
 7 }
 8 //下面使用了STL中的sort(排序)，unique(去重)，lower_bound(查找)函数
 9 sort(t + 1, t + n + 1);//排序
10 int m = unique(t + 1, t + 1 + n) - t - 1;//去重，并获得去重后的长度m
11 for(int i = 1;i <= n;i++)
12 {
13     a[i] = lower_bound(t + 1, t + 1 + m, a[i]) - t;//通过二分查找，快速地把元素和映射对应起来
14 }

奶牛抗议

题目描述

约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字可正可负。

约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。

约翰想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。

输入输出格式

输入格式：

• 第一行：单个整数N，1 ≤ N ≤ 100000

• 第二行到第N + 1 行：第i + 1 行有一个整数Ai，−10^5 ≤ Ai ≤ 10^5

输出格式：

单个整数：表示分组方案数模1000000009 的余数

输入输出样例

输入样例#1：

输出样例#1：

说明

解释:如果分两组，可以把前三头分在一组，或把后三头分在一组；如果分三组，可以把中间两头分在一组，第一和最后一头奶牛自成一组；最后一种分法是把四头奶牛分在同一组里。

思路

我们令

我们发现，这个问题演变成为一个求顺序对的问题，我们使用树状数组解决。

 1 //
 2 #include<stdio.h>
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 #define ll long long
 6 ll a[100005],b[100005],sum[100005],c[100005];//b为sum的离散化对应数组 
 7 int n,cnt,ans;
 8 void modify(int x,ll d)
 9 {
10     for(x;x<=n+1;x+=x&-x)
11         c[x]=(c[x]+d)%1000000009;
12 }
13 ll getsum(int x)
14 {
15     ll sum=0;
16     for(x;x;x-=x&-x)
17         sum=(sum+c[x])%1000000009;
18     return sum;
19 }
20 int main()
21 {
22     cin>>n;
23     for(int i=1;i<=n;i++)
24     {
25         cin>>a[i];
26         sum[i]=sum[i-1]+a[i],b[i]=sum[i];
27     }
28     sort(b+1,b+1+n);
29     cnt=unique(b,b+1+n)-b;
30     ans=0;
31     for(int i=1; i<=n; i++)
32         if(sum[i]>=0)
33         {
34             int x=lower_bound(b+1,b+1+cnt,sum[i])-b;
35             ll tmp=getsum(x)+1;
36             modify(x,tmp);
37             if(i==n)ans=tmp;
38         }
39     cout<<ans;
40     return 0;
41 }