首页 > 其他分享 >[POI2011] MET-Meteors

[POI2011] MET-Meteors

时间:2024-01-16 22:23:58浏览次数:38  
标签:二分 le Meteors ed ll POI2011 st MET 答案

[POI2011] MET-Meteors

题面翻译

Byteotian Interstellar Union

有 \(n\) 个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为 \(m\) 份(第 \(m\) 份和第 \(1\) 份相邻),第 \(i\) 份上有第 \(a_i\) 个国家的太空站。

这个星球经常会下陨石雨。BIU 已经预测了接下来 \(k\) 场陨石雨的情况。

BIU 的第 \(i\) 个成员国希望能够收集 \(p_i\) 单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。

输入格式

第一行是两个数 \(n,m\)。

第二行有 \(m\) 个数,第 \(i\) 个数 \(o_i\) 表示第 \(i\) 段轨道上有第 \(o_i\) 个国家的太空站。

第三行有 \(n\) 个数,第 \(i\) 个数 \(p_i\) 表示第 \(i\) 个国家希望收集的陨石数量。

第四行有一个数 \(k\),表示 BIU 预测了接下来的 \(k\) 场陨石雨。 接下来 \(k\) 行,每行有三个数 \(l_i,r_i,a_i\) ,表示第 \(k\) 场陨石雨的发生地点在从 \(l_i\) 顺时针到 \(r_i\) 的区间中(如果 \(l_i \leq r_i\),则是 \(l_i, l_i + 1 \cdots, r_i\),否则就是 \(l_i, l_i + 1, \cdots m - 1, m, 1, 2, \cdots r_i\)),向区间中的每个太空站提供 \(a_i\) 单位的陨石样本。

输出格式

输出 \(n\) 行。第 \(i\) 行的数 \(w_i\) 表示第 \(i\) 个国家在第 \(w_i\) 波陨石雨之后能够收集到足够的陨石样本。如果到第 \(k\) 波结束后仍然收集不到,输出 NIE

数据范围

\(1\le n,m,k\le 3\cdot10^5\);

\(1\le p_i,a_i\le 10^9\);

题目描述

Byteotian Interstellar Union (BIU) has recently discovered a new planet in a nearby galaxy. The planet is unsuitable for colonisation due to strange meteor showers, which on the other hand make it an exceptionally interesting object of study.

The member states of BIU have already placed space stations close to the planet's orbit. The stations' goal is to take samples of the rocks flying by.

The BIU Commission has partitioned the orbit into \(m\) sectors, numbered from \(1\) to \(m\), where the sectors \(1\) and \(m\) are adjacent. In each sector there is a single space station, belonging to one of the \(n\) member states.

Each state has declared a number of meteor samples it intends to gather before the mission ends. Your task is to determine, for each state, when it can stop taking samples, based on the meter shower predictions for the years to come.

输入格式

The first line of the standard input gives two integers, \(n\) and \(m\) (\(1\le n,m\le 300\ 000\)), separated by a single space, that denote,respectively, the number of BIU member states and the number of sectors the orbit has been partitioned into.

In the second line there are \(m\) integers \(o_i\) (\(1\le o_i\le n\)),separated by single spaces, that denote the states owning stations in successive sectors.

In the third line there are \(n\) integers \(p_i\) (\(1\le p_i\le 10^9\)),separated by single spaces, that denote the numbers of meteor samples that the successive states intend to gather.

In the fourth line there is a single integer \(k\) (\(1\le k\le 300\ 000\)) that denotes the number of meteor showers predictions. The following \(k\) lines specify the (predicted) meteor showers chronologically. The \(i\)-th of these lines holds three integers \(l_i,r_i,a_i\) (separated by single spaces), which denote that a meteor shower is expected in sectors \(l_i,l_{i+1},...,r_i\)(if \(l_i\le r_i\)) or sectors \(l_i,l_{i+1},...,m,1,...,r_i\) (if \(l_i>r_i\)) , which should provide each station in those sectors with \(a_i\) meteor samples (\(1\le a_i\le 10^9\)).

