hdu 3030 Increasing Speed Limits（树状数组求最长上升子序列）(二)
存也应
该更少才对，修改代码如下：
[cpp]
#include
#include
#include
#include
#include
#define MOD 1000000007
#define MAXN 500005
using namespace std;
int num[MAXN], A[MAXN], c[MAXN], seq[MAXN], cnt;
inline int lowbit(int x)
{
return x & -x;
}
//这里的update是正常的
inline void update(int pos, int val)
{
for (int i = pos; i <= cnt; i += lowbit(i))
{
c[i] += val;
if (c[i] >= MOD)
c[i] %= MOD;
}
}
inline int getsum(int pos)
{
int s = 0;
for (int i = pos; i > 0; i -= lowbit(i))
{
s += c[i];
if (s >= MOD)
s %= MOD;
}
return s;
}
int main()
{
int T, n, m;
long long X, Y, Z, res;
scanf("%d", &T);
for (int ca = 1; ca <= T; ++ca)
{
res = 0;
mapmp;
scanf("%d %d %I64d %I64d %I64d", &n, &m, &X, &Y, &Z);
memset(c, 0, sizeof (c));
for (int i = 0; i < m; ++i)
{
scanf("%d", &A[i]);
}
for (int i = 0; i < n; ++i)
{
num[i+1] = A[i%m];
seq[i] = num[i+1];
A[i%m] = (X*A[i%m]+Y*(i+1))%Z;
}
//其中num和seq保存的值是一模一样的
sort(num+1, num+1+n);
//去除临近元素，cnt表示的是一共有多少个不同的元素
//这里进行的是离散化的操作，对于最长上升子序列来说，相同元素是毫无意义的
cnt = unique(num+1, num+1+n) - (num+1);
for (int i = 0; i < n; ++i)
{ //注意这里是累加，而上边的代码中是取最大值
A[i]=lower_bound(num+1,num+cnt+1,seq[i])-num-1;
long long x = getsum(A[i])+1;
res += x;
if (res > MOD)
res %= MOD;
//给下一个位置上update时的值是x
update(A[i]+1, x);
}
printf("Case #%d: %I64d\n", ca, res);
}
return 0;
}
这样的话仅仅需要2703MS，但是内存只减少了80B，额，看来stl中的map做得好牛逼。。。
还得注意下，求最长上升子序列和求子序列个数的时候，BIT中的update和getsum各不相同，要说起解释来呢，也不知该怎么解释，可能对BIT
的理解还不够深刻，一个是求最大值，一个是求和，所以update和getsum的时候各不相同。希望哪位大神能详细的解释下。