bzoj2821 作诗

bzoj 2821

如果模仿一般区间众数比较卡的做法,可以直接对每个数记录出现的位置,然后预处理块i到块j的答案,询问的时候以整块的答案为基础,对于零散的点,二分一下区间内的出现次数,查看是否实际上不是答案/在整块内没有被计入答案。这样的复杂度是$O(n\sqrt{n}logn)$的,不能通过。

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
const int maxn=(int)1e5+5;
int a[maxn],n,st[maxn],up,sz,N,B,m,c,vis[maxn],ans[400+5][400+5];
struct info {
int l,r;
info(int l=0,int r=0): l(l),r(r) {}
};
info b[400+5];
vector<int > pos[maxn];
int id(int po) {return (po-1)/B+1;}
int appr(int l,int r,int v)
{
return upper_bound(pos[v].begin(),pos[v].end(),r)-lower_bound(pos[v].begin(),pos[v].end(),l);
}
int Qry(int l,int r)
{
int lb=(l-1)/B+1,rb=r/B;
if(l%B!=1) lb++;
int ret=ans[lb][rb];
if(lb>rb) {
for(int i=l;i<=r;i++) {
if(!vis[a[i]] && appr(l,r,a[i])%2==0) ret++;
vis[a[i]]=true;
}
for(int i=l;i<=r;i++) vis[a[i]]=0;
}else {
int L=(lb-1)*B+1,R=rb*B,tmp,tmp1;
for(int i=l;i<=(lb-1)*B;i++) {
if(!vis[a[i]]){
tmp=appr(L,R,a[i]),tmp1=appr(l,r,a[i]);
if(tmp1%2==0 && (tmp==0 || tmp%2!=0)) ret++;
if(tmp1%2==1 && (tmp>0 && tmp%2==0)) ret--;
vis[a[i]]=true;
}
}
for(int i=rb*B+1;i<=r;i++) {
if(!vis[a[i]]){
tmp=appr(L,R,a[i]),tmp1=appr(l,r,a[i]);
if(tmp1%2==0 && (tmp==0 || tmp%2!=0)) ret++;
if(tmp1%2==1 && (tmp>0 && tmp%2==0)) ret--;
vis[a[i]]=true;
}
}
for(int i=l;i<=(lb-1)*B;i++) vis[a[i]]=0;
for(int i=rb*B+1;i<=r;i++) vis[a[i]]=0;
}
return ret;
}
int main()
{
n=readInt(),c=readInt(),m=readInt();
for(int i=1;i<=n;i++) a[i]=readInt(),pos[a[i]].push_back(i);
B=(int)sqrt(n);
for(int i=1;i<=n;i+=B) b[++N].l=i,b[N].r=min(n,i+B-1);
int Ans=0;
for(int i=1;i<=N;i++) {
memset(vis,0,sizeof(vis)); Ans=0;
for(int j=b[i].l;j<=n;j++) {
if(vis[a[j]]>0 && vis[a[j]]%2==0) Ans--;
vis[a[j]]++;
if(vis[a[j]]>0 && vis[a[j]]%2==0) Ans++;
if(j%B==0 || j==n) ans[i][id(j)]=Ans;
}
}
memset(vis,0,sizeof(vis));
int l=0,r=0,pre=0;
for(int z=0;z<m;z++) {
l=readInt(),r=readInt();
l=(l+pre)%n+1,r=(r+pre)%n+1;
if(l>r) swap(l,r);
writeInt(pre=Qry(l,r)),putchar('\n');
}
return 0;
}

