MLE求调

#include <bits/stdc++.h>
using namespace std;
#define int long long
char *pa, *pb, buf[1000000];
#define nc() (pa==pb && (pb=(pa=buf)+fread(buf,1,1000000,stdin),pa==pb)?EOF:*pa++)
inline int in() 
{
	int x = 0, f = 1; char c = nc();
	while (c < 48 || c > 57) f = c == 47 ? -1 : 1, c = nc();
	while (c >= 48 && c <= 57) x = (x<<1) + (x<<3) + c-48, c = nc();
	return x * f;
}

const int N = 2e5+5;
int n, q, a[N], b[N], c[N], 
	sc[N], sb[N], 
	t, cnt[101][N/58+5], 
	stx[N][25], stn[N][25], 
	opt, u, v;
	
void inits() 
{
	for (int i = 1; i <= n; ++i) {
		sc[i] = sc[i-1] + c[i];
		sb[i] = sb[i-1] + b[i];
	}
}

inline double qrys(int u, int v) 
{
	return (double) (sc[v] - sc[u-1]) / (sb[v] - sb[u-1]);
}

void initz() 
{
	t = 1;
	while (t*t*t <= n) ++t;--t;
	for (int i = 1; i*t <= n; ++i) {
		for (int k = t*(i-1)+1; k <= t*i; ++k) {
			cnt[a[k]][i] += b[k];
		}
	}
}

inline int qryz(int u, int v) 
{
	int i = u%t ? u/t+1 : u/t, j = v%t ? v/t-1 : v/t;
	int p = i/t+1, q = j/t+1;
	int ct[101];
	memset(ct, 0, sizeof(ct));
	for (int r = 1; r <= 100; ++r) {
		for (int k = p; k <= q; ++k) {
			if (cnt[r][k]) ct[r] += cnt[r][k];
		}
	}
	if (u != i) {
		for (int k = u; k < i; ++k) ct[a[k]] += b[k];
	}
	if (v != j) {
		for (int k = j+1; k <= v; ++k) ct[a[k]] += b[k];
	}
	int res = 0, z = 0;
	for (int k = 1; k <= 100; ++k) if (z < ct[k]) {
		z = ct[k];
		res = k;
	}
	return res;
}

void initst() 
{
	memset(stx, 0, sizeof(stx));
	memset(stn, 0x7f, sizeof(stn));
	for (int i = 1; i <= n; ++i) stx[i][0] = stn[i][0] = a[i];
	for (int j = 1; (1<<j) <= n; ++j) {
		for (int i = 1; i + (1<<j) - 1 <= n; ++i) {
			stx[i][j] = max(stx[i][j-1], stx[i+(1<<j-1)][j-1]);
			stn[i][j] = min(stn[i][j-1], stn[i+(1<<j-1)][j-1]);
		}
	}
}

inline int qryc(int u, int v) 
{
	if (u == v) return 0;
	int t = 1;
	while ((1<<t) <= v-u+1) t <<= 1;
	t >>= 1;
	return max(stx[u][t], stx[v-(1<<t)+1][t]) - min(stn[u][t], stn[v-(1<<t)+1][t]);
}

signed main() 
{
	freopen("P2442.txt", "r", stdin);
	n = in(), q = in();
	for (int i = 1; i <= n; ++i) a[i] = in();
	for (int i = 1; i <= n; ++i) b[i] = in();
	for (int i = 1; i <= n; ++i) c[i] = a[i]*b[i];
	inits();
	initz();
	initst();
	while (q--) {
		opt = in(), u = in(), v = in();
		switch (opt) {
			case 1 : {
				printf("%.2lf\n", qrys(u, v));
				break;
			}
			case 2 : {
				printf("%d\n", qryz(u, v));
				break;
			}
			case 3 : {
				printf("%d\n", qryc(u, v));
				break;
			}
		}
	}
	return 0;
}