BZOJ

BZOJ 2821

传送门

这道题用到了类似区间众数的方法，所以先贴个资料 区间众数解题报告 –WJMZBMR

首先，用暴力的循环和一个统计数组可以算出某区间$[l,r]$中多少个数出现偶数次吧…

然后将数列分块，暴力处理出$f_{i,j}$表示从第$i$块到第$j$块多少个数出现偶数次

对于询问$[l,r]$，只需要统计区间两边不满一块的对已经处理出来的整块答案的影响

  • 若两边偶数次 整块奇数次或没出现 答案++
  • 若两边奇数次 整块偶数次 答案–

现在的问题是如何统计区间中一个数的出现次数

这个也很好解决，将所有数按数值为第一关键字，位置为第二关键字排序，然后直接在每个数的区间里二分查找$l$之后的位置和$r$之前的位置，两个位置相减就是$[l,r]$中的出现次数


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
program bzoj_2821;
type rec=record p,x:longint; end;
var f:array[1..1500,1..1500]of longint;
    a,ll,rr,cnt,st,ed:array[1..100000]of longint;
    b:array[1..100000]of rec;
    mk:array[1..100000]of boolean;
    n,m,c,i,ans,size,block,l,r,log:longint;

procedure swap(var a,b:longint);
var p:longint;
begin
  p:=a;
  a:=b;
  b:=p;
end;

function find(p,x:longint;flag:boolean):longint;
var l,r,mid:longint;
begin
  if flag then find:=0 else find:=n+1;
  l:=st[x];
  r:=ed[x];
  while l<=r do
  begin
    mid:=(l+r)>>1;
    if p=b[mid].p then
    begin
      find:=mid;
      if not flag then r:=mid-1 else l:=mid+1;
    end;
    if p<b[mid].p then
    begin
      if not flag then find:=mid;
      r:=mid-1;
    end;
    if p>b[mid].p then
    begin
      if flag then find:=mid;
      l:=mid+1;
    end;
  end;
end;

function count(l,r,x:longint):longint;
begin
  count:=find(r,x,true)-find(l,x,false)+1;
  if count<0 then exit(0);
end;

procedure qsort(l,r:longint);
var i,j:longint;
    mid:rec;
begin
  i:=l;
  j:=r;
  mid:=b[(l+r)>>1];
  repeat
    while (b[i].x<mid.x)or((b[i].x=mid.x)and(b[i].p<mid.p)) do inc(i);
    while (b[j].x>mid.x)or((b[j].x=mid.x)and(b[j].p>mid.p)) do dec(j);
    if i<=j then
    begin
      swap(b[i].p,b[j].p);
      swap(b[i].x,b[j].x);
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;

procedure init;
var i,j,k,tot:longint;
begin
  for i:=1 to block do
  begin
    for j:=ll[i] to n do cnt[a[j]]:=0;
    tot:=0;
    for j:=i to block do
    begin
      for k:=ll[j] to rr[j] do
      begin
        if (cnt[a[k]] and 1=0)and(cnt[a[k]]<>0) then dec(tot);
        if cnt[a[k]] and 1=1 then inc(tot);
        inc(cnt[a[k]]);
      end;
      f[i,j]:=tot;
    end;
  end;
  for i:=1 to n do
  begin
    b[i].x:=a[i];
    b[i].p:=i;
  end;
  qsort(1,n);
  i:=1;
  while i<=n do
  begin
    st[b[i].x]:=i;
    while (i<n)and(b[i+1].x=b[i].x) do inc(i);
    ed[b[i].x]:=i;
    inc(i);
  end;
end;

function solve(x,y:longint):longint;
var i,l,r,c1,c2,ans:longint;
begin
  if x>y then swap(x,y);
  ans:=0;
  l:=(x-1)div size+1;
  r:=(y-1)div size+1;
  if l+1>=r then
  begin
    for i:=x to y do
    if (not mk[a[i]])and(count(x,y,a[i]) and 1=0) then
    begin
      mk[a[i]]:=true;
      inc(ans);
    end;
    for i:=x to y do mk[a[i]]:=false;
  end else
  begin
    inc(l);
    dec(r);
    ans:=f[l,r];
    for i:=x to ll[l]-1 do if not mk[a[i]] then
    begin
      c1:=count(x,y,a[i]);
      c2:=count(ll[l],rr[r],a[i]);
      if (c1 and 1=0)and(c2 and 1=1) then inc(ans);
      if (c1 and 1=0)and(c1<>0)and(c2=0) then inc(ans);
      if (c1 and 1=1)and(c2 and 1=0)and(c2<>0) then dec(ans);
      mk[a[i]]:=true;
    end;
    for i:=rr[r]+1 to y do if not mk[a[i]] then
    begin
      c1:=count(x,y,a[i]);
      c2:=count(ll[l],rr[r],a[i]);
      if (c1 and 1=0)and(c2 and 1=1) then inc(ans);
      if (c1 and 1=0)and(c1<>0)and(c2=0) then inc(ans);
      if (c1 and 1=1)and(c2 and 1=0)and(c2<>0) then dec(ans);
      mk[a[i]]:=true;
    end;
    for i:=x to ll[l]-1 do mk[a[i]]:=false;
    for i:=rr[r]+1 to y do mk[a[i]]:=false;
  end;
  exit(ans);
end;

begin
  readln(n,c,m);
  log:=0;
  while 1<<log<=n do inc(log);
  size:=trunc(sqrt(n/log));
  block:=n div size+ord(n mod size<>0);
  for i:=1 to block do
  begin
    ll[i]:=(i-1)*size+1;
    rr[i]:=i*size;
  end;
  rr[block]:=n;
  for i:=1 to n do read(a[i]);
  init;
  ans:=0;
  for i:=1 to m do
  begin
    readln(l,r);
    ans:=solve((l+ans)mod n+1,(r+ans)mod n+1);
    writeln(ans);
  end;
end.