反正Orz就对了
by 花里心爱 @ 2019-03-20 18:15:08
@[Irressey](/space/show?uid=79017) 您咋每次都是这句话啊
by LJC00753 @ 2019-03-20 18:17:34
还有谁能帮我证明一下莫队 的 时间复杂度
by LJC00753 @ 2019-03-20 18:17:55
@[凰铃音](/space/show?uid=88256) 莫队时间复杂度不是$n\sqrt{n}$吗qwq
by 花里心爱 @ 2019-03-20 18:19:29
@[Irressey](/space/show?uid=79017) 这题的莫队啊
by LJC00753 @ 2019-03-20 18:19:39
@[凰铃音](/space/show?uid=88256) 窝没做这题qwq
by 花里心爱 @ 2019-03-20 18:20:11
@[Irressey](/space/show?uid=79017) 就是这题用莫队
“说说思路吧,我们用一个mn作为每次转移的答案,add操作就从mn开始找到第一个没有出现的数,del操作,如果减的那个数a[x]等于0,mn=Min(mn,a[x]).”
这种操作每次不是最多是O(n)吗
还有 nsqrt(n)种操作
怎么均摊分析啊
by LJC00753 @ 2019-03-20 18:22:22
@[凰铃音](/space/show?uid=88256)
帮你改过了
```cpp
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200025
int c[MAXN],a[MAXN];
int n,m,ans,nn;
struct wen
{
int l,r,i;
}w[MAXN];
int an[MAXN];
bool cmp(wen a,wen b)
{
return a.l / nn < b.l / nn || a.l / nn == b.l / nn && a.r < b.r;
}
void rd()
{
scanf("%d%d",&n,&m);
nn = sqrt(n);
for(int i = 1; i <= n; i ++){
scanf("%d",&c[i]);
if(c[i] > n+2) c[i] = n+2;
}
for(int i = 1; i <= m; i ++)
{
scanf("%d%d",&w[i].l,&w[i].r);
w[i].i = i;
}
sort(w+1,w+m+1,cmp);
}
void jia(int x)
{
a[c[x]] ++;
if(a[c[x]] == 1) {
if(c[x] == ans)
while(a[ans] != 0) ans ++;
}
}
void jian(int x) {
a[c[x]] --;
if(a[c[x]] == 0) {
if(c[x] < ans) ans = c[x];
}
}
int l,r;
int main()
{
rd();
l = 1,r = 0;
for(int i = 1; i <= n; i ++)
{
while(r < w[i].r) {
r ++;
jia(r);
}
while(l > w[i].l)
{
l --;
jia(l);
}
while(r > w[i].r) {
jian(r);
r --;
}
while(l < w[i].l)
{
jian(l);
l ++;
}
an[w[i].i] = ans;
}
for(int i = 1; i <= m; i ++)
cout<<an[i]<<"\n";
return 0;
}
```
by Smile_Cindy @ 2019-03-20 18:26:06
@[Alpha](/space/show?uid=87058) 块大小sqrt(n) 就过了？？
这么玄学？
我记得块略大于sqrt(n) 更快呀
by LJC00753 @ 2019-03-20 18:58:56