洛谷P4032 火锅盛宴

传送门

题目背景

SkyDec和YJQQQAQ都是Yazid的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。

题目描述

在这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和n种食物，每种食物数量都是无限的。我们用11至nn将这些食材编号。

每种食物煮熟所需要的时间不同，第ii种食物煮熟需要s_is
i
​
单位时间。这表示如果你在第TT个时刻将一个食物ii下到火锅里，那么它会在第T+s_iT+s
i
​
个时刻被煮熟，并且此后一直会延续被煮熟的状态，直到它被拿走为止。

Yazid和YJQQQAQ的口味不同：YJQQQAQ觉得所有食物的好吃程度都是相同的；而Yazid则觉得没有两种食材的好吃程度是相同的，并且，巧合的是，编号越小的食物Yazid越喜欢吃。可怜的SkyDec由于不能吃辣，所以只能帮Yazid和YJQQQAQ煮食物。

整个火锅盛宴持续10^910
9
单位时间。在整个盛宴中，三位好朋友除了谈笑风生之外，最重要的事当然就是吃东西了。在任意整数时刻，都有可能发生下列4种事件中的任意一种，我们用00至33之间的整数opop描述事件类型：

0 id：表示SkyDec往火锅里下了一个编号为idid的食物。

1：Yazid在锅内搜寻熟了的且最喜欢吃的食物，并拿走一个这种食物。特别地，如果锅里没有熟了的食物，那么Yazid会很愤怒。

2 id：YJQQQAQ在锅内搜寻编号为idid的食物：如果锅里不存在该种食物，则YJQQQAQ会很愤怒；如果锅里存在熟了的该食物，则YJQQQAQ会取走一个并食用；如果锅里只有未煮熟的该种食物，那么YJQQQAQ会希望知道最接近煮熟的该种食物（即锅内存在时间最长的该种食物）还需要多少时间被煮熟。

3 l r:馋涎欲滴的SkyDec想知道，锅里编号在[l,r][l,r]之间的且熟了的食物总共有多少个。

输入格式

从标准输入读入数据。

本题包含多组数据，输入的第一行为一个正整数TT，表示数据组数。接下来依次描述每组数据，对于每组数据：

第一行一个正整数nn，表示食物的种类数。

第二行nn个用空格隔开的正整数s_1,s_2,…s_ns
1
​
,s
2
​
,…s
n
​
，描述每种食物煮熟需要的时间。

第三行一个正整数QQ，表示事件的数目。

接下来QQ行，每行若干个用空格隔开的非负整数，描述一个事件。先是两个整数t,opt,op，分别表示发生事件的时间以及事件的类型。如果op=0op=0或op=2op=2，则接下来11个正整数idid，意义见题目描述；如果op=1op=1，则接下来没有其他数；如果op=3op=3，则接下来22个正整数l,rl,r，意义见题目描述。

我们保证tt按输入顺序严格递增。

我们保证1\leq t\leq 10^91≤t≤10
9
，0\leq op\leq 30≤op≤3，1\leq id\leq n1≤id≤n，1\leq l\leq r\leq n1≤l≤r≤n。

输出格式

对于每个op\neq 0op

=0的操作，输出一行表示答案。对于不同的opop，需要输出的内容如下：

对于op=1op=1，如果Yazid成功取走食物，则输出他取走食物的编号；否则输出"Yazid is angry."（不含引号，下同）。

对于op=2op=2，如果YJQQQAQ成功取走食物，则输出"Succeeded!“；否则，如果锅里有未煮熟的该类食物，输出最接近煮熟的该种食物还需要多少时间被煮熟；否则，输出"YJQQQAQ is angry.”。

对于op=3op=3，输出锅内编号在指定范围内的熟食的数量。

输出到标准输出。

输入输出样例

