首页 > 其他分享 >JOISC 2022 D4T2 鱼 2

JOISC 2022 D4T2 鱼 2

时间：2023-09-11 17:24:20浏览次数：48  
标签：rt D4T2 vc return update JOISC 2022 SGT2 find

洛谷传送门

LOJ 传送门

为了方便，设 \(a_0 = a_{n + 1} = \infty\)。

考虑拎出来所有区间 \([l, r]\) 使得 \(\sum\limits_{i = l}^r a_i < \min(a_{l - 1}, a_{r + 1})\)。那么 \([l, r]\) 中的所有鱼都不能吃到 \([l, r]\) 外面的鱼。那么 \([1, n]\) 中能吃掉所有鱼的鱼，一定不被除了 \([1, n]\) 之外的区间包含。

考虑从 \([i, i]\) 开始，通过线段树上二分得到包含它的最小的区间 \([l, r]\) 使得 \(\sum\limits_{i = l}^r a_i < \min(a_{l - 1}, a_{r + 1})\)。每次跳出去区间和至少加倍，所以至多跳 \(\log V\) 次。所以这样的区间有 \(O(n \log V)\) 种。加上线段树上二分的 \(\log n\)，找出所有这样的区间的复杂度为 \(O(n \log n \log V)\)。

先考虑没有修改：因为不能往 \([l, r]\) 外面吃了，所以可能会导致 \([l, r]\) 的一个前缀和后缀不能吃完 \([l, r]\) 了。我们用上面的方法可以找到这样的前缀和后缀。我们把不能往外面吃的鱼的区间拎出来，给它们区间加 \(1\)，查询即查询 \([l, r]\) 最小值个数（因为还有一些大区间 \(L \le l \le r \le R\) 完全包含 \([l, r]\)）。

有修改的话，我们找出所有包含 \(x - 1, x, x + 1\) 的区间（要 \(\pm 1\) 是因为修改 \(x\) 可能会影响所有 \(r = x - 1\) 或者 \(l = x + 1\) 的区间），把它们删除，修改后重新加入即可。

所以总复杂度就是 \(O((n + q) \log n \log V)\)。

代码写起来有点臭。

code 
// Problem: P9530 [JOISC 2022 Day4] 鱼 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9530
// Memory Limit: 1 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    for (; !isdigit(c); c = getchar()) ;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}

const int maxn = 100100;

ll n, m, a[maxn];

namespace BIT {
	ll c[maxn];
	
