首页 > 其他分享 >[JOISC 2016] 雇佣计划 题解

[JOISC 2016] 雇佣计划 题解

时间：2023-09-10 15:55:22浏览次数：57  
标签：int 题解 modify totl JOISC del s2 2016 id

[JOISC 2016] 雇佣计划 题解

这里补充一篇自己的 \(n \log n\) 做法。

本蒟蒻打了两棵线段树，并且进行了繁琐的分类讨论，完全被标算的树状数组吊打 qwq

题意：

给定一个序列 \(a\)，有两种操作：

  • 将 \(c\) 位置权值改为 \(d\)；
  • 给定一个权值 \(b\)，定义集合 \(S = \{i | a_i \ge b\}\)，对于 \(\forall l, r \in S\)，如果 $ \forall j \in [l, r]$，有 \(j \in S\)，则 \(l,r\) 在一组内。求组数。

思路：

首先，我们并不关注每个 \(a\) 与 \(b\) 具体的值，只需要考虑他们之间的相对大小关系，所以我们可以把所有用到的权值全部离线。这样我们就可以把值域分为最多 \(4 \times 10^5\) 个档次。

然后我们来考虑组数的转化。让我们把所有的 \(a_i\) 连起来，可以形成一个曲线。组数就是在曲线上面的连续段数。如图。

pPcDR81.png

然后发现，这里的 \(b\) 可以看作一条扫描线，我们把 \(b\) 上面的部分赋值为 \(1\)，下面部分赋值为 \(0\)，则答案就是 \(1\) 连续段的个数。这个可以让 \(b\) 从上往下扫描，不断加入新的 \(1\)，然后用线段树维护。这样，我们可以求出一个 \(f\) 数组，表示如果没有修改，对于值域的每一档的答案。

现在我们来考虑修改。我们发现，每一个修改的影响只与这个点和它两侧的点的权值相对大小有关，然后我就去分讨了，写了半天，比如下面这个例子，为了简化模型，我们现在只考虑这三个点的答案：

pPcDXxP.png

黑点代表修改前的点，红点代表修改后的点， 黑色的值为修改前的区间内的答案，红色的值为修改后区间内的答案。

对于每一个修改，影响到的区间内答案只有增加一或减小一，所以可以用线段树维护。

而实际上，左右两个点的大小关系是无所谓的，所以一共能分为两大类：权值增大与权值减小，每一类里还有三小类，即修改的点在两侧点下面，在两侧点之间，在两侧点上面。根据修改后的影响范围修改即可（其实这里还要稍微分下类，但是我懒了 xwx）。

具体的分类讨论还是看代码吧……反正很麻烦就对了，自己还是太菜了。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 100;

inline int read() {
	int x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') x = x * 10 + (ch - 48), ch = getchar();
	return x;
}

int a[N], lsh[N];
int totl;
struct Questions {
	int id, val;//id == 0: query.
} q[N];
int n, m;
struct xwx {
	int val, id;
	bool operator < (const xwx &b) const {
		return val < b.val;
	}
};
priority_queue<xwx> qu;
void prework() {//离散化所有出现的权值。 
	sort(lsh + 1, lsh + totl + 1);
	totl = unique(lsh + 1, lsh + totl + 1) - lsh - 1;

	for (int i = 1; i <= n; ++i) {
		a[i] = lower_bound(lsh + 1, lsh + totl + 1, a[i]) - lsh;
		qu.push((xwx) {
			a[i], i
		});
	}

	for (int i = 1; i <= m; ++i) {
		q[i].val = lower_bound(lsh + 1, lsh + totl + 1, q[i].val) - lsh;
	}
}

int f[N];
#define ls tr<<1
#define rs tr<<1 | 1
struct SegmentTree1 {//第一棵线段树，用来预处理 f 

	struct node {
		int lc, rc;
		int ans;
	} tree[N << 2];
	
	void push_up(int tr) {
		tree[tr].ans = tree[ls].ans + tree[rs].ans - (tree[ls].rc & tree[rs].lc);
		tree[tr].lc = tree[ls].lc;
		tree[tr].rc = tree[rs].rc;
	}
	void modify(int tr, int L, int R, int pos) {
		if (L == R) {
			tree[tr] = (node) {
				1, 1, 1
			};
			return;
		}

		int mid = (L + R) >> 1;

		if (pos <= mid) {
			modify(ls, L, mid, pos);
		} else
			modify(rs, mid + 1, R, pos);

		push_up(tr);
	}
	int query() {
		return tree[1].ans;
	}
} s1;

