fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define mp make_pair
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8. const int N = 1e6 + 5;
  9.  
  10. struct Node{
  11.     int l, r, x, id;
  12. };
  13. int n, q, a[N], mn[N << 2], mx[N << 2], st[N << 2], g[N][25];
  14. bool ans[N];
  15. map<int, int> m;
  16. Node query[N];
  17. bool cmp(Node a, Node b){
  18.     return a.r < b.r;
  19. }
  20. void build(int l, int r, int x){
  21.     if (l == r){
  22.         mn[x] = mx[x] = a[l];
  23.         return;
  24.     }
  25.     int mid = (l + r) >> 1;
  26.     build(l, mid, x << 1);
  27.     build(mid + 1, r, x << 1 | 1);
  28.     mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
  29.     mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
  30. }
  31. int getmin(int u, int v, int l = 1, int r = n, int x = 1){
  32.     if (l > v || r < u) return INT_MAX;
  33.     if (l >= u && r <= v) return mn[x];
  34.     int mid = (l + r) >> 1;
  35.     if (v <= mid) return getmin(u, v, l, mid, x << 1);
  36.     if (u > mid) return getmin(u, v, mid + 1, r, x << 1 | 1);
  37.     return min(getmin(u, v, l, mid, x << 1), getmin(u, v, mid + 1, r, x << 1 | 1));
  38. }
  39. int getmax(int u, int v, int l = 1, int r = n, int x = 1){
  40.     if (l > v || r < u) return INT_MIN;
  41.     if (l >= u && r <= v) return mx[x];
  42.     int mid = (l + r) >> 1;
  43.     if (v <= mid) return getmax(u, v, l, mid, x << 1);
  44.     if (u > mid) return getmax(u, v, mid + 1, r, x << 1 | 1);
  45.     return max(getmax(u, v, l, mid, x << 1), getmax(u, v, mid + 1, r, x << 1 | 1));
  46. }
  47. void update(int pos, int val, int l = 1, int r = n, int x = 1){
  48.     if (l == r){
  49.         st[x] = val;
  50.         return;
  51.     }
  52.     int mid = (l + r) >> 1;
  53.     if (pos <= mid) update(pos, val, l, mid, x << 1);
  54.     else update(pos, val, mid + 1, r, x << 1 | 1);
  55.     st[x] = st[x << 1] + st[x << 1 | 1];
  56. }
  57. int get(int u, int v, int l = 1, int r = n, int x = 1){
  58.     if (l > v || r < u) return 0;
  59.     if (l >= u && r <= v) return st[x];
  60.     int mid = (l + r) >> 1;
  61.     if (v <= mid) return get(u, v, l, mid, x << 1);
  62.     if (u > mid) return get(u, v, mid + 1, r, x << 1 | 1);
  63.     return get(u, v, l, mid, x << 1) + get(u, v, mid + 1, r, x << 1 | 1);
  64. }
  65. int getgcd(int l, int r){
  66.     ++l;
  67.     int k = __lg(r - l + 1);
  68.     return __gcd(g[l][k], g[r - (1 << k) + 1][k]);
  69. }
  70. signed main(){
  71.     cin >> n >> q;
  72.     for (int i = 1; i <= n; ++i){
  73.         cin >> a[i];
  74.         if (i >= 2) g[i][0] = abs(a[i] - a[i - 1]);
  75.     }
  76.     for (int i = 1; i <= q; ++i){
  77.         cin >> query[i].l >> query[i].r >> query[i].x;
  78.         query[i].id = i;
  79.     }
  80.     build(1, n, 1);
  81.     for (int i = 1; i <= 20; ++i){
  82.         for (int j = 2; j <= n - (1 << i) + 1; ++j){
  83.             g[j][i] = __gcd(g[j][i - 1], g[j + (1 << (i - 1))][i - 1]);
  84.         }
  85.     }
  86.     sort(query + 1, query + 1 + q, cmp);
  87.     int r = 1; 
  88.     for (int i = 1; i <= q; ++i){
  89.         int u = query[i].l, v = query[i].r;
  90.         int x = query[i].x, id = query[i].id;   
  91.         while (r <= v){
  92.             if (m[a[r]]){
  93.                 update(m[a[r]], 0);
  94.             }
  95.             m[a[r]] = r;
  96.             update(r, 1);
  97.             ++r;
  98.         }
  99.         if(u == v){
  100.             ans[id] = true;
  101.             continue;
  102.         }
  103.         if(x == 0){
  104.             ans[id] = getmin(u,v) == getmax(u,v);
  105.         }
  106.         if (v - u + 1 != get(u, v)) continue; 
  107.         int curmin = getmin(u, v), curmax = getmax(u, v),cnt = get(u,v);
  108.         if (curmax != curmin + x * (v - u)) continue;
  109.         ans[id] = (getgcd(u, v) == x && cnt == v - u + 1);
  110.     }
  111.     for (int i = 1; i <= q; ++i){
  112.         cout << (ans[i] ? "YES\n" : "NO\n");
  113.     }
  114. }
  115.  
Success #stdin #stdout 0.01s 13748KB
comments (?)
stdin
copy 
7 3
3 7 5 11 8 14 3
1 3 2
1 3 3
3 6 3
stdout
copy 
YES
NO
YES
https://ideone.com/Jcc1lb
language:
C++ (gcc 8.3)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!