- 2026-10-08
If you 50pts WA on #3.
- @ 2026-10-9 9:11:49
不明白为什么把 的值改成 而不是 就能过了。 这题感觉写线段树太麻烦,而且常数大,跑得慢,尽量 表。
#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 条评论
目前还没有评论...