struct SegmentTree2 {//第二棵线段树，用来处理修改。 
	struct node {
		int val, tag;
	} tree[N << 2];
	//这里R就是值域totl 了
	//标记永久化
	void build(int tr, int L, int R) {
		if (L == R) {
			tree[tr].val = f[L];
			return;
		}

		int mid = (L + R) >> 1;
		build(ls, L, mid);
		build(rs, mid + 1, R);
	}
	void modify(int tr, int L, int R, int lq, int rq, int val) {
		if (lq <= L && R <= rq) {
			tree[tr].tag += val;
			return;
		}

		int mid = (L + R) >> 1;

		if (lq <= mid)
			modify(ls, L, mid, lq, rq, val);

		if (mid < rq)
			modify(rs, mid + 1, R, lq, rq, val);
	}
	int query(int tr, int L, int R, int pos) {
		if (L == R) {
			return tree[tr].tag + tree[tr].val;
		}

		int mid = (L + R) >> 1;

		if (pos <= mid) {
			return tree[tr].tag + query(ls, L, mid, pos);
		} else {
			return tree[tr].tag + query(rs, mid + 1, R, pos);
		}
	}
} s2;
int main() {
	n = read(), m = read();

	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		lsh[++totl] = a[i];
	}

	for (int i = 1; i <= m; ++i) {
		int op = read();

		if (op == 1) {
			q[i] = (Questions) {
				0, read()
			};
			lsh[++totl] = q[i].val;
		} else {
			q[i].id = read(), q[i].val = read();
			lsh[++totl] = q[i].val;
		}
	}

	prework();

	for (int i = totl; i >= 1; --i) {
		while (qu.size() && qu.top().val >= i) {
			s1.modify(1, 1, n, qu.top().id);//注意这里的R应该是n！不是值域！
			qu.pop();
		}

		f[i] = s1.query();
	}

	s2.build(1, 1, totl);

	for (int i = 1; i <= m; ++i) {
		if (q[i].id) {
			int id = q[i].id, del = q[i].val;

			//这一部分建议结合曲线图来理解修改的区间（三个点的就够） 
			if (id == 1) {//首尾两个点特殊照顾一下。 
				if (a[id] < del) {//权值增加 
					if (del > a[id + 1]) {//如果增加的范围超过了右侧点 
						s2.modify(1, 1, totl, max(a[id + 1], a[id]) + 1, del, 1);
					}
				} else if (a[id] > del) {//权值减少 
					if (a[id] > a[id + 1]) {//如果减少前权值比右侧点大 
						s2.modify(1, 1, totl, max(a[id + 1], del) + 1, a[id], -1);
					}
				}
			} else if (id == n) {//和 id == 1 类似 
				if (a[id] < del) {
					if (del > a[id - 1]) {
						s2.modify(1, 1, totl, max(a[id - 1], a[id]) + 1, del, 1);
					}
				} else if (a[id] > del) {
					if (a[id] > a[id - 1]) {
						s2.modify(1, 1, totl, max(a[id - 1], del) + 1, a[id], -1);
					}
				}
			} else {
				int mx = max(a[id - 1], a[id + 1]), mn = min(a[id - 1], a[id + 1]);
				//我们只关心两侧点中较大的和较小的值为多少 
				if (a[id] < del) {//权值增加 
					if (a[id] < mn) {//修改前比较小值还要小 
						if (del <= mx) {//修改后没超过较大值 
							s2.modify(1, 1, totl, a[id] + 1, min(del, mn), -1);
						} else {//超过了 
							s2.modify(1, 1, totl, a[id] + 1, mn, -1);
							s2.modify(1, 1, totl, mx + 1, del, 1);
						}
					} else if (a[id] <= mx) {//修改前在两侧权值之间 
						if (del > mx) {//只有修改后超过较大值才会更新答案 
							s2.modify(1, 1, totl, mx + 1, del, 1);
						}
					} else {//修改前比较大值大 
						s2.modify(1, 1, totl, a[id] + 1, del, 1);
					}


				} else if (a[id] > del) {//权值减少 
					if (a[id] < mn) {//修改前低于较小值 
						s2.modify(1, 1, totl, del + 1, a[id], 1);
					} else if (a[id] <= mx) {//修改前在两侧权值之间 
						if (del < mn) {
							s2.modify(1, 1, totl, del + 1, mn, 1);
						}
					} else {//修改前在两侧权值上 
						if (del >= mn) {//如果修改后不低于较小值 
							s2.modify(1, 1, totl, max(mx, del) + 1, a[id], -1);
						} else {
							s2.modify(1, 1, totl, mx + 1, a[id], -1);
							s2.modify(1, 1, totl, del + 1, mn, 1);
						}
					}
				}
			}
			a[id] = del;
		} else {
			printf("%d\n", s2.query(1, 1, totl, q[i].val));//单点查询。 
		}
	}
	return 0;
}

