首页 > 其他分享 >POI2011MET-Meteors

POI2011MET-Meteors

时间:2024-04-20 16:57:32浏览次数:23  
标签:tmp POI2011MET int rep tr lv second Meteors

POI #Year2011 #整体二分

整体二分板子,用树状数组维护即可

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

int n, m, t;
vector<int> vec[N];
struct node
{
	int l, r, x;
} s[N];
pii a[N];
struct BIT
{
	int tr[N];

	void add(int x, int v)
	{
		while (x <= m * 2)
		{
			tr[x] += v;
			x += x & -x;
		}
	}

	int sum(int x)
	{
		int res = 0;
		while (x)
		{
			res += tr[x];
			x -= x & -x;
		}
		return res;
	}
} tr;

int res[N];

void solve(int l, int r, int x, int y)
{
	if (x > y)
		return;
	if (l == r)
	{
		debug(l, r, x, y);
		rep(i, x, y)
		{
			res[a[i].second] = l;
			debug(a[i].second);
		}
		return;
	}
	int mid = l + r >> 1;
	rep(i, l, mid)
	{
		tr.add(s[i].l, s[i].x);
		tr.add(s[i].r + 1, -s[i].x);
	}
	vector<pii> lv, rv;
	rep(i, x, y)
	{
		int tmp = 0;
		for (auto v : vec[a[i].second])
		{
			tmp += tr.sum(v) + tr.sum(v + m);
			if (tmp >= a[i].first)
				break;
		}
		debug(l, r, a[i].second, tmp);
		if (tmp >= a[i].first)
			lv.push_back(a[i]);
		else
		{
			a[i].first -= tmp;
			rv.push_back(a[i]);
		}
	}
	rep(i, l, mid)
	{
		tr.add(s[i].l, -s[i].x);
		tr.add(s[i].r + 1, s[i].x);
	}
	int tot = x;
	for (auto v : lv)
		a[tot++] = v;
	for (auto v : rv)
		a[tot++] = v;
	debug(lv, rv);
	solve(l, mid, x, x + lv.size() - 1);
	solve(mid + 1, r, x + lv.size(), y);
}

void solve()
{
	mms(res, -1);
	cin >> n >> m;
	rep(i, 1, m)
	{
		int x;
		cin >> x;
		vec[x].push_back(i);
	}
	rep(i, 1, n)
	{
		cin >> a[i].first;
		a[i].second = i;
	}
	cin >> t;
	rep(i, 1, t)
	{
		cin >> s[i].l >> s[i].r >> s[i].x;
		if (s[i].r < s[i].l)
			s[i].r += m;
	}
	s[++t] = {1, 2 * m, INF};
	solve(1, t, 1, n);
	rep(i, 1, n)
	{
		// debug(res[i]);
		if (res[i] > t - 1 || res[i] == -1)
			cout << "NIE\n";
		else
			cout << res[i] << '\n';
	}
}

#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;
}

标签:tmp,POI2011MET,int,rep,tr,lv,second,Meteors
From: https://www.cnblogs.com/xiaruize/p/18147874

相关文章

  • [POI2011] MET-Meteors
    [POI2011]MET-Meteors题面翻译ByteotianInterstellarUnion有\(n\)个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为\(m\)份(第\(m\)份和第\(1\)份相邻),第\(i\)份上有第\(a_i\)个国家的太空站。这个星球经常会下陨石雨。BIU已经预测了接下来\(k\)场陨......
  • Meteors 题解
    Meteors蒟蒻初学整体二分,写一篇题解记录一下思考与看法。题目大意在一个环形的轨道上分别着若干国家的空间站,在接下来的一段时间内会出现若干次陨石,每次出现在环形的某一段轨道,每个国家都想收集一定量的陨石,需要判断每个国家最少在什么时候可以集齐所需的陨石。思路分析首先......
  • P3527 [POI2011]MET-Meteors
    简要题意有\(n\)个国家和有\(m\)段的环形轨道。轨道的第\(i\)段有第\(o_i\)个国家建立的空间站。有\(k\)个时刻,第\(i\)个时刻会在\([l_i,r_i]\)的轨道中......
  • [POI2011]MET-Meteors 解题报告
    语言系统紊乱了QAQ这道题感觉不是很难鸭qwq。先只考虑一个国家,怎么做?很显然,就直接二分一下就行了。判定答案可以维护一个差分数组,然后最后对它做一个前缀和,再求一下这......
  • P3527 [POI2011]MET-Meteors
    题目之前学完整体二分就一直准备做来着,结果一直到今天才做对,所以我还是太菜辣!整体二分说白了就是将多次二分放在一起一次处理,也并不是简简单单的查询第$K$大,所以有些题......
  • 题解 SP10264 METEORS - Meteors
    整体二分经典题,所以我们用分块解决Solution和整体二分类似,我们把\(k\)次操作分成\(\sqrtk\)块,每一块一起考虑。对于区间加,可以转化为差分,那么在每个块一起作差分后......
  • P3527 [POI2011]MET-Meteors
    \(\mathcalLink\)做法一:分块认为\(n,m,k\)同阶。对操作分块,将\(s\)个操作分成一个块,每次扫一个整块,用差分算出已收集的量。然后依次扫每个国家,判断是否收集满了,是......
  • P3527 [POI2011]MET-Meteors
    P3527[POI2011]MET-Meteors目录P3527[POI2011]MET-Meteors题意正文主席树code:整体二分拆分区间code:题意给定一段1-m的区间,n个国家,每个位置属于一个国家每个国家有......