【题解】[JOI Open 2021] Financial Report

本文主要是介绍【题解】[JOI Open 2021] Financial Report，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

首先考虑 \(D = n\) 的情况，有方程 \(f_i = \max\limits_{j < i\land a_j<a_i}\{f_j + 1\}\)​。

对于 \(D\) 的限制，我们对每个位置计算 \(p_i\) 表示从 \(i\) 开始，每次最多向前跳 \(D\) 格，只能跳到 \(\le a_i\) 的格子上，能够到达的最小格子。显然这可以直接用 set + 并查集维护。

那么我们方程修改为 \(f_i = \max\limits_{p_i\le j < i\land a_j<a_i}\{f_j + 1\}\)​。直接用线段树优化 DP 即可，时间复杂度 \(\mathcal{O}(N\log N)\)。

/*
    Author : SharpnessV
    Right Output ! & Accepted !
*/
#include<bits/stdc++.h>
//#define int long long

#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define pre(i, a, b) for(int i = (a);i >= (b);i--)
#define rp(i, a) for(int i = 1; i <= (a); i++)
#define pr(i, a) for(int i = (a); i >= 1; i--)
#define go(i, x) for(auto i : x)

#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ze(p) memset(p, 0, sizeof(p))
#define mem(p, x) memset(p, x, sizeof(p))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define si(x) (int)(x).size()
#define db cerr
#define pc putchar
#define gc getchar
#define el putchar('\n')

using namespace std;
const double eps = 1e-15, pi = 3.1415926535897932385;
typedef long long LL;
typedef pair<int,int> Pr;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}, inf = 0x7fffffff;
//Author : SharpnessV
//#define main Solution
//char buf[1<<22],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x = 0;bool f = 1;char ch = gc();
    while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = gc();
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    if(f)return x;return -x;
}
inline LL Read(){
    LL x = 0;bool f = 1;char ch = gc();
    while(!isdigit(ch))f = ('-' == ch ? 0 : 1), ch = gc();
    while(isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    if(f)return x;return -x;
}
int gcd(int x,int y){return y ? gcd(y, x % y) : x;}
int lcm(int x,int y){return x / gcd(x, y) * y;}
#define P 1000000007
//#define P 998244353
#define bas 229
inline void ad(int &x, int y){x += y; if(x >= P) x -= P;}
inline void su(int &x, int y){x -= y; if(x < 0) x += P;}
inline void cmn(int &x,int y){if(y < x) x = y;}
inline void cmx(int &x,int y){if(y > x) x = y;}
inline void cmn(LL &x, LL y){if(y < x) x = y;}
inline void cmx(LL &x, LL y){if(y > x) x = y;}

int Pow(int x, int y){
	if(y < 0)return Pow(Pow(x, P - 2), -y);
	int now = 1 ;
	for(;y;y >>= 1, x = 1LL * x * x % P)if(y & 1) now = 1LL * now * x % P;
	return now;
}

/*******************************************************************************************************************/
/*                                                                                                                 */
/*******************************************************************************************************************/

#define N 300005

int n, m, u[N], fa[N], f[N], b[N], T;
int get(int x){return fa[x] == x ? x : fa[x] = get(fa[x]);}
set<int>s;vector<int>c[N];

struct node{
	int l, r, val;
}a[N << 2];
#define L a[x].l
#define R a[x].r
#define ls (x << 1)
#define rs (ls | 1)
#define S a[x].val

void build(int x,int l,int r){
	L = l, R = r, S = 0xcfcfcfcf;
	if(l == r)return;
	int mid = (l + r) >> 1;
	build(ls, l, mid), build(rs, mid + 1, r);
}

void ins(int x,int pos,int val){
	if(L == R)S = val;
	else{
		int mid = (L + R) >> 1;
		if(mid >= pos)ins(ls, pos, val);
		else ins(rs, pos, val);
		S = max(a[ls].val, a[rs].val);
	}
}

int ask(int x,int l,int r){
	if(L >= l && R <= r)return S;
	int mid = (L + R) >> 1, cur = 0xcfcfcfcf;
	if(mid >= l)cmx(cur, ask(ls, l, r));
	if(mid < r)cmx(cur, ask(rs, l, r));
	return cur;
}

int main(){
	//int T = read();while(T--)solve();
	n = read(), m = read();
	rp(i, n)b[i] = u[i] = read(), fa[i] = i;
	sort(b + 1, b + n + 1), T = unique(b + 1, b + n + 1) - b - 1;
	rp(i, n)u[i] = lower_bound(b + 1, b + T + 1, u[i]) - b, c[u[i]].pb(i);
	rp(i, T){
		go(x, c[i]){
			auto k = s.lower_bound(x);
			if(k != s.end() && x + m >= *k && fa[*k] > x)fa[*k] = x;
			if(k != s.begin()){
				k--;if(*k + m >= x)fa[x] = *k;
			}s.insert(x);
		}
		go(x, c[i])f[x] = get(x);
	}
	build(1, 1, n);
	rp(i, T){
		go(x, c[i])u[x] = max(1, ask(1, f[x], x) + 1);
		go(x, c[i])ins(1, x, u[x]);
	}
	printf("%d\n",a[1].val);
	return 0;
}

这篇关于【题解】[JOI Open 2021] Financial Report的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！