首页 > 其他分享 >P3527 MET-Meteors 题解

P3527 MET-Meteors 题解

时间:2024-10-07 09:23:55浏览次数:9  
标签:P3527 int 题解 rep Pos cin mid MET buc

Solution

单次二分:二分时间,做这个时间前的所有操作,然后线性统计。

注意到可以整体二分,直接整体二分是 \(O(n\log^2 n)\)。

考虑扫描序列,用线段树维护每个时间段内该位置的增加值,差分一下可以实现。

将这棵线段树持久化一下,一个国家所有位置同时二分即可 \(O(n\log n)\),可惜空间太大。

回到整体二分,考虑 Solve 相当于一堆区间加后单点查,差分后可线性求出每个国家的权值。

我们要让 Solve 复杂度与当前询问个数、修改个数相关,怎么办呢?

离散化一下再继续递归即可,这里可以直接用桶维护。时间 \(O(n\log n)\),空间 \(O(n)\)。

Code 1

普通整体二分

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
typedef long long ll;
const int N = 3e5 + 10;
int n, m, k, ans[N];
vector<int> Pos[N];
ll p[N];
struct Operations {
	int l, r, s, tim;
} Opers[N << 1];
int optot, queries[N], tmp[N];

ll sum[N];
void Upd(int x, ll v) {
	for (; x <= n; x += x & -x) sum[x] += v;
}
ll Qry(int x) {
	ll res = 0;
	for (; x; x -= x & -x) res += sum[x];
	return res;
}

void Solve(int l, int r, int Opl, int Opr, int Ql, int Qr) {
	if (Opl > Opr || Ql > Qr) return;
	if (l == r) {
		rep(j, Ql, Qr) ans[queries[j]] = l;
		return;
	}
	int mid = (l + r) >> 1, Opmid = Opl, Lc = Ql, Rc = Qr;
	rep(j, Opl, Opr) {
		auto i = Opers[j];
		if (i.tim <= mid) 
			++Opmid, Upd(i.l, i.s), Upd(i.r + 1, -i.s);
	}
	rep(j, Ql, Qr) {
		int i = queries[j];
		ll sum = 0;
		for (int x : Pos[i]) {
			sum += Qry(x);
			if (sum >= p[i]) break;
		}
		if (sum >= p[i]) {
			tmp[Lc++] = i;
		} else {
			p[i] -= sum;
			tmp[Rc--] = i;
		}
	}
	rep(j, Ql, Qr) queries[j] = tmp[j];
	rep(j, Opl, Opmid - 1) {
		auto i = Opers[j];
		Upd(i.l, -i.s), Upd(i.r + 1, i.s);
	}
	Solve(l, mid, Opl, Opmid - 1, Ql, Lc - 1);
	Solve(mid + 1, r, Opmid, Opr, Rc + 1, Qr);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> m >> n;
	rep(i, 1, n) {
		int x;
		cin >> x, Pos[x].push_back(i);
	}
	rep(i, 1, m) cin >> p[i];
	cin >> k;
	vector<int> vec;
	rep(i, 1, k) {
		int l, r, s;
		cin >> l >> r >> s;
		if (l <= r) {
			Opers[++optot] = (Operations){l, r, s, i};
		} else {
			Opers[++optot] = (Operations){l, n, s, i};
			Opers[++optot] = (Operations){1, r, s, i};
		}
	}
	rep(i, 1, m) queries[i] = i, ans[i] = k + 1;
	Solve(1, k + 1, 1, optot, 1, m);
	rep(i, 1, m) {
		if (ans[i] == k + 1) {
			cout << "NIE\n";
		} else {
			cout << ans[i] << '\n';
		}
	}
	return 0;
}

Code 2

可持久化线段树