然后就要考虑去掉这个$log$了…既然对于块外零散的点肯定是要扫一遍的,那么为了得到这些点在整个区间内的出现次数,那肯定需要这些数在整块内的出现次数,所以可以直接预处理一个到这一块为止包括这一块,一个数出现的次数,可以通过处理出每一块了以后再前缀和来实现(空间上要卡一卡,是$n\sqrt{n}$的)。然后同样查看是否实际上不是答案/在整块内没有被计入答案,同时更新答案。这样的话是$O(n\sqrt{n})$的。

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
#include <bits/stdc++.h>
using namespace std;
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
void writeInt(int x)
{
if(x==0) {putchar('0');return;}
if(x<0) {x=-x;putchar('-');}
static char s[21];int idx=0;
while(x) s[++idx]=x%10+'0',x/=10;
while(idx) putchar(s[idx--]);
}
const int maxn=(int)1e5+5;
int a[maxn],n,N,B,m,c,vis[maxn],ans[318][318],sum[318][maxn];
int id(int po) {return (po-1)/B+1;}
bool ok(int x) {return (x>0 && x%2==0);}
int Qry(int l,int r)
{
int lb=(l-1)/B+1,rb=r/B;
if(l%B!=1) lb++;
int ret=ans[lb][rb];
if(lb>rb) {
for(int i=l;i<=r;i++) {
if(vis[a[i]]>0 && vis[a[i]]%2==0) ret--;
vis[a[i]]++;
if(vis[a[i]]>0 && vis[a[i]]%2==0) ret++;
}
for(int i=l;i<=r;i++) vis[a[i]]=0;
}else {
for(int i=l;i<=(lb-1)*B;i++) {
if(!vis[a[i]]) vis[a[i]]+=sum[rb][a[i]]-sum[lb-1][a[i]];
vis[a[i]]++;
}
for(int i=rb*B+1;i<=r;i++) {
if(!vis[a[i]]) vis[a[i]]+=sum[rb][a[i]]-sum[lb-1][a[i]];
vis[a[i]]++;
}
for(int i=l;i<=(lb-1)*B;i++) {
if(vis[a[i]]==0) continue;
if(ok(vis[a[i]]) && !ok(sum[rb][a[i]]-sum[lb-1][a[i]])) ret++;
if(!ok(vis[a[i]]) && ok(sum[rb][a[i]]-sum[lb-1][a[i]])) ret--;
vis[a[i]]=0;
}
for(int i=rb*B+1;i<=r;i++) {
if(vis[a[i]]==0) continue;
if(ok(vis[a[i]]) && !ok(sum[rb][a[i]]-sum[lb-1][a[i]])) ret++;
if(!ok(vis[a[i]]) && ok(sum[rb][a[i]]-sum[lb-1][a[i]])) ret--;
vis[a[i]]=0;
}
for(int i=l;i<=(lb-1)*B;i++) vis[a[i]]=0;
for(int i=rb*B+1;i<=r;i++) vis[a[i]]=0;
}
return ret;
}
int main()
{
n=readInt(),c=readInt(),m=readInt();
int maxx=0;
for(int i=1;i<=n;i++) a[i]=readInt(),maxx=max(maxx,a[i]);
B=(int)sqrt(n); N=(n-1)/B+1;
int Ans=0,tmp=0;
for(int i=1;i<=n;i+=B) {
tmp=(i-1)/B+1;
memset(vis,0,sizeof(vis)); Ans=0;
for(int j=i;j<=n;j++) {
if(vis[a[j]]>0 && vis[a[j]]%2==0) Ans--;
vis[a[j]]++;
if(vis[a[j]]>0 && vis[a[j]]%2==0) Ans++;
if(j%B==0 || j==n) ans[tmp][id(j)]=Ans;
}
}
for(int i=1;i<=n;i++) sum[id(i)][a[i]]++;
for(int i=1;i<=N;i++) {
for(int j=1;j<=maxx;j++) sum[i][j]+=sum[i-1][j];
}
memset(vis,0,sizeof(vis));
int l=0,r=0,pre=0;
for(int z=0;z<m;z++) {
l=readInt(),r=readInt();
l=(l+pre)%n+1,r=(r+pre)%n+1;
if(l>r) swap(l,r);
writeInt(pre=Qry(l,r)),putchar('\n');
}
return 0;
}

