一Iris一 @ 2021-06-27 18:31:56
求区间众数
本地能过第一个测试点，对拍也没问题，IDE也能正常输出，交上去全是too short on line 1
请问为什么这样
```cpp
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define INF 1ll<<30
#define Int unsigned long long
template<typename _T>
inline void read(_T &x)
{
x=0;char s=getchar();int f=1;
while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=f;
}
const int np = 4e4 + 5;
const int block = 200 + 5;
#define lowbit(x) (x&(-x))
#define gb(x) ((x-1)/T + 1)
#define gl(x) ((x-1)*T + 1)
#define pb push_back
int h[np];
int H[np];
int n,m,b[np];
int tree[np],Ans,T;
int a[np];
vector<int> vec[np];
int mor[block][block],la;
int bac[np];
inline void Init()
{
memcpy(b + 1,a + 1,sizeof(a));
sort(b + 1,b + 1 + n);
int *be = b +1 , *en = unique(b +1 ,b + 1 + n);
for(int i=1;i<=n;i++)
{
a[i] = lower_bound(be,en,a[i])-b;
}
}
inline void solve(int x,int y)
{
if(gb(x) == gb(y))
{
int g =0 ;
for(int i=x;i<=y;i++)
{
bac[a[i]]++;
if(bac[a[i]] >= bac[g])
{
g = bac[a[i]] == bac[g]?min(a[i],g):a[i];
}
}
printf("%d\n",la = b[g]);
for(int i=x;i<=y;i++)bac[a[i]]--;
return ;
}
int g = mor[gb(x) + 1][gb(y) - 1];
int Ans = 0;
if(g)
{
int n1 = upper_bound(vec[g].begin(),vec[g].end(),x-1) - vec[g].begin();
int n2 = upper_bound(vec[g].begin(),vec[g].end(),y) - vec[g].begin();
Ans = n2 - n1;
}
for(int i = x;i < gl(gb(x) + 1);i++)
{
int g_= a[i];
int n1 = upper_bound(vec[g_].begin(),vec[g_].end(),x-1) - vec[g_].begin();
int n2 = upper_bound(vec[g_].begin(),vec[g_].end(),y) - vec[g_].begin();
if(n2 - n1 >= Ans)
{
if(n2-n1 == Ans) g = min(g,g_);
else g = g_,Ans = n2 - n1;
}
}
for(int i=gl(gb(y));i<=y;i++)
{
int g_= a[i];
int n1 = upper_bound(vec[g_].begin(),vec[g_].end(),x-1) - vec[g_].begin();
int n2 = upper_bound(vec[g_].begin(),vec[g_].end(),y) - vec[g_].begin();
if(n2 - n1 >= Ans)
{
if(n2-n1 == Ans) g = min(g,g_);
else g = g_,Ans = n2 - n1;
}
}
printf("%d\n",la = b[g]);
return;
}
signed main()
{
// freopen("ao.in","r",stdin);
// freopen("a.out","w",stdout);
read(n);read(m);
for(int i=1;i<=n;i++)
read(a[i]);
Init();
T = sqrt(n);
for(int i=1;i<=n;i++) vec[a[i]].pb(i);//[]++;
for(int i=1;i<=gb(n);i++)
{
for(int j=i;j<=gb(n);j++)
{
int opt = mor[i][j - 1];
for(int x = gl(j);x < gl(j + 1) &&x <= n;x++)
{
bac[a[x]]++;
if(bac[a[x]] >= bac[opt])
{
opt = bac[a[x]]==bac[opt]?min(opt,a[x]):a[x];
}
}
mor[i][j] = opt;
}
memset(bac,0,sizeof(bac));
}
// cout<<mor[1][1]<<'\n';
memset(bac,0,sizeof(bac));
for(int i=1,l,r,l_,r_;i<=m;i++)
{
read(l);
l_ = (l + la - 1)%n + 1;
read(r);
r_ = (r + la - 1)%n + 1;
if(l_ > r_) swap(l_,r_);
solve(l_,r_);
}
return 0;
}
```
by 一Iris一 @ 2021-06-27 19:26:16
额，离散化的时候
memcpy(b + 1,a + 1,sizeof(a))
这么写是错的，会访问越界修改多余的一个变量，然后就非常巧合，这个变量是m，然后m就被修改为0，然后挂掉了