HDU 2227 Find the nondecreasing subsequences dp思想 + 树状数组

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int MOD = ;
const int maxn = + ;
LL a[maxn], b[maxn];
int n;
LL c[maxn];
LL lowbit(LL x) {
return x & (-x);
}
void UpDate(int pos, LL val) {
while (pos <= n) {
c[pos] += val;
if (c[pos] >= MOD) c[pos] %= MOD;
pos += lowbit(pos);
}
}
LL query(int pos) {
LL ans = ;
assert(pos >= );
while (pos) {
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}
void work() {
memset(c, , sizeof c);
for (int i = ; i <= n; ++i) {
cin >> a[i];
b[i] = a[i];
}
sort(b + , b + + n);
LL ans = ;
for (int i = ; i <= n; ++i) {
int pos = lower_bound(b + , b + + n, a[i]) - b;
LL tans = query(pos) + ;
ans += tans;
if (ans >= MOD) ans %= MOD;
UpDate(pos, tans);
}
cout << ans << endl;
}int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
while (cin >> n) work();
return ;
}