抽象莫队卡常,求解答
查看原帖
抽象莫队卡常,求解答
401660
Piqllmxiu楼主2025/1/20 19:28

代码一能过 , 代码二过不了

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

inline int read()
{
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch))ch = getchar();
	while(isdigit(ch))
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}

inline void write(int x)
{
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
}

int n , m;

struct Ques{
	int L , R , k;
}q[MAXN];

int al[MAXN];

int pos[MAXN] , block;

int ans[MAXN];

int cnt[MAXN];
int s;
int from[MAXN], ls = 0;
inline bool cmp(Ques a , Ques b)
{
	if(pos[a.L] != pos[b.L])
	{
		return pos[a.L] < pos[b.L];	
	}
	if(pos[a.L] & 1)return a.R > b.R;
	return a.R < b.R;
}

int main()
{
	n = read();
	block = sqrt(n);
	for(register int i = 1;i <= n;i++)
	{
		al[i] = read();
		if(from[al[i]]) al[i] = from[al[i]];
		else {
			from[al[i]] = ++ls;
			al[i] = ls;
		}
		pos[i] = (i - 1) / block + 1;
	}
	m = read();
	for(register int i = 1;i <= m;i++)
	{
		q[i].L = read();
		q[i].R = read();
		q[i].k = i;
	}
	
	sort(q + 1 , q + 1 + m , cmp);
	int l = 1 , r = 0 , s = 0;
	for(register int i = 1;i <= m;i++)
	{
		while(l < q[i].L)
		{
			cnt[al[l]]--;
			if(!cnt[al[l]])s--;
			l++;
		}
		while(l > q[i].L)
		{
			l--;
			cnt[al[l]]++;
			if(cnt[al[l]] == 1)s++;
		}
		while(r < q[i].R)
		{
			r++;
			cnt[al[r]]++;
			if(cnt[al[r]] == 1)s++;	 
		}
		while(r > q[i].R)
		{
			cnt[al[r]]--;
			if(!cnt[al[r]])s--;
			r--;
		}
		ans[q[i].k] = s;
	}
	
	for(register int i = 1;i <= m;i++)
	{
		write(ans[i]);
		printf("\n");
	}
	
	return 0;
}
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

inline int read()
{
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch))ch = getchar();
	while(isdigit(ch))
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}

inline void write(int x)
{
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
}

int n , m;

struct Ques{
	int L , R , k;
}q[MAXN];

int al[MAXN];

int pos[MAXN] , block;

int ans[MAXN];

int cnt[MAXN];

int s;
int from[MAXN], ls = 0;
inline bool cmp(Ques a , Ques b)
{
	if(pos[a.L] != pos[b.L])
	{
		return pos[a.L] < pos[b.L];	
	}
	if(pos[a.L] & 1)return a.R > b.R;
	return a.R < b.R;
}

int main()
{
	n = read();
	block = sqrt(n);
	for(register int i = 1;i <= n;i++)
	{
		al[i] = read();
		if(from[al[i]]) al[i] = from[al[i]];
		else {
			from[al[i]] = ++ls;
			al[i] = ls;
		}
		pos[i] = (i - 1) / block + 1;
	}
	m = read();
	for(register int i = 1;i <= m;i++)
	{
		q[i].L = read();
		q[i].R = read();
		q[i].k = i;
	}
	
	sort(q + 1 , q + 1 + m , cmp);
	register int l = 1 , r = 0;
	for(register int i = 1;i <= m;i++)
	{
		while(l < q[i].L)
		{
			cnt[al[l]]--;
			if(!cnt[al[l]])s--;
			l++;
		}
		while(l > q[i].L)
		{
			l--;
			cnt[al[l]]++;
			if(cnt[al[l]] == 1)s++;
		}
		while(r < q[i].R)
		{
			r++;
			cnt[al[r]]++;
			if(cnt[al[r]] == 1)s++;	 
		}
		while(r > q[i].R)
		{
			cnt[al[r]]--;
			if(!cnt[al[r]])s--;
			r--;
		}
		ans[q[i].k] = s;
	}
	
	for(register int i = 1;i <= m;i++)
	{
		write(ans[i]);
		putchar('\n');
	}
	
	return 0;
}

求大佬解答%%%

2025/1/20 19:28
加载中...