标签：int,题解,modify,totl,JOISC,del,s2,2016,id
From： https://www.cnblogs.com/frostwood/p/17691358.html

相关文章

  • P8029 [COCI2021-2022#3] Akcija 题解
    注：这篇题解中涉及到的所有概念均会在其第一次出现时用斜体标出，有些概念给出了定义，而有些概念的含义请自行意会。定义状态为选了的物品数\(a\)与相应总价格\(b\)的二元组\((a,b)\)。相应地定义状态之间的大小关系、最优状态与状态和状态的加法运算\((a_1,b_1)+(a_2,b......
  • UVA1030 题解
    思路分析猜想我们可以在题目中看出一下几个突破口：能“看穿”的位置所对应的单位立方体是一定不存在的。如果前视图的右上角的颜色\(A\)和顶视图的的右下角颜色\(B\)不同，那么对应的格子就一定不存在。在删除这个立方体后，我们还可以发现，挖去立方体的左侧和\(B\)左侧的......
  • CF431B 题解
    思路分析答题思路一道纯暴力题！因为我们发现数据最大是\(5\)，而枚举全排列的时间复杂度为\(\mathcalO(n!)\)，对于这种极小的数据范围是丝毫不用顾虑的，因为我们只需要执行\(120\)次。如何快速求出一个数组的全排列？我们可以使用dfs，一层一层获取这个数组的全排列。但是STL......
  • CF387B 题解
    思路分析因为最终要使得\(a,b\)相同，所以我们应该希望让相同的数字尽量相同。所以，我们需要先对\(a\)和\(b\)进行排序，这样子就可以使用双指针的方法来维护最终值了。我们定义\(l\)指针指向\(a_l\)，\(r\)指针指向\(b_r\)。因为题目要求添加数字的次数最少，所以我们希望尽......
  • P9516 题解
    思路分析一道很有洛谷个性的模拟签到题。按照题意，我们只需读入\(a,b,c,d,e\)，然后对其进行求和，然后依次根据洛谷咕值系统介绍进行判断即可。这样是不是太没有意思了？今天为大家带来一点干货作为福利！介绍：accumulate()函数！简略分析：这个函数可以求出一段区间内的数字之和。S......
  • P9517 题解
    思路分析我们只需要找到左边第一个大于\(0\)的位置\(l\)与右边第一个大于\(0\)的位置\(r\)，输出\(r-l+1\)即可。但是很坑的一点是，如果\(∀i∈[1,n],a_i=0\)，那么\(l\)和\(r\)会重合，代码会输出\(1\)！所以，我们需要定义一个\(flag\)来标记是否全部输入为\(0\)。代......
  • UVA11210 题解
    思路分析一道大模拟。一共只有\(34\)种牌，因此可以一次判断是否“听”这些牌。比如，为了判断是否“听”一万，只需要判断自己拿到这张一万后能否可以继续和牌。这样，问题就转化成了给定\(14\)张牌，判断是否可以和牌。为此，我们可以递归求解：首先将两张牌作为“将”，然后每次选\(3\)......
  • UVA1352 题解
    思路分析构造排列表立方体只有\(4\)个，暴力法是可行的。但是如果我们要暴力，首先得清楚一个立方体到底有几种不同的旋转方式。接下来，我们用“姿态”一词代替“旋转方法”。假设\(6\)个面的编号为\(1\sim6\)，从中选择一个面作为“顶面”，“顶面”的对面为“底面”。然后我们在......
  • UVA11464 题解
    思路分析暴力枚举？我们可以枚举每个数字变或不变，最后判断整个矩阵是否满足条件。但是，这样做最多需要枚举\(2^{255}≈5\times10^{67}\)中情况，是一定会超时的。大眼观察注意到\(n\le15\)，第一行只有不超过\(2^{15}=32768\)种可能，所以第一行的情况是可以枚举的。接下来，根据第......
  • 题解 SP4586 Texas Trip
    首先题目翻译是有问题的，求的不是矩形而是最小的正方形。Solution先考虑一下若正方形的边都只能平行于坐标轴怎么做：找到\(x,y\)方向的坐标最值，那么答案就是\(\max^2\{X_{\max}-X_{\min},Y_{\max}-Y_{\min}\}\)。接下来，若正方形可以是斜着的，我们只需把坐标轴旋转，然后同样找出......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99