BZOJ4373 算术天才⑨与等差数列 <线段树+set>

Posted on Symbols count in article: 1.3k Reading time ≈ 5 mins.

Problem

算术天才⑨与等差数列

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为nn的序列，其中第ii个数为aia_i。
他想考考你，每次他会给出询问l,r,kl,r,k，问区间[l,r][l,r]内的数从小到大排序后能否形成公差为kk的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。

Input

第一行包含两个正整数n,m  (1≤n,m≤300000)n,m\;(1\le n,m\le300000)，分别表示序列的长度和操作的次数。
第二行包含nn个整数，依次表示序列中的每个数ai  (0≤ai≤109)a_i\;(0\le a_i\le10^9)。
接下来mm行，每行一开始为一个数opop，
若op=1op=1，则接下来两个整数x,y  (1≤x≤n,0≤y≤109)x,y\;(1\le x\le n,0\le y\le10^9)，表示把axa_x修改为yy。
若op=2op=2，则接下来三个整数l,r,k  (1≤l≤r≤n,0≤k≤109)l,r,k\;(1\le l\le r\le n,0\le k\le10^9)，表示一个询问。
在本题中，x,y,l,r,kx,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。

Output

输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。

Sample Input

1
2
3
4
5
5 3
1 3 2 5 6
2 1 5 1
1 5 4
2 1 5 1

Sample Output

1
2
No
Yes

标签：线段树 set

Solution

线段树判断等差数列，单点修改。

若区间al∼ara_l\sim a_r组成等差数列，则一定有：

  • max⁡i=lrai−min⁡i=lrai=(r−l)×k\max_{i=l}^{r}a_i-\min_{i=l}^{r}a_i=(r-l)\times k
  • 没有重复的数
  • gcd⁡{al,al+1,⋯ ,ar}=k\gcd\lbrace a_l,a_{l+1},\cdots,a_{r}\rbrace=k

其中若存在l=rl=r的情况要单独处理。

对于第一、三个条件，用线段树存储区间min⁡,max⁡,gcd⁡\min,\max,\gcd即可。
对于第二个条件，需要在外面用set\mathrm{set}维护每个位置的值上一次出现在哪个位置，将这个位置存入线段树中，区间求max⁡\max，若最大值小于ll，则一定没有重复的数。

注意修改时不止当前位置的前驱会发生变化，所以需要多次更新。

Code

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
#include <bits/stdc++.h>
#define fir first
#define sec second
#define MAX_N 300000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef set<pii>::iterator IT;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, a[MAX_N+5], lst[MAX_N+5]; set <pii> S;
int mi[MAX_N<<2], mx[MAX_N<<2], pr[MAX_N<<2], cg[MAX_N<<2];
int gcd(int x, int y) {return (~x) ? (y ? gcd(y, x%y) : x) : y;}
void update(int v) {
    mi[v] = min(mi[v<<1], mi[v<<1|1]), mx[v] = max(mx[v<<1], mx[v<<1|1]);
    pr[v] = min(pr[v<<1], pr[v<<1|1]), cg[v] = gcd(cg[v<<1], cg[v<<1|1]);
}
void init(int v, int p) {mi[v] = mx[v] = a[p], pr[v] = lst[p], cg[v] = abs(a[p]-a[p-1]);}
void build(int v, int s, int t) {
    if (s == t) {init(v, s); return;}
    build(v<<1, s, mid);
    build(v<<1|1, mid+1, t);
    update(v);
}
void modify(int v, int s, int t, int p) {
    if (s == t) {init(v, s); return;}
    if (p <= mid) modify(v<<1, s, mid, p);
    if (p >= mid+1) modify(v<<1|1, mid+1, t, p);
    update(v);
}
int query_mi(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return mi[v]; int ret = INF;
    if (l <= mid) ret = min(ret, query_mi(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = min(ret, query_mi(v<<1|1, mid+1, t, l, r));
    return ret;
}
int query_mx(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return mx[v]; int ret = 0;
    if (l <= mid) ret = max(ret, query_mx(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = max(ret, query_mx(v<<1|1, mid+1, t, l, r));
    return ret;
}
int query_pr(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return pr[v]; int ret = 0;
    if (l <= mid) ret = max(ret, query_pr(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = max(ret, query_pr(v<<1|1, mid+1, t, l, r));
    return ret;
}
int query_cg(int v, int s, int t, int l, int r) {
    if (l > r) return 0;
    if (s >= l && t <= r) return cg[v]; int ret = -1;
    if (l <= mid) ret = gcd(ret, query_cg(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = gcd(ret, query_cg(v<<1|1, mid+1, t, l, r));
    return ret;
}
int main() {
    freopen("1.in", "r", stdin);
    freopen("test.out", "w", stdout);
    read(n), read(m), S.insert(pii(-1, 0)), S.insert(pii(INF, 0));
    for (int i = 1; i <= n; i++) {
        read(a[i]); IT it = S.upper_bound(pii(a[i], i)); it--;
        if ((*it).fir == a[i]) lst[i] = (*it).sec; S.insert(pii(a[i], i));
    }
    build(1, 1, n);
    for (int cnt = 0; m; m--) {
        int opt; read(opt);
        if (opt == 1) {
            int p, x; read(p), read(x), p ^= cnt, x ^= cnt;
            S.erase(pii(a[p], p)); IT it = S.upper_bound(pii(a[p], p));
            if ((*it).fir == a[p]) lst[(*it).sec] = lst[p], modify(1, 1, n, (*it).sec);
            a[p] = x, it = S.upper_bound(pii(a[p], p));
            if ((*it).fir == a[p]) lst[(*it).sec] = p, modify(1, 1, n, (*it).sec);
            it--, lst[p] = (*it).fir == a[p] ? (*it).sec : 0, S.insert(pii(a[p], p));
            modify(1, 1, n, p); if (p < n) modify(1, 1, n, p+1);
        }
        if (opt == 2) {
            int l, r, k; read(l), read(r), read(k), l ^= cnt, r ^= cnt, k ^= cnt;
            int MX = query_mx(1, 1, n, l, r), MI = query_mi(1, 1, n, l, r);
            if (!k) {if (MX == MI) cnt++, puts("Yes"); else puts("No"); continue;}
            if (query_pr(1, 1, n, l, r) >= l || query_cg(1, 1, n, l+1, r)%k) {puts("No"); continue;}
            if (1LL*(MX-MI) != 1LL*(r-l)*k) {puts("No"); continue;} cnt++, puts("Yes");
        }
    }
    return 0;
}