自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 21:37:45，当前版本为作者最后更新于2020-04-26 18:08:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

感觉这个题卡空间没什么用（雾

查询的是区间$average,max,min,$众数$,$但是数只有$100$种取值$.$

一种想法是考虑对$100$种取值做前缀和$,$然后每组询问$O(q*100)$来做$,$但需要$O(n*100)$的空间$.$

那么我们就每$S$个数分一块$,$然后维护块之间的前缀和$,$边角暴力即可$.$

时间复杂度$O(\frac{n}{S}*100 +q*max(100+2S))$

空间复杂度$O(\frac{n}{S}*100).$

令$S = 40,$此时空间可看做线性$,$时间仍然为$O(q*100).$

代码$:$

#include <bits/stdc++.h>
#define LL long long
using namespace std;
template <typename T> void read(T &x){
	static char ch; x = 0,ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
const int N = 200005,S = 40;
int n,m,a[N],b[N],cur[N],cl[N],cr[N],prea[N],preb[N],cnt[101][N/S+5],now[101];
int main(){
	register int i,j; int op,l,r,curl,curr,ans,mx,mn; ios::sync_with_stdio(0);
	read(n),read(m);
	for (i = 1; i <= n; ++i) read(a[i]);
	for (i = 1; i <= n; ++i) cur[i] = (i-1)/S+1,read(b[i]),prea[i] = prea[i-1] + a[i] * b[i],preb[i] = preb[i-1] + b[i];
	for (i = 1; i <= cur[n]; ++i){
		cl[i] = S*(i-1)+1,cr[i] = min(n,S*i);
		for (j = 1; j <= 100; ++j) cnt[j][i] = cnt[j][i-1];
		for (j = cl[i]; j <= cr[i]; ++j) cnt[a[j]][i] += b[j]; 
	}
	while (m--){
		read(op),read(l),read(r);
		if (op==1){ cout << fixed << setprecision(2) << ((double)(prea[r]-prea[l-1])) / (preb[r]-preb[l-1]) << '\n'; continue; }
		memset(now,0,sizeof(now));
		curl = cur[l],curr = cur[r];
		if (curl + 1 >= curr) for (i = l; i <= r; ++i) now[a[i]] += b[i];
		else{
			for (i = l; i <= cr[curl]; ++i) now[a[i]] += b[i];
			for (i = cl[curr]; i <= r; ++i) now[a[i]] += b[i];
			for (i = 1; i <= 100; ++i) now[i] += cnt[i][curr-1] - cnt[i][curl];
		}
		if (op==2) for (ans = 1,i = 2; i <= 100; ++i) if (now[i] > now[ans]) ans = i;
		if (op==3){
			for (i = 1; i <= 100; ++i) if (now[i]){ mn = i; break; }
			for (i = 100; i ; --i) if (now[i]){ mx = i; break; }
			ans = mx-mn;
		}
		cout << ans << '\n';
	}
	return 0;
}