bzoj3339 Rmq Problem

　　直接跑了莫队勉强跑过，正解应该是一开始算出所有区间[1,i]的sg值，然后考虑从区间[1,i]到区间[2,i]的sg值变换，发现只有区间[2,next[a[1]]-1]内，sg值大于a[1]的数字sg值全部变成a[1]，这里next[a[1]]表示下一个与a[1]相同的数字的位置。用线段树维护一下即可。

莫队代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define N 500010
 4 using namespace std;
 5 int n,m,i,a[N],ans[N],sum[N],L,R,s[N];
 6 struct g{
 7     int l,r,id;
 8 }b[N];
 9 bool cmp(g a,g b)
10 {
11     if (a.l/400==b.l/400)
12     return a.r<b.r;
13     return a.l/400<b.l/400;
14 }
15 void cc(int x,int w)
16 {
17     if ((s[a[x]]==0)&&(w>1)) sum[a[x]/400]++;
18     if ((s[a[x]]==1)&&(w<-1)) sum[a[x]/400]--;
19     s[a[x]]+=w;
20 }
21 int query()
22 {
23     int i;
24     for (i=0;;i++)
25     if (sum[i]==400) continue;else break;
26     int j;
27     for (j=400*i;;j++)
28     if (s[j]) continue;else break;
29     return j;
30 }
31 int main()
32 {
33     scanf("%d%d",&n,&m);
34     for (i=1;i<=n;i++)
35         scanf("%d",&a[i]);
36     for (i=1;i<=m;i++)
37     {
38         scanf("%d%d",&b[i].l,&b[i].r);
39         b[i].id=i;
40     }
41     sort(b+1,b+1+m,cmp);
42     L=1;R=0;
43     for (i=1;i<=m;i++)
44     {
45         
46         while (R<b[i].r) R++,cc(R,1);
47         while (R>b[i].r) cc(R,-1),R--;
48         while (L<b[i].l) cc(L,-1),L++;
49         while (L>b[i].l) L--,cc(L,1);
50         ans[b[i].id]=query();
51     }
52     for (i=1;i<=m;i++)
53     printf("%d
",ans[i]);
54 }