也可以强行根号平衡,使得复杂度较小,也就是改一下块的大小。设块大小为$x$,预处理复杂度$n^2/x$,然后总的询问复杂度为$n(xlogn+n/x)$,让$xlogn=n/x$得到$x=\sqrt{n/logn}$,然后这样的话复杂度比$n\sqrt{n}$多带一个根号下log,也就两三倍的常数了。

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
#include <bits/stdc++.h>
using namespace std;
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
void writeInt(int x)
{
if(x==0) {putchar('0');return;}
if(x<0) {x=-x;putchar('-');}
static char s[21];int idx=0;
while(x) s[++idx]=x%10+'0',x/=10;
while(idx) putchar(s[idx--]);
}
const int maxn=(int)1e5+5;
int a[maxn],n,N,B,m,c,vis[maxn],ans[2000+5][2000+5];
struct info {
int l,r;
info(int l=0,int r=0): l(l),r(r) {}
};
info b[2000+5];
vector<int > pos[maxn];
int id(int po) {return (po-1)/B+1;}
int appr(int l,int r,int v)
{
return upper_bound(pos[v].begin(),pos[v].end(),r)-lower_bound(pos[v].begin(),pos[v].end(),l);
}
int Qry(int l,int r)
{
int lb=(l-1)/B+1,rb=r/B;
if(l%B!=1) lb++;
int ret=ans[lb][rb];
if(lb>rb) {
for(int i=l;i<=r;i++) {
if(!vis[a[i]] && appr(l,r,a[i])%2==0) ret++;
vis[a[i]]=true;
}
for(int i=l;i<=r;i++) vis[a[i]]=0;
}else {
int L=(lb-1)*B+1,R=rb*B,tmp,tmp1;
for(int i=l;i<=(lb-1)*B;i++) {
if(!vis[a[i]]){
tmp=appr(L,R,a[i]),tmp1=appr(l,r,a[i]);
if(tmp1%2==0 && (tmp==0 || tmp%2!=0)) ret++;
if(tmp1%2==1 && (tmp>0 && tmp%2==0)) ret--;
vis[a[i]]=true;
}
}
for(int i=rb*B+1;i<=r;i++) {
if(!vis[a[i]]){
tmp=appr(L,R,a[i]),tmp1=appr(l,r,a[i]);
if(tmp1%2==0 && (tmp==0 || tmp%2!=0)) ret++;
if(tmp1%2==1 && (tmp>0 && tmp%2==0)) ret--;
vis[a[i]]=true;
}
}
for(int i=l;i<=(lb-1)*B;i++) vis[a[i]]=0;
for(int i=rb*B+1;i<=r;i++) vis[a[i]]=0;
}
return ret;
}
int main()
{
n=readInt(),c=readInt(),m=readInt();
for(int i=1;i<=n;i++) a[i]=readInt(),pos[a[i]].push_back(i);
B=(double)sqrt((double)n/(double)log2(n*1.0));
for(int i=1;i<=n;i+=B) b[++N].l=i,b[N].r=min(n,i+B-1);
int Ans=0;
for(int i=1;i<=N;i++) {
memset(vis,0,sizeof(vis)); Ans=0;
for(int j=b[i].l;j<=n;j++) {
if(vis[a[j]]>0 && vis[a[j]]%2==0) Ans--;
vis[a[j]]++;
if(vis[a[j]]>0 && vis[a[j]]%2==0) Ans++;
if(j%B==0 || j==n) ans[i][id(j)]=Ans;
}
}
memset(vis,0,sizeof(vis));
int l=0,r=0,pre=0;
for(int z=0;z<m;z++) {
l=readInt(),r=readInt();
l=(l+pre)%n+1,r=(r+pre)%n+1;
if(l>r) swap(l,r);
writeInt(pre=Qry(l,r)),putchar('\n');
}
return 0;
}

实际大概慢了一倍左右。