1.Problem
https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_h
2.Idea
Using BIT Max Range Query
3.Source
const int N = 100005;
//////////////////////////////
class BIT { //1 -indexed
const int n;
vector<Int> bit;
public:
BIT(int _n = 0) : n(_n), bit(n + 1, 0) {}
void add(int i, const Int x = 1) { for (i++; i <= n; i += i&-i) bit[i] += x; }
Int sum(int i) { Int x = 0; for (i++; i; i -= i & -i) x += bit[i]; return x; }
Int sum(int i, int j) { return sum(j) - sum(i - 1); }
};
struct FenwickTreeMin {
vector<int> bit; //0 -indexed
int n;
const int INF = (int)1e9;
FenwickTreeMin(int n) {
this->n = n;
bit.assign(n, INF);
}
FenwickTreeMin(vector<int> a) : FenwickTreeMin(a.size()) {
for (size_t i = 0; i < a.size(); i++)
update(i, a[i]);
}
int getmin(int r) {
int ret = INF;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret = min(ret, bit[r]);
return ret;
}
void update(int idx, int val) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] = min(bit[idx], val);
}
};
struct FenwickTreeMax {
vector<int> bit; // 0 - indexed
int n;
FenwickTreeMax(int n) {
this->n = n;
bit.assign(n, -INF);
}
FenwickTreeMax(vector<int> a) : FenwickTreeMax(a.size()) {
for (size_t i = 0; i < a.size(); i++)
update(i, a[i]);
}
int getMax(int r) {
int ret = -INF;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret = max(ret, bit[r]);
return ret;
}
void update(int idx, int val) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] = max(bit[idx], val);
}
};
int n;
int a[N];
void solve()
{
cin >> n;
REP(i, n) cin >> a[i];
map<int, int> mp;
REP(i, n) mp[a[i]] = 0;
int i = 0;
for (auto it = mp.begin(); it != mp.end(); it++) {
it->second = i;
i++;
}
FenwickTreeMax ftm(n);
REP(i, n) {
int cur = mp[a[i]];
int tmp = ftm.getMax(cur - 1);
if(tmp == -INF) ftm.update(cur, 1);
else ftm.update(cur, tmp + 1);
}
cout << ftm.getMax(n - 1) << endl;
}
