不明白为什么把 NN 的值改成 1.5e51.5e5 而不是 2e52e5 就能过了。 这题感觉写线段树太麻烦,而且常数大,跑得慢,尽量 STST 表。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1.5e5 + 5;
int n, m, a[N], l, r;
struct tree {
	int l, r, num;
}tr[N << 3];
void pushup(int u) { tr[u].num = max(tr[u << 1].num, tr[u << 1 | 1].num); }
void build(int u, int l, int r) {
	tr[u].l = l, tr[u].r = r;
	if(l == r) { tr[u].num = 0; return ; }
	int mid = (l + r) >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}
void update(int u, int p, int x) {
	if(tr[u].l > p || tr[u].r < p) return ;
	if(tr[u].l == tr[u].r) { tr[u].num+=x; return ; }
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(p <= mid) update(u << 1, p, x);
	else update(u << 1 | 1, p, x);
	pushup(u);
}
int query(int u, int l, int r) {
    if(l > r) return 0;
	if(tr[u].l >= l && tr[u].r <= r) { return tr[u].num; }
	if(tr[u].l > r || tr[u].r < l) return 0;
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(r <= mid) return query(u << 1, l, r);
	if(l > mid) return query(u << 1 | 1, l, r);
	return max(query(u << 1, l, r), query(u << 1 | 1, l, r));
}
int fst[N << 1], lst[N << 1];
unordered_map<int, bool> vis;
int cpt[N << 1];
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while(cin >> n) {
		if(!n) break;
		cin >> m;
        memset(lst, 0, sizeof(lst));
        memset(fst, 0, sizeof(fst));
        memset(cpt, 0, sizeof(cpt));
        vis.clear();
		for(int i=1; i<=n; ++i) cin >> a[i], a[i] += (N - 5);
		for(int i=1; i<=n; ++i) {
			if(!vis[a[i]]) {
				vis[a[i]] = 1;
				fst[a[i]] = i;
				lst[a[i - 1]] = i - 1;
			}
		}
		build(1, 0, (N - 5) << 1);
		for(int i=1; i<=n; ++i) {
            cpt[a[i]]++;
		}
        for(int i=0; i<=200000; ++i) {
            if(cpt[i]) {
                update(1, i, cpt[i]);
            }
        }
        lst[a[n]] = n;
		for(int i=1; i<=m; ++i) {
			cin >> l >> r;
			if(l == r) {
				cout << 1 << '\n';
				continue;
			}
			if(a[l] == a[r]) {
				cout << r - l + 1 << '\n';
				continue;
			}
            int num1 = lst[a[l]] - l + 1, num2 = r - fst[a[r]] + 1;
            int ans = max(num1, max(num2, query(1, a[l] + 1, a[r] - 1)));
            cout << ans << '\n';
		}
	}
	return 0;
}

0 条评论

目前还没有评论...