FZU 2236离散化树状数组如何高效实现？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1259个文字，预计阅读时间需要6分钟。
【离散化】+ 借此题目记录一下离散化。离散化：当主题数据很大时，但数值的个数不多，可以采用离散化，降低数值，便于计算。例如数列{89, 14, 9, 1000, 2}；离散化后：{4, 3, 2, 5, 1}；（此处省略）
借此题记一下离散化。离散化：当题目数据很大时，但数的个数不多，可以采用离散化，降低数值，便于计算。
例如数列{ 89, 14, 9, 1000, 2 }；离散化后：{ 4, 3, 2, 5, 1 }；（此操作后，数值整体降低，甚至可以当数组下标使用了）
具体操作参见本题代码。
离散化三部曲：
1. 数组 ha[] 存储所有存在过的数据，sort排序
2. 对ha数组进行去重，重复的数据只保留一个。unique去重（unique函数前提有序）
3. 查询某个数字离散化之后对应的数字，lower_bound查排名
vjudge.net/contest/209548
Problem 2236 第十四个目标
Accept: 159Submit: 523
Time Limit: 1000 mSecMemory Limit : 32768 KB
Problem Description
目暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算，柯南追踪伤害阿笠博士的凶手，根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经过一系列的推理后，柯南发现受害者的名字均包含扑克牌的数值，且扑克牌的大小是严格递增的，此外遇害者与毛利小五郎有关。
为了避免下一个遇害者的出现，柯南将可能遭到暗算的人中的数字按关联程度排列了出来，即顺序不可改变。柯南需要知道共有多少种可能结果，满足受害人名字出现的数字严格递增，但是他柯南要找出关键的证据所在，所以这个任务就交给你了。
(如果你看不懂上面在说什么，这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。)
Input
多组数据(<=10)，处理到EOF。
第一行输入正整数N(N≤100 000)，表示共有N个人。
第二行共有N个整数Ai(1≤Ai≤10^9)，表示第i个人名字中的数字。
Output
每组数据输出一个整数，表示所有可能的结果。由于结果可能较大，对1 000 000 007取模后输出。
Sample Input
3
1 3 2
Sample Output
5
Source
：
题意求严格递增子序列的个数。如果你会用树状数组求序列逆序对的个数，那就能理解这个题，是在求：正序子序列的个数。
而逆序对就是逆序长度为2的子序列 个数。
设数组dp[i]表示以数字i结尾时，递增子序列的个数。那么dp[i] = sum(dp[j]) j属于[1,i-1]，即i可以接在这样的j后面形成递增。
扫描数列a，当前为a[i],，那么dp[a[i]] = 所有dp[j]之和，j<a[i]。
但是所有dp[j]之和，暴力计算很容易超时，所以用树状数组维护，即下面代码中的c数组
还有一个关键问题，数字太大10^9，不能当数组c的下标，所以要离散化！
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=303030;
const int mod=1e9+7;
int a[N],n,ha[N];
ll c[N];
inline ll MOD(ll u,ll v){return ((u+v)%mod+mod)%mod;}
void add(int k,ll num)
{
for(;k<=n;k+=k&-k)
c[k]=MOD(num,c[k]);
}
ll read(int k)
{
ll res=0;
for(;k;k-=k&-k)
res=MOD(res,c[k]);
return res;
}
int main()
{
while(cin>>n)
{
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),ha[i]=a[i];
sort(ha+1,ha+n+1);
int top=unique(ha+1,ha+n+1)-ha-1;
for(int i=1;i<=n;i++)
{
int t=lower_bound(ha+1,ha+top+1,a[i])-ha;
add(t,read(t-1)+1);
}
cout<<read(top)<<endl;
}
}
本文共计1259个文字，预计阅读时间需要6分钟。
【离散化】+ 借此题目记录一下离散化。离散化：当主题数据很大时，但数值的个数不多，可以采用离散化，降低数值，便于计算。例如数列{89, 14, 9, 1000, 2}；离散化后：{4, 3, 2, 5, 1}；（此处省略）
借此题记一下离散化。离散化：当题目数据很大时，但数的个数不多，可以采用离散化，降低数值，便于计算。
例如数列{ 89, 14, 9, 1000, 2 }；离散化后：{ 4, 3, 2, 5, 1 }；（此操作后，数值整体降低，甚至可以当数组下标使用了）
具体操作参见本题代码。
离散化三部曲：
1. 数组 ha[] 存储所有存在过的数据，sort排序
2. 对ha数组进行去重，重复的数据只保留一个。unique去重（unique函数前提有序）
3. 查询某个数字离散化之后对应的数字，lower_bound查排名
vjudge.net/contest/209548
Problem 2236 第十四个目标
Accept: 159Submit: 523
Time Limit: 1000 mSecMemory Limit : 32768 KB
Problem Description
目暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算，柯南追踪伤害阿笠博士的凶手，根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经过一系列的推理后，柯南发现受害者的名字均包含扑克牌的数值，且扑克牌的大小是严格递增的，此外遇害者与毛利小五郎有关。
为了避免下一个遇害者的出现，柯南将可能遭到暗算的人中的数字按关联程度排列了出来，即顺序不可改变。柯南需要知道共有多少种可能结果，满足受害人名字出现的数字严格递增，但是他柯南要找出关键的证据所在，所以这个任务就交给你了。
(如果你看不懂上面在说什么，这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。)
Input
多组数据(<=10)，处理到EOF。
第一行输入正整数N(N≤100 000)，表示共有N个人。
第二行共有N个整数Ai(1≤Ai≤10^9)，表示第i个人名字中的数字。
Output
每组数据输出一个整数，表示所有可能的结果。由于结果可能较大，对1 000 000 007取模后输出。
Sample Input
3
1 3 2
Sample Output
5
Source
：
题意求严格递增子序列的个数。如果你会用树状数组求序列逆序对的个数，那就能理解这个题，是在求：正序子序列的个数。
而逆序对就是逆序长度为2的子序列 个数。
设数组dp[i]表示以数字i结尾时，递增子序列的个数。那么dp[i] = sum(dp[j]) j属于[1,i-1]，即i可以接在这样的j后面形成递增。
扫描数列a，当前为a[i],，那么dp[a[i]] = 所有dp[j]之和，j<a[i]。
但是所有dp[j]之和，暴力计算很容易超时，所以用树状数组维护，即下面代码中的c数组
还有一个关键问题，数字太大10^9，不能当数组c的下标，所以要离散化！
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=303030;
const int mod=1e9+7;
int a[N],n,ha[N];
ll c[N];
inline ll MOD(ll u,ll v){return ((u+v)%mod+mod)%mod;}
void add(int k,ll num)
{
for(;k<=n;k+=k&-k)
c[k]=MOD(num,c[k]);
}
ll read(int k)
{
ll res=0;
for(;k;k-=k&-k)
res=MOD(res,c[k]);
return res;
}
int main()
{
while(cin>>n)
{
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),ha[i]=a[i];
sort(ha+1,ha+n+1);
int top=unique(ha+1,ha+n+1)-ha-1;
for(int i=1;i<=n;i++)
{
int t=lower_bound(ha+1,ha+top+1,a[i])-ha;
add(t,read(t-1)+1);
}
cout<<read(top)<<endl;
}
}