首页 > 其他分享 >P4093 序列 题解

P4093 序列 题解

时间:2024-10-07 09:10:49浏览次数:8  
标签:P4093 int 题解 rep mid cin Item 序列 id

Statement

给出 \(n\) 个数的序列 \(\{a_i\}\),接下来 \(m\) 秒中每一秒会有一个数发生变化,然后恢复。

问最长的子序列长度,使得任意时刻这个子序列不下降。\(n\le 10^5\)

Solution

设 \(b_i\) 为 \(i\) 最小能变成的数,\(c_i\) 为 \(i\) 最大能变成的数

\[ f(i)=\max_{j<i\land c_j\le a_i\land a_j\le b_i}\{f(j)\}+1 \]

分治即可,\(O(n\log^2 n)\)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 2e5 + 10;
int n, m, ans;
struct Item {
	int a, b, c, f, id;
} a[N];

struct BIT {
	int mx[N];
	void Upd(int x, int v) {
		for (; x <= 100000; x += x & -x) mx[x] = max(mx[x], v);
	}
	int Qry(int x) {
		int res = 0;
		for (; x; x -= x & -x) res = max(res, mx[x]);
		return res;
	}
	void Clear(int x) {
		for (; x <= 100000; x += x & -x) mx[x] = 0;
	}
} bit;

void Solve(int l, int r) {
	if (l == r) return (void)(ans = max(ans, a[l].f));
	int mid = (l + r) >> 1;
	Solve(l, mid);
	sort(a + l, a + mid + 1, [&](Item l, Item r) { return l.c < r.c; });
	sort(a + mid + 1, a + r + 1, [&](Item l, Item r) { return l.a < r.a; });
	for (int j = l, i = mid + 1; j <= mid || i <= r; ) {
		if (j <= mid && (a[j].c <= a[i].a || i > r)) {
			bit.Upd(a[j].a, a[j].f), ++j;
		} else {
			a[i].f = max(a[i].f, bit.Qry(a[i].b) + 1), ++i;
		}
	}
	rep(i, l, mid) bit.Clear(a[i].a);
	sort(a + l, a + r + 1, [&](Item l, Item r) { return l.id < r.id; });
	Solve(mid + 1, r);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	rep(i, 1, n) {
		cin >> a[i].a, a[i].b = a[i].c = a[i].a, a[i].f = 1, a[i].id = i;
	}
	rep(i, 1, m) {
		int x, y;
		cin >> x >> y;
		a[x].b = min(a[x].b, y), a[x].c = max(a[x].c, y);
	}
	Solve(1, n);
	cout << ans << '\n';
	return 0;
}

标签:P4093,int,题解,rep,mid,cin,Item,序列,id
From: https://www.cnblogs.com/laijinyi/p/18449765

相关文章

  • P4690 镜中的昆虫 (动态区间颜色数) 题解
    Statement区间涂颜色区间颜色数Solution\(O(\text{polysqrt})\)略。\(O(\text{polylog})\)颜色段均摊有两层含义:随机数据下:任意时刻的颜色段个数期望\(O(\logn)\)非随机数据下:每次推平时访问的颜色段个数均摊\(O(n)\)首先维护每个点\(i\)的\(pre_i\),一次询......
  • GB | Seqrutinator:一个用于鉴定和去除非功能性序列的基因家族分析流程
    分享一篇近期发表在GenomeBiology上 的一个基因家族分析软件:Seqrutinator。该软件用于识别和去除基因家族数据集中的无功能基因,包括假基因、测序错误、基因结构错误、比对错误等,从而避免基因家族鉴定中的假阳性结果,进一步确保基因家族注释的准确性,以便于后续系统发育分析和功......
  • Codeforces Rund 977 div2 个人题解(A~E1)
    CodeforcesRund977div2个人题解(A,B,C1,C2,E1)Dashboard-CodeforcesRound977(Div.2,basedonCOMPFEST16-FinalRound)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#includ......
  • 【题解】C - STEP
    目录题目内容DescriptionInputOutput数据规模与约定做法一思路代码做法2思路代码题目内容原题:洛谷P6492Description给定一个长度为\(n\)的字符序列\(a\),初始时序列中全部都是字符L。有\(q\)次修改,每次给定一个\(x\),若\(a_x\)为L,则将\(a_x\)修改成R,否则将\(a_x\)......
  • 常见问题解决 --- maven手动安装依赖jar包报错
    报错内容:执行命令mvninstall:install-file-DgroupId=com.beidouapp-DartifactId=SSDK-Dversion=4.0.2.0 -Dfile=C:\1\SSDK-Release-4.0.2.0.jar-Dpackaging=jar报错Unknownlifecyclephase“.ggstar“.Youmustspecifyavalidlifecyclephaseoragoal原因:在pow......
  • 序列化器中拿到request
    classUpdateMobileSerializer(serializers.ModelSerializer):old=serializers.CharField(write_only=True,validators=[RegexValidator(r"\d{11}",message="格式错误")])mobile=serializers.CharField(write_only=True,validators=[RegexV......
  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......
  • CCF-CSP认证资格考试题解系列——第4次第3题节日
    #include<iostream>usingnamespacestd;intm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};intis_run(intyear){ if(year%400==0||(year%4==0&&year%100))return1; return0;}intgetdays(intyear,intmonth){ if(month==2)returnm[month]+i......
  • ABC374 E 题解
    ABC374E题解E-SensorOptimizationDilemma2题目链接:AT|洛谷容易发现答案可以二分。于是我们把问题转化为了判定性问题:给定目标\(x\),能否在花费不超过预算的情况下,使得每个过程的产量都不低于\(x\)?进一步,由于各个过程的生产互不相关,所以我们要尽可能让每个过程的费......
  • P7078 [CSP-S2020] 贪吃蛇 题解
    P7078[CSP-S2020]贪吃蛇这题好啊题目传送门看到题之后觉得有点像砍蚯蚓的那道题看看题目可以证明,若一条蛇在吃完之后不是最弱的那一条蛇,那么他一定会选择吃,证明如下设蛇长为\(a_{1,\dots,n}\)且依次递增,那么很明显的因为​......