输出格式

Your program should print \(n\) lines on the standard output.

The \(i\)-th of them should contain a single integer \(w_i\), denoting the number of shower after which the stations belonging to the \(i\)-th state are expected to gather at least \(p_i\) samples, or the word NIE (Polish for no) if that state is not expected to gather enough samples in the foreseeable future.

样例 #1

样例输入 #1

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

样例输出 #1

3
NIE
1

原题链接

第一眼没有什么思路。
考虑一下整体二分的模板是怎么样的

离线动态求给定区间第k大值
先想想暴力的思路。
如果这个区间不是环形,那么就是直接线段树模拟,区间加减。
但是问题是询问是判断每一个数字是否等于另一个数字
这个是做不到的(就我现在知道的算法没有能够快速解决的)

看了题解。想不到是因为没有往二分答案的方向去想。
整体二分其实本质是二分答案,但是又不太一样,差别很大
发现这个答案是单调的,如果x最小时刻,那比x小的时候都不可以,比x大的时候都可以

按照之前的例题的思路,整体二分是把二分答案过程的消息充分利用上,所以自然也是建立在对一个点的基础的二分答案之上的

设整体二分函数\(solve(l,r,st,ed)\)表示在值域\([st,ed]\)上处理第\([l,r]\)个国家的的陨石,其中st和ed的含义是最少和最多第几场可以结束(时间上的值域)
取\(mid=(st+ed)/2\),对每一个国家的询问用树状数组判断在mid的时候有没有收集够,如果够了就放到后面的部分,不够就在前面。
二分的复杂度加上树状数组的复杂度,总复杂度\(O(n*(log_2n)^2)\)

现在回过头去看上一题,理解也更深了,我之前只是知道整体二分在二分答案的过程上充分利用信息来加速,没注意到二分答案在考虑思路的时候的这么重要的地位

开始的时候的没有思路和在看普通的二分答案的题目的时候的感觉很想。
这个可以动态统计一个区间中和0相等的数字数量并且支持区间修改的数据结构目前我还是不知道,桶是可以做到统计的,但是区间修改是支持不了一点,我上次碰到的题目是暴力。这次碰到的题目是整体二分,这个是因为只有区间加,那就是有答案单调性,所以能二分答案。

这个感觉比CDQ分治更灵活一些,可能是因为二分答案更灵活一些吧

环形的处理只是添头,直接把超过首尾的拆开就好了

但是好像没结束,如果是暴力统计每一场流星雨,那么每次统计的总复杂度会达到\(O(n*m*log(Size))\)
那就要优化了,可以发现,每一次的流星雨是区间修改,那么我们就直接把每一次流星雨区间修改在那个空间站上,然后再查询没过国家的陨石数的时候,就用邻接表把每一个位置穿起来,这样的总复杂度就是\(O(m*log(Size)+n)\),相当于单次是\(O(nlogn)\)级别的,是可以接受的,整个算法的复杂度就是\(O(n(logn)^2)\),二分答案一共\(logn\)层嘛

在紫题里面算是难度中等的吧,我感觉,因为嵌套的做法稍微有点多,而且,挺自然的,不是那种很暴力的嵌套,让我自己想应该是想不到的。

学到了,这个区间修改+邻接表。
然后是对整体二分的理解更深了一点吧,整体二分一定是建立在二分答案的基础上的。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
	char c=getchar();ll a=0,b=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll n,m,k,sta[300001],tr[300001],ans[300001];
