RE on #2,普通莫队
查看原帖
RE on #2,普通莫队
838570
Double_Sheep楼主2024/3/6 21:58

为什么会 RE 啊?还有一个点是 TLE。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int n,m,B,a[N],sum[N],maxv,b[N],c[N],bv[N];
int v[N],tmp[N],vl[N],vr[N],sump[N],sumb[N];
ll k[N],num[N],ans[N];
vector<int> base[N];
struct Q {
	int l,r,id;
}q[N];
inline bool cmp(const Q &x,const Q &y) {
	if(b[x.l] != b[y.l]) return b[x.l] < b[y.l];
	if(b[x.l] & 1) return x.r < y.r;
	return x.r > y.r;
}
inline void add(const int &now) {
	if(c[tmp[now]] < 0) {
		c[tmp[now]]++; return;
	}
	int kv = base[tmp[now]][c[tmp[now]]];
	int val = base[tmp[now]][++c[tmp[now]]];
	sump[val]++,sumb[bv[val]]++;
	sump[kv]--,sumb[bv[kv]]--;
}
inline void del(const int &now) {
	if(c[tmp[now]] <= 0) {
		c[tmp[now]]--; return;
	}
	int kv = base[tmp[now]][c[tmp[now]]];
	int val = base[tmp[now]][--c[tmp[now]]];
	sump[val]++,sumb[bv[val]]++;
	sump[kv]--,sumb[bv[kv]]--;
}
inline int query() {
	int id = 0;
	for(int b = bv[maxv];b >= 0;b--)
		if(sumb[b] > 0) {id = b; break;}
	if(!id) return 0;
	for(int p = vr[id];p >= vl[id];p--)
		if(sump[p]) return p;
}
int main() {
    scanf("%d%d",&n,&m); B = n / sqrt(m);
    for(int i = 1;i <= n;i++)
    	scanf("%d",&a[i]);
    for(int i = 1;i <= m;i++) {
    	scanf("%d%d",&q[i].l,&q[i].r);
    	q[i].id = i;
	}
	sort(q + 1,q + m + 1,cmp);
    for(int i = 1;i <= n;i++)
    	sum[a[i]]++,num[i] = 1ll * a[i] * sum[a[i]];
    sort(num + 1,num + n + 1);
    memset(sum,0,sizeof(sum));
    for(int i = 1;i <= n;i++) {
    	b[i] = i / B,sum[a[i]]++;
    	int now = upper_bound(num + 1,num + n + 1,1ll * a[i] * sum[a[i]]) - num - 1;
    	if(sum[a[i]] == 1) {
    		base[now].push_back(0);
    		base[now].push_back(now),v[a[i]] = now;
		} else base[v[a[i]]].push_back(now);
		maxv = max(maxv,now),k[now] = 1ll * a[i] * sum[a[i]],num[now]++;
	}
	for(int i = 1;i <= n;i++) tmp[i] = v[a[i]];
	B = sqrt(maxv) + 1;
	for(int i = 1;i <= maxv;i++) {
		bv[i] = i / B + 1;
		if(bv[i] != bv[i - 1])
			vr[bv[i - 1]] = i - 1,vl[bv[i]] = i;
	}
	int l = 1,r = 0; vr[bv[maxv]] = maxv;
	for(int i = 1;i <= m;i++) {
		while(l > q[i].l) add(--l);
		while(r < q[i].r) add(++r);
		while(l < q[i].l) del(l++);
		while(r > q[i].r) del(r--);
		ans[q[i].id] = k[query()];
	}
	for(int i = 1;i <= m;i++)
		printf("%lld\n",ans[i]);
    return 0;
}
2024/3/6 21:58
加载中...