标签：pii Monotonicity2 int res 1e6 mid POI2010MOT max

线段树 #dp #线段树优化dp #POI #Year2010

线段树维护 \(dp\) 转移即可

// Author: xiaruize
const int N = 1e6 + 10;

struct segment_tree
{
#define ls p << 1
#define rs p << 1 | 1

	pii mx[N << 2];

	void update(int p, int l, int r, int x, pii v)
	{
		if (l == r)
		{
			mx[p] = max(mx[p], v);
			return;
		}
		int mid = l + r >> 1;
		if (mid >= x)
			update(ls, l, mid, x, v);
		else
			update(rs, mid + 1, r, x, v);
		mx[p] = max(mx[ls], mx[rs]);
	}

	pii query(int p, int l, int r, int ll, int rr)
	{
		if (ll <= l && r <= rr)
			return mx[p];
		int mid = l + r >> 1;
		pii res = {0, 0};
		if (mid >= ll)
			res = max(res, query(ls, l, mid, ll, rr));
		if (mid < rr)
			res = max(res, query(rs, mid + 1, r, ll, rr));
		return res;
	}
} seg1, seg2;
int n, m;
int a[N], dp[N];
pii lst[N];
char op[N];
int pre[N];

void solve()
{
	cin >> n >> m;
	rep(i, 1, n) cin >> a[i];
	rep(i, 1, m) cin >> op[i];
	pii res = {0, 0};
	rep(i, 1, n)
	{
		pii p = max({seg1.query(1, 0, 1e6, 1, a[i] - 1), seg2.query(1, 0, 1e6, a[i] + 1, 1e6), lst[a[i]]});
		p.first++;
		dp[i] = p.first;
		pre[i] = p.second;
		p.second = i;
		res = max(res, p);
		// debug(p);
		int cur = (p.first - 1) % m + 1;
		if (op[cur] == '<')
			seg1.update(1, 0, 1e6, a[i], p);
		else if (op[cur] == '>')
			seg2.update(1, 0, 1e6, a[i], p);
		else
			lst[a[i]] = max(lst[a[i]], p);
	}
	vector<int> vec;
	int x = res.second;
	while (x)
	{
		vec.push_back(x);
		x = pre[x];
	}
	reverse(ALL(vec));
	cout << res.first << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签：pii,Monotonicity2,int,res,1e6,mid,POI2010MOT,max
From： https://www.cnblogs.com/xiaruize/p/18142213