莫队总是莫名T飞
查看原帖
莫队总是莫名T飞
483252
罗小菜楼主2022/6/3 18:56

求求了,我的莫队总是在写某些奇怪的题目的时候T掉,都好几次了,有没有大佬帮我看看那个地方出问题了,会T掉

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=2e5+10;
struct node
{
	int l,r,id;
}qry[MAXN];
struct node2
{
	int p,x;
	inline bool operator < (const node2 &temp) const
	{
		return x<temp.x;
	}
}dc[MAXN];
int res[MAXN],sum;
int l,r;
int used[MAXN];
int len,bl[MAXN];
int n,q;
int ans[MAXN];
int rk[MAXN],cnt;
inline bool cmp(node a,node b)
{
	if(bl[a.l]==bl[b.l]) return a.r<b.r;
	return a.l<b.l;
}
inline void Del(int x)
{
	if(used[x]==sum && res[sum]==1) sum--;
	res[used[x]]--;
	used[x]--;
	res[used[x]]++;
	return ;
}
inline void Add(int x)
{
	if(used[x]==sum) sum++;
	res[used[x]]--;
	used[x]++;
	res[used[x]]++;
	return ;
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
	    int x;
	    cin>>x;
		dc[i].x=x;
		dc[i].p=i;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>qry[i].l>>qry[i].r;
		qry[i].id=i;
	}
	sort(qry+1,qry+1+q,cmp);
	sort(dc+1,dc+1+n);
	for(int i=1;i<=n;i++)
	{
		if(dc[i].x!=dc[i-1].x) cnt++;
		rk[dc[i].p]=cnt;
	}
	l=1,r=0,sum=0;
	for(int i=1;i<=q;i++)
	{
		while(l<qry[i].l) Del(rk[l++]);
		while(l>qry[i].l) Add(rk[--l]);
		while(r<qry[i].r) Add(rk[++r]);
		while(r>qry[i].r) Del(rk[r--]);
		ans[qry[i].id]=sum;
	}
	for(int i=1;i<=q;i++) cout<<-ans[i]<<"\n";
	return 0;
}
2022/6/3 18:56
加载中...