// O(n log n)
#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 = 3e5 + 10, M = 2e7 + 10;
vector<pair<int, int>> Upds[N];
vector<int> Pos[N];
int n, m, k, p[N];
#define mid ((l + r) >> 1)
struct Node {
	int lc, rc;
	ll sum;
} f[M];
int tot, rt[N];
void Build(int &u, int l, int r) {
	f[u = ++tot].sum = 0ll;
	if (l == r) return;
	Build(f[u].lc, l, mid), Build(f[u].rc, mid + 1, r);
}
void Upd(int &u, int l, int r, int x, ll v) {
	if (x < l || r < x) return;
	f[++tot] = f[u], u = tot, f[u].sum += v;
	if (l == r) return;
	Upd(f[u].lc, l, mid, x, v), Upd(f[u].rc, mid + 1, r, x, v);
}
int Qry(vector<int> &nodes, int l, int r, ll v) {
	if (l == r) return l;
	ll sum = 0;
	for (int u : nodes) {
		sum += f[f[u].lc].sum;
		if (sum >= v) break;
	}
	if (v <= sum) {
		for (int & u : nodes) u = f[u].lc;
		return Qry(nodes, l, mid, v);
	} else {
		for (int & u : nodes) u = f[u].rc;
		return Qry(nodes, mid + 1, r, v - sum);
	}
}
#undef mid

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> m >> n;
	rep(i, 1, n) {
		int x;
		cin >> x, Pos[x].push_back(i);
	}
	rep(i, 1, m) {
		cin >> p[i];
	}
	cin >> k;
	rep(i, 1, k) {
		int l, r, s;
		cin >> l >> r >> s;
		if (l <= r) {
			Upds[l].push_back(make_pair(i, s));
			Upds[r + 1].push_back(make_pair(i, -s));
		} else {
			Upds[l].push_back(make_pair(i, s));
			Upds[1].push_back(make_pair(i, s));
			Upds[r + 1].push_back(make_pair(i, -s));
		}
	}
	Build(rt[0], 1, k + 1);
	rep(i, 1, n) {
		rt[i] = rt[i - 1];
		for (auto it : Upds[i]) {
			Upd(rt[i], 1, k + 1, it.first, it.second);
		}
	}
	rep(i, 1, m) {
		vector<int> nodes;
		for (int v : Pos[i]) nodes.push_back(rt[v]);
		int ans = Qry(nodes, 1, k + 1, p[i]);
		if (ans == k + 1) {
			cout << "NIE\n";
		} else {
			cout << ans << '\n';
		}
	}
	return 0;
}

Code 3

单 \(\log\) 整体二分

#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 = 3e5 + 10;
vector<int> Pos[N];
int n, m, k, p[N];
struct Oper {
	int l, r, a, t;
} O[N << 1];
int tot, id[N], _id[N], ans[N];
ll buc[N], Res[N];

void Solve(int l, int r, int ql, int qr, int range) {
	if (ql > qr) return;
	if (l == r) {
		rep(i, ql, qr) ans[id[i]] = l;
		return;
	}
	int mid = (l + r) >> 1, L = ql - 1, R;
	rep(i, 1, range) buc[i] = 0;
	rep(i, ql, qr) for (int v : Pos[id[i]]) buc[v] = 1;
	rep(i, 1, range) buc[i] += buc[i - 1];
	rep(i, ql, qr) for (int & v : Pos[id[i]]) v = buc[v];
	rep(i, l, r) O[i].l = buc[O[i].l - 1] + 1, O[i].r = buc[O[i].r];
	range = buc[range];
	rep(i, 1, range) buc[i] = 0;
	rep(i, l, mid) buc[O[i].l] += O[i].a, buc[O[i].r + 1] -= O[i].a;
	rep(i, 1, range) buc[i] += buc[i - 1];
	rep(i, ql, qr) {
		ll res = 0;
		int now = id[i];
		for (int v : Pos[now]) {
			res += buc[v];
			if (res >= p[now]) break;
		}
		Res[i] = res;
		if (res >= p[now]) _id[++L] = now;
	}
	R = L;
	rep(i, ql, qr) {
		int now = id[i];
		if (Res[i] < p[now]) p[now] -= Res[i], _id[++R] = now;
	}
	rep(i, ql, qr) id[i] = _id[i];
	Solve(l, mid, ql, L, range), Solve(mid + 1, r, L + 1, qr, range);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> m >> n;
	rep(i, 1, n) {
		int x;
		cin >> x, Pos[x].push_back(i);
	}
	rep(i, 1, m) cin >> p[i];
	cin >> k;
	rep(i, 1, k) {
		int l, r, s;
		cin >> l >> r >> s;
		if (l <= r) {
			O[++tot] = {l, r, s, i};
		} else {
			O[++tot] = {l, n, s, i}, O[++tot] = {1, r, s, i};
		}
	}
	rep(i, 1, m) ans[i] = tot + 1, id[i] = i;
	Solve(1, tot + 1, 1, m, n);
	rep(i, 1, m) {
		if (ans[i] == tot + 1) {
			cout << "NIE\n";
		} else {
			cout << O[ans[i]].t << '\n';
		}
	}
	return 0;
}

