hdu 2227 Find the nondecreasing subsequences - c++编程基础

1 7 5
排序后： 1 5 7
对应原来的编号：1 3 2

依次遍历排序后的元素：对于元素 1 ：num[1] = 1;
对于元素 5 ：num[3] = num[1]+num[2] + 1 = 1+0 + 1 = 2
对于元素 2 ：num[2] = num[1] + 1 = 1 + 1 = 2
ans = num[1]+num[2]+num[3] = 5

这样就解决了元素出现的先后问题,而且也是离散化后把要处理的问题映射到了 1 到 N 这个区间,
但是还是没有说明元素的值一样却要对出现的顺序也排序。
其实到了这里，自己也应该想明白了，我还是再写下好了。

注意到：处理的过程不断的更新相应的 num[] 对应于树桩数组中快速更新元素值的思想。
num[index] = num[1]+...+num[index-1] + 1对应于树状数组快速求前缀和的思想。

对于情况一: 排序前后并未影响原来的顺序,所以可以直接把大的元素插在前面所有出现过的元素后面形成新的不下降子序列.
对于情况二: 加入了树状数组的思想其实是这样算的
num[1] = 1;
num[3] = num[1]+num[2] + 1 = 1+0+1 = 2;
num[2] = num[1] + 1 = 2 ;
ans = 1+2+2 = 5

所以：对于一样的元素, 先出现的一定要先处理

思路二：

不用定义结构体, 按照元素的值从小到大排序 ,然后对于重复元素的下标定义成一样的就可以了
比如说样例：
3
1 3 3
排序后的下标是： 1 2 2
而不是原来的：1 2 3 那么就不用纠结什么元素一样的时候,是先排前面的还是后面的问题了。
这样有两种方法处理, 但是效率没有思路一的高。具体看程序实现。

#include
#include
#include
#include
using namespace std;

const int maxn = 100000+10;
const int mod = 1000000007;
int c[maxn];
int n;

struct Node{
    int value; //对应元素的值
    int index; //元素初始编号
}node[maxn];

bool cmp(Node a, Node b) //先按元素值从小到大排序,元素值一样，再按照 编号从小到大排序
{
    if(a.value == b.value) return a.index < b.index;
    else return a.value < b.value;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int index, int value) //快速更新 ：节点 index 增加 value
{
    while(index <= n)
    {
        c[index] = (c[index]+value) % mod;
        index += lowbit(index);
    }
}

int sum(int index) //快速求前缀和
{
    int ret = 0;
    while(index > 0)
    {
        ret = (ret+c[index])%mod;
        index -= lowbit(index);
    }
    return ret; //勿忘
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        memset(node, 0, sizeof(node));
        memset(c, 0, sizeof(c));

        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &node[i].value);
            node[i].index = i;
        }
        sort(node+1, node+n+1, cmp); //排序

        int tmp = 0;
        for(int i = 1; i <= n; i++)
        {
            tmp = sum(node[i].index)+1; //求处理过后的前缀和相当于思路中的 num[index]
            tmp %= mod;
            add(node[i].index, tmp); // 相当于思路中给 num[index]增加 tmp

        }

        printf("%d\n", sum(n));
    }
    return 0;
}

hdu 2227 Find the nondecreasing subsequences (三)