求助,莫队,玄关
查看原帖
求助,莫队,玄关
981551
DGFLSzfd楼主2024/7/23 22:51

题目在这!!!

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5+10;;
int n,m;

int block_size,pos[N];

int v[N];

struct Q
{
	int l,r,k;
}question[M];

int ans[M],res=0;

map<int,int> cnt;

//priority_queue<pair<int,pair<int,int> > >que;

int book[N];
void Add(int x,bool y)
{
	book[cnt[v[x]]]--;
	cnt[v[x]]++;
	book[cnt[v[x]]]++;
	res=max(res,cnt[v[x]]);
}
void Sub(int x,bool y)
{
	book[cnt[v[x]]]--;
	if(book[cnt[v[x]]]==0 and cnt[v[x]]==res)res--;
	cnt[v[x]]--;
	book[cnt[v[x]]]++;
}

int main()
{
	
	while(cin>>n)
	{
		if(n==0)break;cin>>m;
		block_size=sqrt(n);
		cnt.clear();
		memset(book,0,sizeof(book));
		for(int i=1;i<=n;i++)
		{
			cin>>v[i];pos[i]=i/block_size;
		}
		
		for(int i=0;i<m;i++)
		{
			cin>>question[i].l>>question[i].r;
			question[i].k=i;
		}
		
		sort(question,question+m, [](Q x ,Q y) 
		{
			return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];
		});
		
		int l=1,r=0;
		for(int i=0;i<m;i++)
		{
			
			while(question[i].l<l) Add(--l,0);
			while(question[i].r>r) Add(++r,1);
			while(question[i].l>l) Sub(l++,0);
			while(question[i].r<r) Sub(r--,1);
			
			
			ans[question[i].k]=res;
		}
		for(int i=0;i<m;i++)
			cout<<ans[i]<<endl;
		}
	return 0;
}

我真的崩溃了,再也不想做外国oj的题了,还没有数据给我我测试。
我用的是莫队,请大佬调教我的代码(哭哭哭)

2024/7/23 22:51
加载中...