输入 #1复制
1
2
1 100
10
1 0 2
2 0 1
3 2 1
4 2 2
5 2 1
200 0 1
201 3 1 2
202 1
203 1
204 1
输出 #1复制
Succeeded!
97
YJQQQAQ is angry.
2
1
2
Yazid is angry.

说明/提示

对于所有数据，保证T\leq 4T≤4，保证n\leq 100,000n≤100,000，Q\leq 500,000Q≤500,000，1\leq s_i\leq 10^81≤s
i
​
≤10
8
。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/王聿中 命题/王聿中 验题/吕时清，杨景钦

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。

上代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
using namespace std;
int n;
const int mx=101010;
inline int Read(){
    
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
}
queue<int>food[mx];
int q_num;//询问总数 
int cost[mx];//每种食物需要的时间 
#define lowbit(i) i&-i
int tree[mx];
void change(int pos,int k){
    //pos位置+k 
	while(pos<=n){
    
		tree[pos]+=k;
		pos+=lowbit(pos);
	}
}
int query(int pos){
    //查询到pos为止有多少个食物 
	int ans=0;
	while(pos>=1){
    
		ans+=tree[pos];
		pos-=lowbit(pos);
	}
	return ans;
}
struct FOOD{
    //食物 
	int t;//煮熟时间 
	int pos;//食物编号
}; 
struct cmp1{
    
	bool operator () (const FOOD &a,const FOOD &b)const{
    
		return a.t>b.t;//按照结束时间从小到大排 
	}
};
priority_queue<FOOD,vector<FOOD>,cmp1>f1;//食物
void query_1(){
    //第一个问题：拿出编号最小的食物 
	if(!query(n)){
    //没有任何食物 
		printf("Yazid is angry.\n");
		return;
	}
	int l=1,r=n,mid=(l+r)>>1;
	while(l<r){
    
		if(query(mid)-query(l-1))r=mid;
		else l=mid+1;
		mid=(l+r)>>1;
	}
	printf("%d\n",mid);
	food[mid].pop();//食物出堆 
	change(mid,-1);
	return;
}
void query_2(int pos,int t){
    //第二问，pos食物是否有熟的，如果没有，最快熟的还要多久 
	if(food[pos].empty()){
    //没有该食物 
		printf("YJQQQAQ is angry.\n");
		return;
	}
	int tp=food[pos].front();
	if(tp<=t){
    //熟了 
		printf("Succeeded!\n");
		food[pos].pop();//从堆中删除该食物 
		change(pos,-1);//从树状数组中删除该食物 
		return;
	}
	else{
    
		printf("%d\n",tp-t);
		return;
	}
}
void query_3(int l,int r){
    //第三个问题：查询[l,r]之间有多少个食物 
	printf("%d\n",query(r)-query(l-1));
	return;
}
int main(){
    
	int T=Read();
	while(T--){
    
		q_num=0;
		n=Read();
		for(int i=1;i<=n;++i)cost[i]=Read();
		int num=Read();
		for(int i=1;i<=num;++i){
    
			int t=Read();
			int opt=Read();
			if(!f1.empty()){
    
				FOOD tp=f1.top();
				while(tp.t<=t){
    
					f1.pop();
					change(tp.pos,1);
					if(f1.empty())break;
					tp=f1.top();
				}
			}
			if(opt==0){
    
				int pos=Read();
				FOOD a;
				a.pos=pos;
				a.t=t+cost[pos];
				f1.push(a);
				food[pos].push(t+cost[pos]);
			}
			else if(opt==1){
    
				query_1();
			}
			else if(opt==2){
    
				int pos=Read();
				query_2(pos,t);
			}
			else{
    
				int l=Read(),r=Read();
				query_3(l,r);
			}
		}
		//清除数据，为下一组数据做准备 
		memset(tree,0,sizeof(tree));
		while(!f1.empty())f1.pop();
		for(int i=1;i<=n;i++)while(!food[i].empty())food[i].pop();//清空队列
	}
	return 0;
}