loj#6508. 「雅礼集训 2018 Day7」B

loj#6508. 「雅礼集训 2018 Day7」B

原题传送门:>Here<

我们发现有性质$(a,n)=1$,也就是说,$a\cdot i+b \mod n$的取值不会重复。

我们考虑对$S[0\cdots m-1]$建线段树,线段树下标为$a\cdot i + b\mod n$,存储的值是当前区间内$T$上对应位置为$1$的数的个数。

这样说可能有点抽象,我详细说明一下。

以样例为例:

1
2
3
9 5 6 4 3
101
...

构成的$S$的$a\cdot i+b\mod n$数组的前$m$项为

1
6 2 7

所以线段树维护的数组为

1
2
0 1 2 3 4 5 6 7 8
x x 0 x x x 1 1 x

现在我们考虑$\ge C$的限制。

仍然以样例为例:

在样例中,$C=4$。

所以对于所有$< C$的$S$值,当$T[i]=1$时会对答案产生贡献;

对于所有$\ge C$的$S$值,当$T[i]=0$时会对答案产生贡献。

我们发现这相当于查询线段树上$0\cdots C-1$中$1$的个数,以及$C\cdots n-1$中$0$的个数。

这样我们也可以实现单点修改。


我们现在再考虑查询位置的问题。

假设查询的位置从$x$开始,则每个点的值需要加上$a\cdot x$。

还是以样例为例:

1
2
0 1 2 3 4 5 6 7 8
x x 0 x x x 1 1 x

当我们要查询从$1$开始的匹配时,每个点的值需要加上$a$。

这样序列就变成

1
2
5 6 7 8 0 1 2 3 4
x x 0 x x x 1 1 x

也就是说,我们查询到线段树上的一个节点$[l,r]$时,实际查询的权值区间是$[l_0,r_0]$,其中$l_0=(l+a\cdot x)\mod n,r_0=(r+a\cdot x)\mod n$。

我们发现区间内的数“极性”相等(亦即所有数都$<C$或$\ge C$)需要满足两个条件:

  • $l_0<r_0$,也就是没有上例中$3\cdots 6$这样跨越边界的情况;
  • $l_0<C \space and \space r_0\ge C$,也就是区间没有被$C$“劈开”。

如果“极性”相等,则区间的贡献可以直接计算;否则就递归下去。

我们发现这个操作相当于查询$4$个区间的贡献,即

  • 加上权值以后比原来权值大,但是仍然$<C​$的区间;
  • 加上权值以后比原来权值大,且$\ge C​$的区间;
  • 加上权值以后比原来权值小,且$<C​$的区间;
  • 加上权值以后比原来权值小,且$\ge C$的区间;

所以复杂度是没有问题的。

代码:

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
#include <cstdio>
#include <algorithm>

int orig[100001],val[100001],n,m,a,b,c,q,opt,x,T[100001],se[500001];
char tem[100001];
void insert(int root,int l,int r,int e,int x){
if(!x)return;
se[root]+=x;
if(l==r)return;
if((l+r)>>1>=e)insert(root<<1,l,(l+r)>>1,e,x);
else insert(root<<1|1,((l+r)>>1)+1,r,e,x);
}
int query(int root,int l,int r,int w){
int x=(orig[l]+w)%n,y=(orig[r]+w)%n;
if(x<=y || l==r){
if(y<c)return se[root];
else if(x>=c)return (r-l+1)-se[root];
}
return query(root<<1,l,(l+r)>>1,w)+query(root<<1|1,((l+r)>>1)+1,r,w);
}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
void write(int x){
if(x>9)write(x/10);
putchar((x%10)+'0');
}
signed main(){
n=read(),a=read(),b=read(),c=read(),m=read();
orig[1]=val[1]=b%n;
for(int i=1;i<m;++i)val[i+1]=orig[i+1]=(val[i]+a)%n;
std::sort(orig+1,orig+m+1);
for(int i=1;i<=m;++i)val[i]=std::lower_bound(orig+1,orig+m+1,val[i])-orig;
scanf("%s",tem+1);
for(int i=1;i<=m;++i)T[i]=tem[i]-'0',insert(1,1,m,val[i],T[i]);
q=read();
for(int i=1;i<=q;++i){
opt=read(),x=read();
if(opt==1)write(query(1,1,m,(long long)x*a%n)),putchar('\n');
else insert(1,1,m,val[x+1],(T[x+1]?-1:1)),T[x+1]^=1;
}
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×