bzoj4373 算术天才⑨与等差数列

Posted on |

这题挺好的…

给定一个序列，支持

  • 单点修改
  • 询问一个区间从大到小排序后是否是给定公差的等差数列

如果一个区间是一个公差是$k$的等差数列，那么这个区间会满足：

  1. 最大值和最小值之差为(区间长度-1)$\times$公差
  2. 区间内所有相邻数之间的差$gcd$为公差的倍数
  3. 当公差不为0时，区间里没有相等的数

1条件：线段树维护最大值最小值即可。

2条件：维护这个区间的所有相邻两数差的$gcd$即可。具体而言，设这个标记为$gd$，在从左右儿子$push~up$到当前结点时，考虑每个节点维护这个区间最左和最右的元素，然后相减求$gcd$再与两区间的$gd$值的$gcd$即可。

3条件：因为强制在线，所以不能对数据($\leq 10^9$)离散化，于是只能用个$map$搞下。考虑对于每种值开一个$set$，记录这个值所有的下标，记$a_i$为原序列，$pre_i$为$i$这个位置与$a_i$相等的数在前面最大的位置，$nxt_i$为$i$这个位置与$a_i$相等的数在前面最小的位置，然后我们对一个区间询问有没有相同的数，就可以看作是在$pre$和$nxt$数组上这个区间里前者取最大值，后者取最小值，若这两个值在区间中，自然就证明了这个区间里有重复数字辣。

然而原题的出题人并没有考虑到条件3，也就是说，不写条件3的两棵线段树和那两个容器的版本造的数据，所以内存限制被出题人卡到$128MB$，我可能写的丑在bzoj被卡了内存，不过没写条件3的还是可以顺利地过的。写了条件3的版本本地写了个脚本也测$ac$了。不过应该是我写丑的原因，每棵线段树如果能写优到两倍点空间的话这题还是可以在$128MB$内过的。

条件1~2

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <climits>
#include <cassert>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
template<typename T> T readin(T &rd)
{
    char c;T tmp=0,x=1;c=getchar();
    while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
    while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
    return rd=tmp*x;
}
template<typename T> void writeout(T ot)
{
    if(ot==0) {putchar('0');return;}
    if(ot<0) {putchar('-');ot*=-1;}
    static char s[21];int idx=0;
    while(ot>0) s[++idx]=ot%10+'0',ot/=10;
    while(idx) putchar(s[idx--]);
}
const int maxn=300000+5;
ll a[maxn];
int n,m;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
#define lson (o<<1)
#define rson (o<<1|1)
ll pre[maxn],nxt[maxn];
struct intervaltree{
    ll maxv[maxn<<2],minv[maxn<<2],gc[maxn<<2],lnum[maxn<<2],rnum[maxn<<2];
    void maintain(int o,int l,int r)
    {
        if(l<r){
            maxv[o]=max(maxv[lson],maxv[rson]);
            minv[o]=min(minv[lson],minv[rson]);
        }
        if(l==r) return;
        lnum[o]=lnum[lson],rnum[o]=rnum[rson];
        int del=rnum[lson]-lnum[rson];
        if(del<0) del=-del;
        gc[o]=gcd(gcd(gc[lson],del),gc[rson]);
    }
    void build(int o,int l,int r)
    {
        if(l>r) return;
        if(l==r) {
            maxv[o]=minv[o]=a[l],lnum[o]=a[l],rnum[o]=a[l],gc[o]=0;
            return;
        }else{
            int mid=(l+r)>>1;
            build(lson,l,mid);
            build(rson,mid+1,r);
            maintain(o,l,r);
        }
    }
    void getchg(int o,int l,int r,ll val)
    {
        assert(l==r);
        maxv[o]=minv[o]=val;
        lnum[o]=rnum[o]=val;
    }
    void Uchg(int o,int l,int r,int pos,ll val)
    {
        if(pos<l || pos>r) return;
        if(l==r && l==pos) {getchg(o,l,r,val);return;}
        else{
            int mid=(l+r)>>1;
            if(pos<=mid) Uchg(lson,l,mid,pos,val);
            else Uchg(rson,mid+1,r,pos,val);
            maintain(o,l,r);
        }
    }
    ll Qmos(int o,int l,int r,int ql,int qr,int typ) //1->max 0->min
    {
        if(ql>r || qr<l) return typ==1?LLONG_MIN:LLONG_MAX;
        if(ql<=l && r<=qr) return typ==1?maxv[o]:minv[o];
        else{
            int mid=(l+r)>>1;
            ll ret=(typ==1?LLONG_MIN:LLONG_MAX);
            if(ql<=mid) {
                if(typ==1) ret=max(ret,Qmos(lson,l,mid,ql,qr,typ));
                else ret=min(ret,Qmos(lson,l,mid,ql,qr,typ));
            }
            if(qr>mid) {
                if(typ==1) ret=max(ret,Qmos(rson,mid+1,r,ql,qr,typ));
                else ret=min(ret,Qmos(rson,mid+1,r,ql,qr,typ));
            }
            return ret;
        }
    }
    ll Qgcd(int o,int l,int r,int ql,int qr)
    {
        if(ql>r || qr<l) return 0;
        if(ql<=l && r<=qr) return gc[o];
        else{
            int mid=(l+r)>>1;
            ll ret=0;
            if(ql<=mid) ret=gcd(ret,Qgcd(lson,l,mid,ql,qr));
            if(qr>mid) ret=gcd(ret,Qgcd(rson,mid+1,r,ql,qr));
            return ret;
        }
    }
    void out()
    {
        for(int o=1;o<=n*2;o++) {
            printf("maxv[%d]=%lld minv[%d]=%lld\ngc[%d]=%lld lnum[%d]=%lld rnum[%d]=%lld\n",
            o,maxv[o],o,minv[o],o,gc[o],o,lnum[o],o,rnum[o]);
            puts("");
        }
    }
} Tree;
#define MP make_pair
void ok(){printf("Yes\r\n");}
void no(){printf("No\r\n");}
int main()
{
    scanf("%d%d",&n,&m);
    for(ll i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
    }
    int op;
    ll l,r,x,y,k;
    Tree.build(1,1,n);
    ll ys=0;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%lld%lld",&x,&y);
            x^=ys,y^=ys;
            a[x]=y;
            Tree.Uchg(1,1,n,x,y);
        }else if(op==2){
            scanf("%lld%lld%lld",&l,&r,&k);
            l^=ys,r^=ys,k^=ys;
            assert(l<=r);
            ll gd=Tree.Qgcd(1,1,n,l,r),mx=Tree.Qmos(1,1,n,l,r,1),mn=Tree.Qmos(1,1,n,l,r,0);
            if(((k==0 && gd==0) || (k>0 && gd%k==0)) && mx-mn==(r-l)*k) 
                ok(),ys++;
            else no();
        }
    }
    return 0;
}

