算术天才⑨与等差数列

Time Limit: 10 Sec Memory Limit: 128 MB

Description

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

Input

第一行包含两个正整数n,m，分别表示序列的长度和操作的次数。
　第二行包含n个整数，依次表示序列中的每个数a[i]。
　接下来m行，每行一开始为一个数op，
　若op=1，则接下来两个整数x,y，表示把a[x]修改为y。
　若op=2，则接下来三个整数l,r,k，表示一个询问。
　在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。

Output

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

Sample Input

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

Sample Output

No
　Yes

HINT

1<=n,m<=300000, 0<=a[i]<=10^9, 1<=x<=n，0<=y<=10^9, 1<=l<=r<=n, 0<=k<=10^9

Solution

显然，如果可以组成等差数列，首项必定是区间最小值。这样我们就知道了要求的等差数列的首项和公差。

一个首先的想法就是：我们判断一下区间和是否等于所要求的等差数列的和。

但是这样显然是不够的，那么怎么办呢？我们试想：能否求出所要求的等差数列的平方和？

显然公差为 1 的时候用平方和公式计算，剩下公差不是 1 的时候我们轻易推一下式子即可。

img

那么我们只要用线段树维护一下：区间最小值、区间和、区间平方和即可，资磁单点修改。

正确性不会证明啊，但是满足的概率应该挺大的吧qwq

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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 500005;
const int INF = 1e9+7;

int n, T;
s64 a[ONE];
int opt, x, y, d;
int num;

struct power
{
    s64 sumx, sumxx, minx;
}Node[ONE * 4], res;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Renew(int i)
{
    int a = i<<1, b = i<<1|1;
    Node[i].sumx = Node[a].sumx + Node[b].sumx;
    Node[i].sumxx = Node[a].sumxx + Node[b].sumxx;
    Node[i].minx = min(Node[a].minx, Node[b].minx);
}

void Build(int i, int l, int r)
{
    Node[i].minx = INF;
    if(l == r)
    {
        Node[i].minx = a[l];
        Node[i].sumx = a[l];
        Node[i].sumxx = a[l] * a[l];
        return;
    }

    int mid = l + r >> 1;
    Build(i<<1, l, mid);  Build(i<<1|1, mid+1, r);
    Renew(i);
}

void Update(int i, int l, int r, int L, s64 x)
{
    if(l > r) return;
    if(L == l && l == r)
    {
        Node[i].minx = x;
        Node[i].sumx = x;
        Node[i].sumxx = x * x;
        return;
    }

    int mid = l + r >> 1;
    if(L <= mid) Update(i<<1, l, mid, L, x);
    else Update(i<<1|1, mid+1, r, L, x);
    Renew(i);
}

void Query(int i, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
    {
        res.minx = min(res.minx, Node[i].minx);
        res.sumx += Node[i].sumx;
        res.sumxx += Node[i].sumxx;
        return;
    }

    int mid = l + r >> 1;
    if(L <= mid) Query(i<<1, l, mid, L, R);
    if(mid+1 <= R) Query(i<<1|1, mid+1, r, L, R);
}

s64 Calc_sumx(s64 a0, s64 n, s64 d)
{
    s64 an = a0 + (n-1) * d;
    return (a0 + an) * n / 2;
}

s64 Calc_sumxx(s64 a0, s64 n, s64 d)
{
    s64 item1 = n * a0 * a0;
    s64 item2 = 2 * a0 * d * n * (n-1) / 2;
    s64 item3 = d * d * (n * (n+1) * (2*n+1) / 6 - n*n);
    return item1 + item2 + item3;
}

int main()
{
    n = get();  T = get();
    for(int i=1; i<=n; i++)
        a[i] = get();
    Build(1, 1, n);

    while(T--)
    {
        opt = get();
        x = get() ^ num;    y = get() ^ num;

        if(opt == 1)
        {
            Update(1, 1, n, x, y);
            continue;
        }
        else
        {
            d = get() ^ num;
            res.minx = INF;
            res.sumx = res.sumxx = 0;
            Query(1, 1, n, x, y);

            if(res.sumx == Calc_sumx(res.minx, y-x+1, d))
                if(res.sumxx == Calc_sumxx(res.minx, y-x+1, d))
                {
                    printf("Yes\n");
                    num++;
                    continue;
                }

            printf("No\n");
        }
    }

}