inline ll lowbit(ll x)
{
	return x&(-x);
}
inline void add(ll i,ll x)
{
	while(i<=m*2)
	{
		tr[i]+=x;
		i+=lowbit(i);
	}
}
inline ll ask(ll i)
{
	ll ans=0;
	while(i>0)
	{
		ans+=tr[i];
		i-=lowbit(i);
	}
	return ans;
}
struct edge
{
	ll next,to;
}e[300001];
ll head[300001],tot;
inline void add1(ll i,ll j)
{
	e[++tot].next=head[i];
	e[tot].to=j;
	head[i]=tot;
}
struct node1
{
	ll l,r,a;
}p[300001];
struct node2
{
	ll id,c;
}per[300001],pl[300001],pr[300001];
void solve(ll st,ll ed,ll l,ll r)//stºÍedÊÇÖµÓò¶øµÚlµ½µÚr¼Ò¹«Ë¾ÊÇÔÚÕâ¸öÖµÓòÉÏÍê³ÉµÄ 
{
	if(l>r)return;
//	cout<<st<<' '<<ed<<' '<<l<<' '<<r<<endl;
//	if(st==1&&ed==2&&l==1&&r==2)
//	{
//		for(int i=1;i<=m*2;i++)
//		{
//			cout<<ask(i)-ask(i-1)<<' ';
//		}
//		cout<<endl;
//		cout<<"**\n";
//		for(int i=l;i<=r;i++)
//		{
//			cout<<per[i].id<<' '<<per[i].c<<' ';
//		}
//		cout<<endl;
//	}
	if(st==ed)
	{
		for(ll i=l;i<=r;i++)
		{
			ans[per[i].id]=st;
		}
		return;
	}
	ll mid=(st+ed)>>1;
	for(ll i=st;i<=mid;i++)
	{
		add(p[i].l,p[i].a);
		add(p[i].r+1,-p[i].a);
	}
//	if(st==1&&ed==3&&l==1&&r==2+1)
//	{
//		for(int i=1;i<=m*2;i++)
//		{
//			cout<<ask(i)<<' ';
//		}
//		cout<<endl;
//	}
	ll tl=0,tr=0;
	for(ll i=l;i<=r;i++)
	{
		ll tmp=0;
		for(ll j=head[per[i].id];j!=0&&tmp<=per[i].c;j=e[j].next)
		{
			ll u=e[j].to;
			tmp+=ask(u+m)+ask(u);
		}
		if(tmp>=per[i].c)
		{
			pl[++tl]=per[i];
		}
		else
		{
			pr[++tr]=per[i];
			pr[tr].c-=tmp;
//			if(st==1&&ed==3&&l==1&&r==2+1&&i==2)
//			{
//				cout<<pr[tr].id<<' '<<pr[tr].c<<"???\n";
//			}
		}
	}
	for(ll i=st;i<=mid;i++)
	{
		add(p[i].l,-p[i].a);
		add(p[i].r+1,p[i].a);
	}
	for(ll i=l;i<=l+tl-1;i++)
	{
		per[i]=pl[i-l+1];
	}
	for(ll i=l+tl;i<=r;i++)
	{
		per[i]=pr[i-l-tl+1];
	}
	solve(st,mid,l,l+tl-1);
	solve(mid+1,ed,l+tl,r);
}
int main()
{
//	freopen("2.in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read();
	for(ll i=1;i<=m;i++)
	{
		ll ned=read();
		add1(ned,i);
	}
//	cout<<endl;
//	for(int i=head[2];i!=0;i=e[i].next)
//	{
//		cout<<e[i].to<<' ';
//	}
//	cout<<endl<<endl;
	for(ll i=1;i<=n;i++)
	{
		per[i].c=read();
		per[i].id=i;
	}
	k=read();
	for(ll i=1;i<=k;i++)
	{
		ll l=read(),r=read(),a=read();
		if(l>r)r+=m;
		p[i].l=l;p[i].r=r;p[i].a=a;
	}
	solve(1,k+1,1,n);
	for(ll i=1;i<=n;i++)
	{
		if(ans[i]!=k+1)
			cout<<ans[i]<<endl;
		else 
			cout<<"NIE"<<endl;
	}
	return 0;
}

唉唉,终于,调出来了,一天啊
好多细节,主要还是写代码的时候一定要专注

这个整体二分,其实像是多次询问的二分答案的做法。
其实算是二分答案的加强版,我感觉应用会非常非常广泛,比CDQ分治无脑转化三维偏序会灵活很多
再写两题总结看看