条件1~3：容器+询问的常数，带起来就是$O(n\times 10logn)$了,常数有点大

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
173
174
175
176
177
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <climits>
#include <cassert>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
template<typename T> T readin(T &rd)
{
    char c;T tmp=0,x=1;c=getchar();
    while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
    while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
    return rd=tmp*x;
}
template<typename T> void writeout(T ot)
{
    if(ot==0) {putchar('0');return;}
    if(ot<0) {putchar('-');ot*=-1;}
    static char s[21];int idx=0;
    while(ot>0) s[++idx]=ot%10+'0',ot/=10;
    while(idx) putchar(s[idx--]);
}
const int maxn=300000+5;
ll a[maxn];
int n,m;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
#define lson (o<<1)
#define rson (o<<1|1)
ll pre[maxn],nxt[maxn];
struct intervaltree{
    ll maxv[3][maxn<<2],minv[3][maxn<<2],gc[maxn<<2],lnum[maxn<<2],rnum[maxn<<2];
    void maintain(int id,int o,int l,int r)
    {
        if(l<r){
            maxv[id][o]=max(maxv[id][lson],maxv[id][rson]);
            minv[id][o]=min(minv[id][lson],minv[id][rson]);
        }
        if(l==r) return;
        if(id==0) {
            lnum[o]=lnum[lson],rnum[o]=rnum[rson];
            int del=rnum[lson]-lnum[rson];
            if(del<0) del=-del;
            gc[o]=gcd(gcd(gc[lson],del),gc[rson]);
        }
    }
    void build(int id,int o,int l,int r)
    {
        if(l>r) return;
        if(l==r) {
            if(id==0) maxv[id][o]=minv[id][o]=a[l],lnum[o]=a[l],rnum[o]=a[l],gc[o]=0;
            else if(id==1) maxv[id][o]=minv[id][o]=pre[l];
            else if(id==2) maxv[id][o]=minv[id][o]=nxt[l];
            return;
        }else{
            int mid=(l+r)>>1;
            build(id,lson,l,mid);
            build(id,rson,mid+1,r);
            maintain(id,o,l,r);
        }
    }
    void getchg(int id,int o,int l,int r,ll val)
    {
        assert(l==r);
        maxv[id][o]=minv[id][o]=val;
        if(id==0) lnum[o]=rnum[o]=val;
    }
    void Uchg(int id,int o,int l,int r,int pos,ll val)
    {
        if(pos<l || pos>r) return;
        if(l==r && l==pos) {getchg(id,o,l,r,val);return;}
        else{
            int mid=(l+r)>>1;
            if(pos<=mid) Uchg(id,lson,l,mid,pos,val);
            else Uchg(id,rson,mid+1,r,pos,val);
            maintain(id,o,l,r);
        }
    }
    ll Qmos(int id,int o,int l,int r,int ql,int qr,int typ) //1->max 0->min
    {
        if(ql>r || qr<l) return typ==1?LLONG_MIN:LLONG_MAX;
        if(ql<=l && r<=qr) return typ==1?maxv[id][o]:minv[id][o];
        else{
            int mid=(l+r)>>1;
            ll ret=(typ==1?LLONG_MIN:LLONG_MAX);
            if(ql<=mid) {
                if(typ==1) ret=max(ret,Qmos(id,lson,l,mid,ql,qr,typ));
                else ret=min(ret,Qmos(id,lson,l,mid,ql,qr,typ));
            }
            if(qr>mid) {
                if(typ==1) ret=max(ret,Qmos(id,rson,mid+1,r,ql,qr,typ));
                else ret=min(ret,Qmos(id,rson,mid+1,r,ql,qr,typ));
            }
            return ret;
        }
    }
    ll Qgcd(int o,int l,int r,int ql,int qr)
    {
        if(ql>r || qr<l) return 0;
        if(ql<=l && r<=qr) return gc[o];
        else{
            int mid=(l+r)>>1;
            ll ret=0;
            if(ql<=mid) ret=gcd(ret,Qgcd(lson,l,mid,ql,qr));
            if(qr>mid) ret=gcd(ret,Qgcd(rson,mid+1,r,ql,qr));
            return ret;
        }
    }
    void out()
    {
        for(int o=1;o<=n*2;o++) {
            printf("maxv[%d]=%lld minv[%d]=%lld\ngc[%d]=%lld lnum[%d]=%lld rnum[%d]=%lld\n",
            o,maxv[0][o],o,minv[0][o],o,gc[o],o,lnum[o],o,rnum[o]);
            puts("");
        }
    }
} Tree;
#define MP make_pair
void ok(){printf("Yes\r\n");}
void no(){printf("No\r\n");}
map<ll ,set<ll > > ss;
int main()
{
    scanf("%d%d",&n,&m);
    for(ll i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
        ss[a[i]].insert(i);
    }
    set<ll>::iterator ite;
    for(int i=1;i<=n;i++){
        ite=ss[a[i]].upper_bound(i);
        nxt[i]=(ite==ss[a[i]].end())?LLONG_MAX:*ite;
        ite=ss[a[i]].lower_bound(i);
        pre[i]=(ite==ss[a[i]].begin())?LLONG_MIN:*(--ite);
    }
    Tree.build(1,1,1,n),Tree.build(2,1,1,n);
    int op;
    ll l,r,x,y,k;
    Tree.build(0,1,1,n);
    ll ys=0;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%lld%lld",&x,&y);
            x^=ys,y^=ys;
            ll pr=pre[x],nx=nxt[x];
            if(pr!=LLONG_MIN) {Tree.Uchg(2,1,1,n,pr,nx);nxt[pr]=nx;}
            if(nx!=LLONG_MAX) {Tree.Uchg(1,1,1,n,nx,pr);pre[nx]=pr;}
            ss[a[x]].erase(x);
            ss[y].insert(x);
            ite=ss[y].upper_bound(x);
            nxt[x]=(ite==ss[y].end())?LLONG_MAX:*ite;
            ite=ss[y].lower_bound(x);
            pre[x]=(ite==ss[y].begin())?LLONG_MIN:*(--ite);
            a[x]=y;
            if(pre[x]!=LLONG_MIN) Tree.Uchg(2,1,1,n,pre[x],x);
            if(nxt[x]!=LLONG_MAX) Tree.Uchg(1,1,1,n,nxt[x],x);
            Tree.Uchg(1,1,1,n,x,pre[x]);
            Tree.Uchg(2,1,1,n,x,nxt[x]);
            Tree.Uchg(0,1,1,n,x,y);
        }else if(op==2){
            scanf("%lld%lld%lld",&l,&r,&k);
            l^=ys,r^=ys,k^=ys;
            assert(l<=r);
            ll gd=Tree.Qgcd(1,1,n,l,r),mx=Tree.Qmos(0,1,1,n,l,r,1),mn=Tree.Qmos(0,1,1,n,l,r,0);
            ll premx=Tree.Qmos(1,1,1,n,l,r,1),nxtmn=Tree.Qmos(2,1,1,n,l,r,0);
            if(((k==0 && gd==0) || (k>0 && gd%k==0)) && mx-mn==(r-l)*k && (k==0 || (k>0 && premx<l && nxtmn>r))) 
                ok(),ys++;
            else no();
        }
    }
    return 0;
}