1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
// 模板地址：https://github.com/elainafan/Algorithms
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lowbit(x) (x & (-x))
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define frep(i, x, y) for (int i = x; i >= y; i--)
#define all(x) (x).begin(), (x).end()
#define all2(x) (x).rbegin(), (x).rend()
#define sz(a) (int)a.size()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tri tuple<int, int, int>
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define pq priority_queue
#define umap unordered_map
#define mset multiset
using namespace std;
struct Info {
ll x;
Info(ll a = 0) : x(a) {}
};
Info operator+(const Info& a, const Info& b) {
Info c;
c.x = max(a.x, b.x);
return c;
}
template <typename T>
class SegmentTree {
int n;
vector<T> tree;
T merge_val(T a, T b) const { return a + b; } // 合并子树
void maintain(int node) { // 维护整棵树
tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
}
void build(const vector<T>& a, int node, int l, int r) {
if (l == r) {
tree[node] = a[l];
return;
}
int m = (l + r) / 2;
build(a, node * 2, l, m);
build(a, node * 2 + 1, m + 1, r);
maintain(node);
} // 建树
void update(int node, int l, int r, int i, T val) {
if (l == r) {
tree[node] = val;
return;
}
int m = (l + r) / 2;
if (i <= m)
update(node * 2, l, m, i, val);
else
update(node * 2 + 1, m + 1, r, i, val);
maintain(node);
} // 更新i处的值为val
T query(int node, int l, int r, int ql, int qr) const {
if (ql <= l && r <= qr) return tree[node];
int m = (l + r) / 2;
if (qr <= m) return query(node * 2, l, m, ql, qr);
if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
T l_res = query(node * 2, l, m, ql, qr);
T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
return merge_val(l_res, r_res);
} // 查询[ql,qr]的值
int find_first(int node, int l, int r, int ql, int qr, T val) const {
if (r < ql || l > qr) return -1;
if (tree[node] < val) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int res = find_first(node << 1, l, m, ql, qr, val);
if (res != -1) return res;
return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
} // 若遇到固定左端点的情况，需要使用全局变量（或者传入引用）记录前缀分段最大值，加一个被待求区间完全覆盖的剪枝
int find_last(int node, int l, int r, int ql, int qr, T val) const {
if (r < ql || l > qr) return -1;
if (tree[node] < val) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
if (res != -1) return res;
return find_last(node << 1, l, m, ql, qr, val);
}
public:
SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}
SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); } // 传入一个数组维护
void update(int i, T val) { update(1, 0, n - 1, i, val); } // 更新i的值为val
T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); } // 查询[ql,qr]的值
T get(int i) const { return query(1, 0, n - 1, i, i); } // 取出i处的值
int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); } // 查询[ql,qr]中第一个满足条件的下标
int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); } // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) {
cin >> a[i];
a[i]--;
}
map<int, vi> ma;
vi tem;
rep(i, 0, n - 1) {
if (0 <= a[i] && a[i] <= i) {
ma[a[i]].push_back(i - a[i]);
tem.push_back(i - a[i]);
}
}
if (ma.empty()) {
cout << 0 << endl;
return;
}
ranges::sort(tem);
tem.erase(unique(all(tem)), tem.end());
int m = sz(tem);
SegmentTree<Info> tree(m, Info(0));
int ans = 0;
for (auto& [x, y] : ma) {
vector<pii> tem2;
for (int& p : y) {
int tem3 = ranges::lower_bound(tem, p) - tem.begin();
int tem4 = tree.query(0, tem3).x + 1;
tem2.emplace_back(tem3, tem4);
ans = max(ans, tem4);
}
for (auto& [x, y] : tem2) {
tree.update(x, Info(max(tree.get(x).x, 1LL * y)));
}
}
cout << ans << endl;
return;
}
|