标签:二分,le,Meteors,ed,ll,POI2011,st,MET,答案
From: https://www.cnblogs.com/HLZZPawa/p/17968679

相关文章

  • Jmeter之插件安装
    在实际工作中,会用到一些额外的jmeter插件,现在描述其插件的安装。 一、下载plugins-manager.jar在官网中下载plugins-manger.jar,方便后续其他插件的安装,下载地址如下:https://jmeter-plugins.org/install/Install/  点击下载。 二、Plugin-manager.jar配置和......
  • 关于修改prometheus-operator 方式下的prometheus的配置文件
    fq简单介绍prometheus-operator中的每个PrometheusCRD资源,Operator都会以StatefulSet形式在相同的命名空间下部署对应配置的资源,PrometheusPod的配置是通过一个包含Prometheus配置的名为的Secret对象声明挂载的。该CRD根据标签选择来指定部署的Prometheus实......
  • 关于修改Prometheus指标告警阈值
     方法一:在rancher平台仪表盘里修改 修改告警规则的配置文件 修改阈值并保存 rules界面查看是否生效 方法二: ......
  • 关于命令行修改K8s内Prometheus配置文件参数
    #登录master节点操作1、进入prometheus介质目录:[root@k8s-master01]$cd/yang/operator/operator-0.7/manifests/prometheus2、备份prometheus配置文件[root@k8s-master01]$cpprometheus-prometheus.yamlprometheus-prometheus.yaml.202312153、编辑prometheus配置文件修......
  • jmeter并发与持续压测生成测试报告操作日志
    接口压测的方式:1、同时并发:设置线程组、执行时间、循环次数,这种方式可以控制接口请求的次数2、持续压测:设置线程组、循环次数,勾选“永远”,调度器(持续时间),这种方式可以控制压测周期时间指定并发数 例1:设置线程数:10;设置执行时间:0;设置循环次数:5说明:使10个线程启动并同时运......
  • docker jmeter分布式压测部署 jmeter websocket压测
    测试场景:1.多名用户加入房间。2.房间人数为固定人数(比如4人) 3.有人进入时,进入用户会收到反馈当前房间人员列表。4.其他人会收到反馈新加入用户的信息消息。5.当人数已满时,会自动推送消息给所有人。6.在人满后,每个人需要按固定序列,发送消息。7.所有人发送特定消息后,推进房......
  • 【JMeter】jmeter 操作 mysql 数据库
    一、下载驱动包二、JDBC连接配置三、JDBCRequest1、单条查询语句2、多条查询语句3、增删改语句4、参数化sql语句5、占位符语句 本文内容基于如下测试环境:JMeter4.0版本Win7系统mysql-connector-java-5.1.7-bin.jar不同环境下可能会有不一致的地方。......
  • JMeter测试WebSocket的经验总结
    最近有一个微信聊天系统的项目需要性能测试,既然是测试微信聊天,肯定绕不开websocket接口的测试,首选工具是Jmeter,网上能搜到现成的方法,但是网上提供的jar包往往不是最新的,既然是用最新版本的Jmeter4.0,那么所依赖的插件jar包也应该追求新的。所以提供了以下链接供大家下载(甚至连源码......
  • jmeter jdbc操作myql数据库及mysql驱动下载
     mysql驱动下载https://dev.mysql.com/downloads/connector/j/   1、先安装mysql的驱动mysql-connector-java-5.1.7-bin.jar配置jdbc的connectionconfigurationDatabaseUrl:jdbc:mysql://xxx.xxx.xxx.xxx:3306/test?allowMultiQueries=true&serverTimezone=UTC&c......
  • java调用jmeter集群服务压力测试 jmeter数据库压测
    目录〇、前言。一、jmeter工具安装。二、数据库驱动插件jar包安装。三、脚本开发与调试。四、加压设置。五、数据监听。  正文〇、前言。依据云栖大会项目部分数据库压测经验编写。一、jmeter工具安装。1、Apache官网下载地址:https://jmeter.apache.org/download_j......