cf1132G. Greedy Subsequences(线段树)
程序员文章站
2022-04-28 10:51:14
题意 "题目链接" Sol 昨天没想到真是有点可惜了。 我们考虑每个点作为最大值的贡献,首先预处理出每个位置$i$左边第一个比他大的数$l$,显然$[l + 1, i]$内的数的后继要么是$i$,要么在这一段区间中。那么可以对这段区间$+1$,然后每次查询$[i k + 1, i]$的最大值即可 c ......
题意
sol
昨天没想到真是有点可惜了。
我们考虑每个点作为最大值的贡献,首先预处理出每个位置\(i\)左边第一个比他大的数\(l\),显然\([l + 1, i]\)内的数的后继要么是\(i\),要么在这一段区间中。那么可以对这段区间\(+1\),然后每次查询\([i - k + 1, i]\)的最大值即可
#include<bits/stdc++.h> #define pair pair<int, int> #define mp(x, y) make_pair(x, y) #define fi first #define se second //#define int long long #define ll long long #define fin(x) {freopen(#x".in","r",stdin);} #define fout(x) {freopen(#x".out","w",stdout);} using namespace std; const int maxn = 4e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10; const double eps = 1e-9; template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;} template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;} template <typename a, typename b> inline ll add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;} template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);} template <typename a, typename b> inline ll mul(a x, b y) {return 1ll * x * y % mod;} template <typename a, typename b> inline void mul2(a &x, b y) {x = (1ll * x * y % mod + mod) % mod;} template <typename a> inline void debug(a a){cout << a << '\n';} template <typename a> inline ll sqr(a x){return 1ll * x * x;} inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, k, a[maxn], st[maxn], top, pre[maxn]; int root, ls[maxn], rs[maxn], tag[maxn], mx[maxn], ll[maxn], rr[maxn], tot, times; void ps(int &k, int v, int l, int r) { if(!k) k = ++tot, ll[k] = l, rr[k] = r; mx[k] += v; tag[k] += v; } void pushdown(int k, int l, int r) { if(!tag[k]) return ; int mid = l + r >> 1; ps(ls[k], tag[k], l, mid); ps(rs[k], tag[k], mid + 1, r); tag[k] = 0; } void update(int k) { mx[k] = max(mx[ls[k]], mx[rs[k]]); } void intadd(int &k, int l, int r, int ql, int qr, int v) { if(!k) k = ++tot, ll[k] = l, rr[k] = r; if(ql <= l && r <= qr) {ps(k, v, l, r); return ;} pushdown(k, l, r); int mid = l + r >> 1; if(ql <= mid) intadd(ls[k], l, mid, ql, qr, v); if(qr > mid) intadd(rs[k], mid + 1, r, ql, qr, v); update(k); } int query(int k, int l, int r, int ql, int qr) { if(!k) return 0; if(ql <= l && r <= qr) return mx[k]; pushdown(k, l, r); int mid = l + r >> 1; if(ql > mid) return query(rs[k], mid + 1, r, ql, qr); else if(qr <= mid) return query(ls[k], l, mid, ql, qr); else return max(query(ls[k], l, mid, ql, qr), query(rs[k], mid + 1, r, ql, qr)); } signed main() { n = read(); k = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = n; i; i--) { while(top && a[st[top]] <= a[i]) pre[st[top--]] = i; st[++top] = i; } while(top) pre[st[top--]] = 0; for(int i = 1; i <= n; i++) { intadd(root, 1, n, pre[i] + 1, i, 1); if(i >= k) cout << query(root, 1, n, i - k + 1, i) << " "; } return 0; }
上一篇: 走过老街区