列表

详情

NC200049. Mars Automaton

描述

在火星某科学的研究所中，正在进行着一项关于“人工稳定可再生能源 (Artificial Stable Renewable Energy Resources)” 的研究，研究的过程中使用了一种被称为“Mars Automaton”（火星机器人，或战神机器人）的机器人，别名叫做"Auto-Correct Automaton"，因为某种地球时代遗留下来的传统，研究者们通常把它简称作“AC机器人”，象征着某种美好的意义。

这种机器人可以合体，当若干个机器人走到同一个位置上，它们就会合体变成更大的机器人，并且其大小是所有参与合体的机器人的大小之和。

工作台上有n个用来放置机器人的位置，这些位置在同一条直线上，为了方便同事沟通，研究员从左到右依次对这些位置从1到n进行编号。相邻的两个位置之间铺设有轨道，机器人可以沿着轨道走到相邻的位置上。
对于摆放着机器人的位置，研究员会将这个位置与这个机器人的大小对应起来并进行记录。
初始时，所有位置上都摆放着大小为1的AC机器人。

研究员会不停地做两种操作：
1. 将从的位置上全部替换为大小为1的AC机器人（对于没有放置机器人的位置，会直接摆上大小为1的机器人）。
2. 将的所有位置与其它位置孤立，之后让这一段区间上的所有机器人行动起来，AC机器人被设定了“采取正确行为”的指令，于是此区间的所有机器人会向右走 ()，但是因为这段区间被孤立处理，当机器人走到区间的最右端后便会停在最右端上，于是最后这个区间的所有机器人都会在区间的最右端上，并且合为一体。

为了获取实验数据，研究员想要知道在区间上有多少种不同大小的机器人。

形式化地说，对于一个长度为n的初始全1序列，之后会有多次三种操作：
1. 将区间[l, r]上的值全部修改为1。
2. 将区间[l, r]上的所有值求和，覆盖位置r上的值，之后区间内所有非r位置的值都会被设置为0。
3. 询问区间[l,r]上有多少种不同的非0数字。

输入描述

本题数据均匀随机生成。

输入第一行包含两个正整数n和q，之间使用一个空格符分隔，分别表示序列长度，以及操作次数。
接下来输入q行，将这样输入的第i行的第一个整数记作op_i，表示操作类型，对应于题目描述中的三种操作，接着在这一行输入两个正整数l_i和r_i，含义如题目所述，相邻整数之间使用一个空格符分隔。

数据规范：
* .
* .
* .
* .
* 保证除n和q外全部数据均匀随机生成（包含样例）。
* 如果在随机生成数据过程中出现了的情况，则数据生成器会交换这两个值，使得其满足条件。因此输入数据保证不会出现左端点大于右端点的情况。

输出描述

对于每个3操作，输出一个整数表示操作3的查询结果，每个整数占一行。

示例1

输入: 

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

输出: 

1

示例2

输入: 

1000 9
2 633 635
1 656 789
2 688 953
3 95 661
3 398 602
1 653 769
1 364 440
2 205 422
2 186 981

输出: 

2
1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 176ms, 内存消耗: 1824K, 提交时间: 2019-12-08 22:07:50 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,q,l,r,op;
namespace ODT//将区间推平 
{
	struct node{
		int l,r;
		ll val;//[l,r]区间值为val 
		node(){}
		node(int _l=-1,int _r=-1,ll _val=0):l(_l),r(_r),val(_val){}
		bool operator < (const node &right)const
		{
			return l<right.l;
		}
	};
	typedef set<node>::iterator SIT;
	set<node>tr;
	void print()
	{
		for(SIT it=tr.begin();it!=tr.end();it++)
			for(int j=1;j<=(it->r)-(it->l)+1;j++)
			printf("%d ",it->val);
	}
	SIT split(int pos)
	{
		SIT it=tr.lower_bound(node(pos));
		if(it!=tr.end()&&it->l==pos)
		return it;
		it--;
		node temp=*it;
		tr.erase(it);
		tr.insert(node(temp.l,pos-1,temp.val));
		return tr.insert(node(pos,temp.r,temp.val)).first;
	}
	void assign(int l,int r,ll val)//第一个操作 
	{
		SIT itl=split(l),itr=split(r+1);
		tr.erase(itl,itr);
		tr.insert(node(l,r,val));
	}
	void sum(int l,int r)//第二个操作 
	{
		SIT itl=split(l),itr=split(r+1);
		ll sum=0;
		for(SIT it=itl;it!=itr;it++)
		sum+=(it->val)*((it->r)-(it->l)+1);
		tr.erase(itl,itr);
		tr.insert(node(l,r-1,0));
		tr.insert(node(r,r,sum));
	}
	int query(int l,int r)//第三个询问 
	{
		set<ll>temp;
		SIT itl=split(l),itr=split(r+1);
		for(SIT it=itl;it!=itr;it++)
		{
			if(it->val!=0)
			temp.insert(it->val);
		}
		return temp.size();
	}
}
using namespace ODT;
int main()
{
	scanf("%d%d",&n,&q);
	tr.insert(node(1,n,1));
	while(q--)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		assign(l,r,1);
		else if(op==2)
		sum(l,r);
		else
		printf("%d\n",query(l,r));
	}
}

C++(clang++11) 解法, 执行用时: 123ms, 内存消耗: 524K, 提交时间: 2021-03-19 12:13:17 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int mod=1e9+7;
struct node{
	int l,r;
	mutable LL val;
	bool friend operator < (node a,node b){
		return a.l<b.l;
	}
};
set<node>s;
#define IT set<node>::iterator
IT split(int pos){
	IT it=s.lower_bound(node{pos});
	if(it!=s.end()&&it->l==pos)	return it;
	it--;
	int l=it->l,r=it->r;
	LL val=it->val;
	s.erase(it);
	s.insert(node{l,pos-1,val});
	return s.insert(node{pos,r,val}).first;
}
void assign(int l,int r,LL x){
	IT itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(node{l,r,x});
}
void change(int l,int r){
	LL sum=0;
	IT itr=split(r+1),itl=split(l);
	IT temp=itl;
	for(;itl!=itr;itl++)	sum+=(itl->val)*(itl->r-itl->l+1);
	s.erase(temp,itr);
	if(l!=r)	s.insert(node{l,r-1,0});
	s.insert(node{r,r,sum});
}
int query(int l,int r){
	set<LL>st;
	IT itr=split(r+1),itl=split(l);
	for(;itl!=itr;itl++){
		if(itl->val!=0)	st.insert(itl->val);
	}
	return st.size();
}
int n,q;
int main(){
	scanf("%d%d",&n,&q);
	s.insert(node{1,n,1});
	while(q--){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(l>r)	swap(l,r);
		if(op==1)	assign(l,r,1);
		if(op==2)	change(l,r);
		if(op==3)	printf("%d\n",query(l,r)); 
	}
	return 0;
}

上一题

© 2024 nowcoder.com