自动搬运

查看原文

来自洛谷，原作者为

	xiwang **

搬运于2025-08-24 21:55:05，当前版本为作者最后更新于2018-03-29 08:13:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在网上听人说这题暴力可过，本着no zuo no die的心态试了一发...

结果不仅过了，还跑得比香港记者还快，我甚至还没开氧气优化！

我将发动同学写此题，此题将成为一道省选红题

正解好像是平衡树?

upd:加点完全不必要的说明

id/fid记录每部电影存在数组里的编号/R操作给出的编号

Q:直接把所有电影存进数组排序即可

R:直接按题意模拟即可

C:fid转换编号直接按题意修改即可

直接暴力搞就好了

上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ddf;
const int N=100000+10;
int id[N],fid[N],ac[N],tot,n;
ddf s[N];
struct node{
	ddf x;
	int y;
}a[N];
bool cmp(node a,node b){
	return a.x==b.x?a.y<b.y:a.x>b.x;
}
char b[16];
int main(){
	int x,y,z;
	ddf xp,yp,zp;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",b);
		if(b[0]=='Q'){
			scanf("%d",&x);
			for(int i=1;i<=tot;i++)a[i]=(node){s[i],i};
			sort(a+1,a+1+tot,cmp);
			printf("%d\n",id[a[x].y]);
		}
		else if(b[0]=='R'){
			int mx=0;
			scanf("%d%d",&x,&y);
			id[++tot]=x;
			fid[x]=tot;
			for(int i=1;i<=y;i++){
				scanf("%d",&z);
				mx=max(mx,ac[z]);
				ac[z]=tot;
			}
			s[tot]=s[mx];
		}
		else {
			scanf("%d%lf",&x,&xp);
			x=fid[x];
			s[x]=(s[x]+xp)/2;
		}
	}
	return 0;
}
/*
10
R 1 1 1
R 2 2 1 2
C 2 2
R 3 1 2
Q 1
C 3 2
C 1 5
Q 1
Q 2
Q 3
*/