基础数据离散化

ACM
评论

大量数据离散化处理

需要注意的是，这里的离散化指的是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。当然在程序实现上，个体也不可能是无限的。
这里分两种情况讨论，对于无重数组和有重数组。

无重离散化

无重离散化的局限性在于在排序的时候对于相同数值的数据会给出不同rank,导致离散化失效，好处在于它写法简洁。产生的b数组对解题有有一定和帮助。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long ll;
ll a[maxn];
int b[maxn],r[maxn],n;
int cmp(int x,int y)
{
    return a[x]<a[y];
}
void discrete()
{
    sort(b,b+n,cmp);
    for(int i=0;i<n;i++)
        r[b[i]]=i;
}

有重离散化

有重离散化的时间效率不及无重离散化的地方在于lower_bound()的二分查找。空间效率的复杂度由于cpy数组的引入而增高。可以顺便建立个index数组来索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef long long ll;
ll a[maxn],cpy[maxn],index[maxn];
int r[maxn],n;
void discrete()
{
    mec(cpy,a);
    sort(cpy,cpy+n);
    int tot=unique(cpy,cpy+n)-cpy;
    for(int i=0;i<n;i++)
    {
        r[i]=lower_bound(cpy,cpy+tot,a[i])-cpy;
        index[r[i]]=a[i];
    }
}

单个大值数据离散化处理

离散数学高深莫测，在此我仅逼逼一些皮毛。对于整块的连续数据，可以通过把其拆分成多个数据段，对于不同的运算需求可以选择不同的拆分方式来简化运算是离散化的目的。在程序设计中，常见的离散化方法是按照二进制来处理数据。

树状数组

树状数组是针对于一个数组数据的和的数据结构。基本思想就是把一个大的数据(前i个数据和）按照二进制高度(最低位1所在位置）打包储存在i之前的数据中。
把大块数据离散地储存在一个树状数组的结构中可批量更新区间数据，查询单点数据。

树状数组由于它的特殊性质，对于维护整段数值的同一个性质（比如最值）表现良好。详见cf486E。注意，这里是从初始位置到询问位置的性质，对于起点不定的区间，线段树显然更加优越。(比较可见 HDU 1754.)
PS：
线段树也是一种利用二进制处理数据的类型结构，但它用到的思想不是离散化，在此我暂且不深度挖掘。

于是让我们利用树状数组维护最大值来做一发最长上升子序列poj 2533。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
#define debug puts("--------")
#define mx 100050
#define mem(x,y) memset(x,y,sizeof(x))
int c[mx];
int f[mx],b[mx],sum[mx];
int n;
int a[mx];
int lb(int x){return x&(-x);}
int sumf(int x)
{
    int ans=0;
    while(x>0)
    {
        ans=max(ans,c[x]);
        x-=lb(x);
    }
    return ans;
}
int sumb(int x)
{
    int ans=0;
    while(x<mx)
    {
        ans=max(ans,c[x]);
        x+=lb(x);
    }
    return ans;
}
void updatef(int i,int x)
{
    while(i<mx)
    {
        c[i]=max(c[i],x);
        i+=lb(i);
    }
}
void updateb(int i,int x)
{
    while(i>0)
    {
        c[i]=max(c[i],x);
        i-=lb(i);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",a+i);
    int len=0;
    mem(c,0);
    for(int i=0;i<n;i++)
    {
        a[i]+=2;
        f[i]=sumf(a[i]-1);
        updatef(a[i],f[i]+1);
    }
    mem(c,0);
    for(int i=n-1;i>=0;i--)
    {
        b[i]=sumb(a[i]+1);
        updateb(a[i],b[i]+1);
        sum[i]=b[i]+f[i];
        len=max(sum[i],len);
    }
  printf("%d\n",len+1);
}

对，就是这样做的。c数组储存的是值为i的数对应的前缀LIS长度，以及后来用来储存后缀LIS长度，然后求和找最大值。很容易看出其局限性，只能从固定起点开始搜索，比如类似前缀后缀的问题，线段树对这个局限性有很好的解决。

快速运算法

对于快速运算法，之所以在原运算上得到了优化，在于这些运算把原来整块数据按照二进制进行了拆分，对于有值的数据段进行运算，无值的数据段进行平移。常用的有快速幂，快速模，快速乘法，矩阵快速幂等，都是很经典的按照二进制拆分优化。贴模板不是我想做的，上述算法大家想必也十分熟悉。
啊，还是来两发吧。

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct matrix
{
    int arr[arr_size][arr_size];
    int r,c;
};
matrix multi(matrix a,matrix b)
{
   matrix c;
    mem(c.arr,0);
    c.r=a.r;
    c.c=b.c;
    for(int i=1;i<=a.r;i++)
        for(int j=1;j<=b.c;j++)
    {
       for(int k=1;k<=a.c;k++)
        c.arr[i][j]=(c.arr[i][j]+a.arr[i][k]%mod*b.arr[k][j]%mod)%mod;
    }
    return c;
}
matrix qpow(matrix a,int k)
{
    matrix res;
    init(res);
    while(k)
    {
        if(k&1)res=multi(res,a);
        k>>=1;
        a=multi(a,a);
    }
    return res;
}

给出的矩阵乘法是普适乘法，所以在初始化的时候注意r,c的初始化。然而在快速幂实现的时候，矩阵一定是正方矩阵，所以可以进行优化。

快速乘法+快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ll qmult(ll a,ll b)//ORZ
{
    return (a*b-(ll)(a/(long double)M*b+1e-3)*M+M)%M;
}
ll qmulti(ll a,ll b)
{
    a%=M;
    ll res=0;
    while(b)
    {
        if(b&1)res=(res+a)%M;
        b>>=1;
        a=(a+a)%M;
    }
    return res;
}
ll qpow(ll a,ll b)
{
    if(b<0)return 0;
    ll ret=1;
    a%=M;
    for(;b;b>>=1,a=qmulti(a,a)%M)
        if(b&1)
        ret=qmulti(ret,a)%M;
    return ret;
}

快速乘法是个很着急的玩意儿，慎用。使用于处理mod长整型变量的场合。

*EOF