重发一遍代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,k;
long long w[1000000+1],cnt[1000000+1],dd[1000000+1],num[1000000+1];
struct roro
{
int l;
int r;
int pos;
int id;
}a[1000000+1];
bool cmp(roro k1,roro k2)
{
if(k1.pos==k2.pos)
{
return k1.r<k2.r;
}
else
{
return k1.pos<k2.pos;
}
}
int main()
{
scanf("%d%d",&n,&m);
int size=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].pos=(a[i].l-1)/size+1;
a[i].id=i;
}
sort(a+1,a+m+1,cmp);
int hh=100;
int l1=1;
int r1=0;
long long ans=0;
int id1=0;
int id2=0;
num[0]=n;
for(int i=1;i<=m;i++)
{
while(a[i].l<l1)
{
l1--;
if(cnt[w[l1]]==ans)
{
ans++;
}
num[cnt[w[l1]]+hh]--;
cnt[w[l1]]++;
num[cnt[w[l1]]+hh]++;
}
while(a[i].r>r1)
{
r1++;
if(cnt[w[r1]]==ans)
{
ans++;
}
num[cnt[w[r1]]+hh]--;
cnt[w[r1]]++;
num[cnt[w[r1]]+hh]++;
}
while(a[i].l>l1)
{
if(cnt[w[l1]]==ans and num[cnt[w[l1]]+hh]==1)
{
ans--;
}
num[cnt[w[l1]]+hh]--;
cnt[w[l1]]--;
num[cnt[w[l1]]+hh]++;
l1++;
}
while(a[i].r<r1)
{
if(cnt[w[r1]]==ans and num[cnt[w[r1]+hh]]==1)
{
ans--;
}
num[cnt[w[r1]]+hh]--;
cnt[w[r1]]--;
num[cnt[w[r1]]+hh]++;
r1--;
}
dd[a[i].id]=-ans;
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",dd[i]);
}
return 0;
}
by 吉良吉影 @ 2018-02-01 12:04:48
再重发一遍
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,k;
long long w[1000000+1],cnt[1000000+1],dd[1000000+1],num[1000000+1];
struct roro
{
int l;
int r;
int pos;
int id;
}a[1000000+1];
bool cmp(roro k1,roro k2)
{
if(k1.pos==k2.pos)
{
return k1.r<k2.r;
}
else
{
return k1.pos<k2.pos;
}
}
int main()
{
scanf("%d%d",&n,&m);
int size=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].pos=(a[i].l-1)/size+1;
a[i].id=i;
}
sort(a+1,a+m+1,cmp);
int hh=100;
int l1=1;
int r1=0;
long long ans=0;
int id1=0;
int id2=0;
num[0]=n;
for(int i=1;i<=m;i++)
{
while(a[i].l<l1)
{
l1--;
if(cnt[w[l1]]==ans)
{
ans++;
}
num[cnt[w[l1]]+hh]--;
cnt[w[l1]]++;
num[cnt[w[l1]]+hh]++;
}
while(a[i].r>r1)
{
r1++;
if(cnt[w[r1]]==ans)
{
ans++;
}
num[cnt[w[r1]]+hh]--;
cnt[w[r1]]++;
num[cnt[w[r1]]+hh]++;
}
while(a[i].l>l1)
{
if(cnt[w[l1]]==ans and num[cnt[w[l1]]+hh]==1)
{
ans--;
}
num[cnt[w[l1]]+hh]--;
cnt[w[l1]]--;
num[cnt[w[l1]]+hh]++;
l1++;
}
while(a[i].r<r1)
{
if(cnt[w[r1]]==ans and num[cnt[w[r1]+hh]]==1)
{
ans--;
}
num[cnt[w[r1]]+hh]--;
cnt[w[r1]]--;
num[cnt[w[r1]]+hh]++;
r1--;
}
dd[a[i].id]=-ans;
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",dd[i]);
}
return 0;
}
```
by 吉良吉影 @ 2018-02-01 12:05:50
。。。。。。。。。。。。。我绝望了
by 吉良吉影 @ 2018-02-01 12:06:23
```
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,k;
long long w[1000000+1],cnt[1000000+1],dd[1000000+1],num[1000000+1];
struct roro
{
int l;
int r;
int pos;
int id;
}a[1000000+1];
bool cmp(roro k1,roro k2)
{
if(k1.pos==k2.pos)
{
return k1.r<k2.r;
}
else
{
return k1.pos<k2.pos;
}
}
int main()
{
scanf("%d%d",&n,&m);
int size=(int)sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].pos=(a[i].l-1)/size+1;
a[i].id=i;
}
sort(a+1,a+m+1,cmp);
int hh=100;
int l1=1;
int r1=0;
long long ans=0;
int id1=0;
int id2=0;
num[0]=n;
for(int i=1;i<=m;i++)
{
while(a[i].l<l1)
{
l1--;
if(cnt[w[l1]]==ans)
{
ans++;
}
num[cnt[w[l1]]+hh]--;
cnt[w[l1]]++;
num[cnt[w[l1]]+hh]++;
}
while(a[i].r>r1)
{
r1++;
if(cnt[w[r1]]==ans)
{
ans++;
}
num[cnt[w[r1]]+hh]--;
cnt[w[r1]]++;
num[cnt[w[r1]]+hh]++;
}
while(a[i].l>l1)
{
if(cnt[w[l1]]==ans and num[cnt[w[l1]]+hh]==1)
{
ans--;
}
num[cnt[w[l1]]+hh]--;
cnt[w[l1]]--;
num[cnt[w[l1]]+hh]++;
l1++;
}
while(a[i].r<r1)
{
if(cnt[w[r1]]==ans and num[cnt[w[r1]+hh]]==1)
{
ans--;
}
num[cnt[w[r1]]+hh]--;
cnt[w[r1]]--;
num[cnt[w[r1]]+hh]++;
r1--;
}
dd[a[i].id]=-ans;
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",dd[i]);
}
return 0;
}
```
by 吉良吉影 @ 2018-02-01 12:06:55
终于发成功了,话说前面的代码不能删掉吗?
总之就是求大佬帮我找出RE的原因,感激不尽
by 吉良吉影 @ 2018-02-01 12:08:07
同蜜汁RE
by Misaka_Azusa @ 2018-04-18 18:47:36