一个很猎奇的问题
查看原帖
一个很猎奇的问题
1059849
tjx114514楼主2025/5/27 18:05

这个代码,如果我的cnt数组开的是4e5就能过,但是2e5就过不了,一直找不到问题,求助

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5,N=2e5+5;
int n,q,bel,a[N],c[MAXN],cnt[N],res[N],L=1,R;
struct node{
	int a[MAXN],l[MAXN],r[MAXN],sum[MAXN],b[MAXN];
	void init(){
		for(int i=1;i<=n;i++) a[i]=sum[i]=0,b[i]=(i-1)/bel+1;
		for(int i=1;i<=n;i++) r[b[i]]=i;
		l[1]=1;
		for(int i=2;i<=n;i++) l[i]=r[i-1]+1;
	}
	void upd(int x,int k){
		if(x<=0) return;
		if(x>2e5) exit(1);
		sum[b[x]]+=k,a[x]+=k;
	}
	int ask(){
		for(int i=b[n];i>=1;i--){
			if(sum[i]){
				for(int j=r[i];j>=l[i];j--)
					if(a[j]) return j;
			}
		}
		return 0;
	}
}t;
struct qry{
	int l,r,id;
}b[MAXN];
inline bool cmp(qry x,qry y){
	if(x.l/bel<y.l/bel) return 1;
	if(x.l/bel>y.l/bel) return 0;
	if((x.l/bel)&1) return x.r<y.r;
	return x.r>y.r;
}
void add(int x){
	t.upd(cnt[a[x]]*c[cnt[a[x]]],-1);
	--c[cnt[a[x]]];
	t.upd(cnt[a[x]]*c[cnt[a[x]]],1);
	++cnt[a[x]];
	if(a[x]>2e5) exit(1);
	t.upd(cnt[a[x]]*c[cnt[a[x]]],-1);
	++c[cnt[a[x]]];
	t.upd(cnt[a[x]]*c[cnt[a[x]]],1);
}
void del(int x){
	t.upd(cnt[a[x]]*c[cnt[a[x]]],-1);
	--c[cnt[a[x]]];
	t.upd(cnt[a[x]]*c[cnt[a[x]]],1);
	--cnt[a[x]];
	t.upd(cnt[a[x]]*c[cnt[a[x]]],-1);
	++c[cnt[a[x]]];
	t.upd(cnt[a[x]]*c[cnt[a[x]]],1);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;bel=sqrt(n);
	t.init();
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>2e5) exit(1);
	}
	for(int i=1;i<=q;i++){
		cin>>b[i].l>>b[i].r;
		b[i].id=i;
	}
	sort(b+1,b+q+1,cmp);
	for(int i=1;i<=q;i++){
		int l=b[i].l,r=b[i].r;
		while(L<l) del(L++);
		while(L>l) add(--L);
		while(R>r) del(R--);
		while(R<r) add(++R);
		res[b[i].id]=t.ask();
	}
	for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
	return 0;
}
2025/5/27 18:05
加载中...