代码一能过 , 代码二过不了
#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;
}
求大佬解答%%%