4373: 算术天才⑨与等差数列
Time Limit: 10 Sec Memory Limit: 128 MBDescription
算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。当然，他还会不断修改其中的某一项。为了不被他鄙视，你必须要快速并正确地回答完所有问题。注意：只有一个数的数列也是等差数列。Input
第一行包含两个正整数n,m(1<=n,m<=300000)，分别表示序列的长度和操作的次数。
第二行包含n个整数，依次表示序列中的每个数a[i](0<=a[i]<=10^9)。接下来m行，每行一开始为一个数op，若op=1，则接下来两个整数x,y(1<=x<=n，0<=y<=10^9)，表示把a[x]修改为y。若op=2，则接下来三个整数l,r,k(1<=l<=r<=n，0<=k<=10^9)，表示一个询问。在本题中，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
题解
可以发现，如果是等差数列的话，所有相邻两项的gcd必然是k，而且满足最大数与最小数的差满足等差数列。
线段树维护区间相邻两项差的gcd，区间max，区间min，\(O(n \log{n} + m\log ^ {2}n)\)
代码
1 #include2 using namespace std; 3 template inline void read(_T &_x) { 4 int _t; bool flag = false; 5 while ((_t = getchar()) != '-' && (_t < '0' || _t > '9')) ; 6 if (_t == '-') _t = getchar(), flag = true; _x = _t - '0'; 7 while ((_t = getchar()) >= '0' && _t <= '9') _x = _x * 10 + _t - '0'; 8 if (flag) _x = -_x; 9 }10 typedef long long LL;11 const int maxn = 300010;12 #define reg register13 #define max(a, b) (a > b ? a : b)14 #define min(a, b) (a > b ? b : a)15 inline int gcd(reg int a, reg int b) {16 reg int t;17 while (b) t = a, a = b, b = t % b;18 return a;19 }20 inline int Abs(int v) { return v > 0 ? v : -v; }21 struct Tnode {22 int g, mn, mx;23 inline Tnode(int a = 0, int b = 0, int c = 0):g(a), mn(b), mx(c) {}24 inline Tnode operator + (Tnode B) const {25 if (g == -1) return B;26 if (B.g == -1) return *this;27 Tnode C;28 C.g = gcd(gcd(g, B.g), Abs(B.mx - mn));29 C.mn = min(mn, B.mn), C.mx = max(mx, B.mx);30 return C;31 }32 }t[(1 << 21) + 1];33 int n, m, N;34 inline void change(reg int x, int y) {35 x += N, t[x].mn = t[x].mx = y;36 while (x >>= 1) t[x] = t[x << 1] + t[x << 1 | 1];37 }38 inline bool query(reg int x, reg int y, int z) {39 //cout << x << ' ' << y << ' ' << z << ':' << endl;40 LL len = z * (y - x);41 Tnode r = t[x + N];42 for (x += N - 1, y += N + 1; y - x > 1; x >>= 1, y >>= 1) {43 if (~x & 1) r = r + t[x ^ 1];44 if ( y & 1) r = r + t[y ^ 1];45 }46 //cout << r.g << ' ' << r.mn << ' ' << r.mx << endl;47 return (r.g == z && r.mx - r.mn == len);48 }49 int main() {50 //freopen(".in", "r", stdin);51 //freopen(".out", "w", stdout);52 read(n), read(m);53 int yescnt = 0;54 N = 1 << ((int)log2(n + 1) + 1);55 for (reg int i = N + 1; i <= N + n; ++i) {56 int v; read(v);57 t[i].g = 0, t[i].mn = t[i].mx = v;58 }59 for (reg int i = N + n + 1; i < N + N; ++i) t[i] = Tnode(-1, 0, 0);60 for (reg int i = N - 1; i >= 1; --i)61 t[i] = t[i << 1] + t[i << 1 | 1];62 for (int i = 1, op, x, y, z; i <= m; ++i) {63 read(op);64 if (op == 1) {65 read(x), read(y);66 x ^= yescnt, y ^= yescnt;67 change(x, y);68 } else {69 read(x), read(y), read(z);70 x ^= yescnt, y ^= yescnt, z ^= yescnt;71 if (x == y || query(x, y, z)) puts("Yes"), ++yescnt;72 else puts("No");73 }74 }75 return 0;76 }