	inline void update(ll x, ll d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline ll query(ll x) {
		ll res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
	
	inline ll query(int l, int r) {
		return query(r) - query(l - 1);
	}
}

namespace SGT {
	ll mx[maxn << 2];
	
	inline void pushup(int x) {
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	void build(int rt, int l, int r) {
		if (l == r) {
			mx[rt] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int x, ll y) {
		if (l == r) {
			mx[rt] = y;
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
		pushup(rt);
	}
	
	ll query(int rt, int l, int r, int x) {
		if (l == r) {
			return mx[rt];
		}
		int mid = (l + r) >> 1;
		return (x <= mid) ? query(rt << 1, l, mid, x) : query(rt << 1 | 1, mid + 1, r, x);
	}
	
	int findl(int rt, int l, int r, ll x) {
		if (mx[rt] < x) {
			return -1;
		}
		if (l == r) {
			return l;
		}
		int mid = (l + r) >> 1;
		if (mx[rt << 1] >= x) {
			return findl(rt << 1, l, mid, x);
		} else {
			return findl(rt << 1 | 1, mid + 1, r, x);
		}
	}
	
	int findr(int rt, int l, int r, ll x) {
		if (mx[rt] < x) {
			return -1;
		}
		if (l == r) {
			return l;
		}
		int mid = (l + r) >> 1;
		if (mx[rt << 1 | 1] >= x) {
			return findr(rt << 1 | 1, mid + 1, r, x);
		} else {
			return findr(rt << 1, l, mid, x);
		}
	}
	
	int findl(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql > qr || mx[rt] < x) {
			return -1;
		}
		if (ql <= l && r <= qr) {
			return findl(rt, l, r, x);
		}
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			int t = findl(rt << 1, l, mid, ql, qr, x);
			if (t != -1) {
				return t;
			}
		}
		if (qr > mid) {
			int t = findl(rt << 1 | 1, mid + 1, r, ql, qr, x);
			if (t != -1) {
				return t;
			}
		}
		return -1;
	}
	
	int findr(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql > qr || mx[rt] < x) {
			return -1;
		}
		if (ql <= l && r <= qr) {
			return findr(rt, l, r, x);
		}
		int mid = (l + r) >> 1;
		if (qr > mid) {
			int t = findr(rt << 1 | 1, mid + 1, r, ql, qr, x);
			if (t != -1) {
				return t;
			}
		}
		if (ql <= mid) {
			int t = findr(rt << 1, l, mid, ql, qr, x);
			if (t != -1) {
				return t;
			}
		}
		return -1;
	}
}

namespace SGT2 {
	pii mn[maxn << 2];
	int tag[maxn << 2];
	
	inline pii operator + (const pii &a, const pii &b) {
		int t = min(a.fst, b.fst);
		return mkp(t, (a.fst == t ? a.scd : 0) + (b.fst == t ? b.scd : 0));
	}
	
	inline void pushup(int x) {
		mn[x] = mn[x << 1] + mn[x << 1 | 1];
	}
	
	inline void pushdown(int x) {
		if (!tag[x]) {
			return;
		}
		mn[x << 1].fst += tag[x];
		mn[x << 1 | 1].fst += tag[x];
		tag[x << 1] += tag[x];
		tag[x << 1 | 1] += tag[x];
		tag[x] = 0;
	}
	
	void build(int rt, int l, int r) {
		mn[rt] = mkp(0, r - l + 1);
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
	}
	
	void update(int rt, int l, int r, int ql, int qr, int x) {
		if (ql > qr) {
			return;
		}
		if (ql <= l && r <= qr) {
			mn[rt].fst += x;
			tag[rt] += x;
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	pii query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return mn[rt];
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		pii res = mkp(1e9, 0);
		if (ql <= mid) {
			res = res + query(rt << 1, l, mid, ql, qr);
		}
		if (qr > mid) {
			res = res + query(rt << 1 | 1, mid + 1, r, ql, qr);
		}
		return res;
	}
}

vector<pii> vc;

inline void find(int x) {
	if (x < 1 || x > n) {
		return;
	}
	int l = x, r = x;
	ll s = a[x];
	while (1 <= l && r <= n) {
		int pl = SGT::findr(1, 0, n + 1, 0, l - 1, s + 1), pr = SGT::findl(1, 0, n + 1, r + 1, n + 1, s + 1);
		l = pl + 1;
		r = pr - 1;
		s = BIT::query(l, r);
		if (min(a[pl], a[pr]) > s) {
			vc.pb(l, r);
			if (a[pl] <= a[pr]) {
				s += a[--l];
			} else {
				s += a[++r];
			}
		}
	}
}

const int mod = 114514191;

struct HashTable {
	int head[mod + 3], len, nxt[maxn * 100];
	pii val[maxn * 100];
	bool sta[maxn * 100];
	
	inline bool add(pii p) {
		int x = (1LL * p.fst * n + p.scd) % mod;
		for (int i = head[x]; i; i = nxt[i]) {
			if (val[i] == p) {
				if (sta[i]) {
					return 0;
				} else {
					sta[i] = 1;
					return 1;
				}
			}
		}
		val[++len] = p;
		nxt[len] = head[x];
		sta[len] = 1;
		head[x] = len;
		return 1;
	}
	
	inline bool del(pii p) {
		int x = (1LL * p.fst * n + p.scd) % mod;
		for (int i = head[x]; i; i = nxt[i]) {
			if (val[i] == p) {
				if (sta[i]) {
					sta[i] = 0;
					return 1;
				} else {
					return 0;
				}
			}
		}
		return 0;
	}
} S;

void solve() {
	n = read();
	a[0] = a[n + 1] = 1e18;
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		BIT::update(i, a[i]);
	}
	m = read();
	SGT::build(1, 0, n + 1);
	SGT2::build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		vector<pii>().swap(vc);
		find(i);
		for (pii p : vc) {
			if (S.add(p)) {
				SGT2::update(1, 1, n, p.fst, p.scd, 1);
			}
		}
	}
	while (m--) {
		ll op, x, y;
		op = read();
		x = read();
		y = read();
		if (op == 1) {
			vector<pii>().swap(vc);
			find(x - 1);
			find(x);
			find(x + 1);
			for (pii p : vc) {
				if (S.del(p)) {
					SGT2::update(1, 1, n, p.fst, p.scd, -1);
				}
			}
			BIT::update(x, y - a[x]);
			SGT::update(1, 0, n + 1, x, y);
			a[x] = y;
			vector<pii>().swap(vc);
			find(x - 1);
			find(x);
			find(x + 1);
			for (pii p : vc) {
				if (S.add(p)) {
					SGT2::update(1, 1, n, p.fst, p.scd, 1);
				}
			}
		} else {
			int p = x, pl = x - 1, pr = y + 1;
			ll s = a[x];
			while (1) {
				p = SGT::findl(1, 0, n + 1, p + 1, y, s + 1);
				if (p == -1) {
					break;
				}
				s = BIT::query(x, p);
				if (a[p] > s - a[p]) {
					pl = p - 1;
				}
			}
			p = y;
			s = a[y];
			while (1) {
				p = SGT::findr(1, 0, n + 1, x, p - 1, s + 1);
				if (p == -1) {
					break;
				}
				s = BIT::query(p, y);
				if (a[p] > s - a[p]) {
					pr = p + 1;
				}
			}
			SGT2::update(1, 1, n, x, pl, 1);
			SGT2::update(1, 1, n, pr, y, 1);
			printf("%d\n", SGT2::query(1, 1, n, x, y).scd);
			SGT2::update(1, 1, n, x, pl, -1);
			SGT2::update(1, 1, n, pr, y, -1);
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签：rt,D4T2,vc,return,update,JOISC,2022,SGT2,find
From： https://www.cnblogs.com/zltzlt-blog/p/17694007.html

相关文章

  • 开源 & Dad：聊一下我与 2022 的故事
    开源&Dad：聊一下我与2022的故事董天成​github.com/andycall​关注他 22人赞同了该文章​展开目录 每个人都有这自己难忘的2022年，同样，2022对于我来说，是个重要的人生转折点。通常每次在新年的时候，我都是向前看，想象着新的一年后，自......
  • CSP-S2022初赛易错题解析
    一.2.错误原因：不会解析：real代表实际运行时间，user代表用户态运行时间，sys表示内核态运行时间，故选A 5.错误原因：不会解析：基数排序的思路类似于桶排序，故选A 9.错误原因：不会解析：这个问题可以转化成圆排列问题，公式为A(n-1,n-1)，即(n-1)!,要考虑从两个方向看的图，所以要除......
  • [Writeup]2022 NewstarCTF_Week2(Web部分)
    一只网络安全菜鸟--(˙<>˙)/--写博客主要是想记录一下自己的学习过程，过两年毕业了也能回头看看自己都学了些啥东西。由于本人水平有限内容难免有错误、疏漏、逻辑不清、让人看不懂等各种问题，恳请大家批评指正如果我写的东西能对你有一点点帮助，那真是再好不过了......
  • 2022ICPC南京站D
    1：题意给你一个序列要求你进行一次操作，选一个位置i从他开始往后加数直到加到第i+m-1个，加的值成等差求操作完后的第k大的数2：思路1）:二分答案二分找到第k大的值2）：差分check里面，枚举每一个数看他是否大于mid，记录为num，小于的判断他是否+等差最后一位小于mid，小于直接跳过，大于则判断......
  • Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
    给一个长为\(n\)的正整数数组，执行以下操作严格一次。选择\(l,r,(1\leql<r\leqn)\)，任意一个正整数\(k\)。重复\(k\)次：让\([l,r]\)的数组成环，按顺时针走一次。希望\(a_n-a_1\)最大，找到这个数。分类讨论题。先判断\(n\)为\(1\)时\(a_n-a_1\)......
  • [JOISC 2016] 雇佣计划 题解
    [JOISC2016]雇佣计划题解这里补充一篇自己的\(n\logn\)做法。本蒟蒻打了两棵线段树，并且进行了繁琐的分类讨论，完全被标算的树状数组吊打qwq题意：给定一个序列\(a\)，有两种操作：将\(c\)位置权值改为\(d\)；给定一个权值\(b\)，定义集合\(S=\{i|a_i\geb\}\)，对于......
  • 2022年线下赛的一道流量分析题
    题目给了一个where_is_password.pcapngbinwalk看到里面有个压缩包，利用foremost分离出来压缩包需要密码分析流量包，发现存在sql注入提取出来进行url解码，可以看到利用二分法进行sql盲注ascii有128个所以从>64开始判断,返回用户名或密码错误，然后判断>32,没有返回错误，说明在3......
  • P8029 [COCI2021-2022#3] Akcija 题解
    注：这篇题解中涉及到的所有概念均会在其第一次出现时用斜体标出，有些概念给出了定义，而有些概念的含义请自行意会。定义状态为选了的物品数\(a\)与相应总价格\(b\)的二元组\((a,b)\)。相应地定义状态之间的大小关系、最优状态与状态和状态的加法运算\((a_1,b_1)+(a_2,b......
  • LabVIEW 2022中文版下载附安装教程 新功能介绍
    LabVIEW（LaboratoryVirtualInstrumentEngineeringWorkbench）是美国国家仪器公司（NationalInstruments）公司的一款图形化编程语言，主要应用于工程领域。LabVIEW软件提供了一个可视化编程环境，使得使用者可以通过简单的拖曳和连接图案块来建立程序，而不需要编写繁琐的代码。LabVIEW软件......
  • JOISC 2023 纪录
    记录一下JOISC2023的做题记录Day1T1TwoCurrencies给定一棵树，在边上有总计\(m\)个检查站，经过一个检查站需要叫\(1\)枚金币或者若干枚银币。\(Q\)次询问，问一个人有\(X\)枚金币和\(Y\)枚银币，能否从\(u\)走到\(v\)，同时回答最多可以留下多少枚金币。发现一定是......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99