标签:P3527,int,题解,rep,Pos,cin,mid,MET,buc
From: https://www.cnblogs.com/laijinyi/p/18449767

相关文章

  • P3250 网络 题解
    Solution单次二分:问“重要度\(\gex\)的所有操作,且\(t\)时间点还存在的所有操作中,是否有不经过这个点的”整体二分:保持操作、询问按时间有序,即预先按时间排序,下传时保持有序;对于一次Solve,对于所有重要度\(\gemid+1\)的操作(加入、删除),考虑与询问按时间混合排序,然后依次......
  • P3215 括号修复 题解
    Statement维护一个括号序列,有以下操作:区间覆盖区间翻转区间反转(左括号变右括号,右括号变左括号)区间问最少改多少位能使括号序列合法,保证有解Solution单纯没想到答案怎么算。。。首先一段括号序,如果消除中间的所有匹配,最终一定形如))))(((,这个信息是可合并的设这时左括......
  • P5416 = UOJ 198 时空旅行 题解
    Statement一棵树,每个节点上有一个集合,每个儿子集合由父亲集合增加一个点\((x_i,c_i)\)或删除一个点得到。根节点集合为\(\{(0,0,0,c_0)\}\)多次询问,每次问\(u\)点的集合内,\(\min\{(x_i-x)^2+c_i\}\)Solution首先你认真读完题发现原题中\(y,z\)都是没用的然后离线DFS......
  • 火星商店问题 题解
    Solution线段树套trie,秒了!\(O(n\log^2n)\)Code#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=1e5+......
  • Gym 100543G Virus synthesis 题解
    Solution首先只考虑回文串的答案;我们重点考虑的是偶回文串结论:对于偶回文串\(u\),从其最长的长度小于等于他的一半的回文后缀,或其父亲转移过来,一定是最优的证明:设\(u\)的一个回文子串为\(v\)(不是父亲),你要让\(v\tou\)的转移最优首先\(v\)不能跨过\(u\)的中点,因为此......
  • LOJ 6041 事情的相似度 题解
    Statement先把串reverse,多次给\(l,r\),求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\):莫队+线段树/树状数组/set,用SA做\(nm/\omega\):bitset乱搞\(\log^2\):SAM+LCT+BIT在parent树上,LCP等于LCA的......
  • P3332 K大数查询 题解
    Solution整体二分板子题vector太好写了111#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=50010;intn,m,ans[......
  • P4093 序列 题解
    Statement给出\(n\) 个数的序列\(\{a_i\}\),接下来\(m\)秒中每一秒会有一个数发生变化,然后恢复。问最长的子序列长度,使得任意时刻这个子序列不下降。\(n\le10^5\)Solution设\(b_i\)为\(i\)最小能变成的数,\(c_i\)为\(i\)最大能变成的数\[f(i)=\max_{j<i\landc......
  • P4690 镜中的昆虫 (动态区间颜色数) 题解
    Statement区间涂颜色区间颜色数Solution\(O(\text{polysqrt})\)略。\(O(\text{polylog})\)颜色段均摊有两层含义:随机数据下:任意时刻的颜色段个数期望\(O(\logn)\)非随机数据下:每次推平时访问的颜色段个数均摊\(O(n)\)首先维护每个点\(i\)的\(pre_i\),一次询......
  • prometheus学习笔记之PromQL
    prometheus学习笔记之PromQL一、PromQL语句简介官方文档:https://prometheus.io/docs/prometheus/latest/querying/basics/Prometheus提供⼀个函数式的表达式语⾔PromQL(PrometheusQueryLanguage),可以使⽤户实时地查找和聚合时间序列数据,表达式计算结果可以在图表中展示,也可......