CF1599F Mars 题解
Nagisa_Tomoya
·
·
题解
题目大意
每次 check 出一个区间是否能被重排为公差为 d 的等差数列。
乱搞过去的（
首先可以很轻易的算出等差数列的首项。
然后把 d = 0 和 d >0 分开来考虑。
$d>0$ 的话，先 check 一下是否整个区间所有数都不同，这个可以轻易的用线段树实现。
然后在区间内随一些数，若它不是末项的话看它的后继是否在 $[l,r]$ 内即可。可以预处理一个 set 来做。
正确率应该很高，至少我不会卡（
假设每次随 $B$ 个数，那么时间复杂度即为 $O(n\log n + qB\log n)$。
事实上后面这项常数很小，$B$ 取 $100$ 可以通过。
```cpp
/*
60 + 0 + 100 + 64 = 224.
*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int sum = 0, nega = 1;
char ch = getchar();
while (ch > '9'||ch < '0')
{
if (ch == '-') nega = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') sum = sum * 10 + ch - '0', ch = getchar();
return sum * nega;
}
const int N = 2e5 + 9, mod = 1e9 + 7;
inline int Pow(int x, int y)
{
int res = 1, base = x;
while(y)
{
if(y & 1) res = res * base % mod;
base = base * base % mod; y >>= 1;
} return res;
}
int tr[N << 2], nxt[N], n, q, a[N];
inline int lc(int p) {return p << 1;}
inline int rc(int p) {return p << 1 | 1;}
inline void build(int l, int r, int p)
{
if(l == r) {tr[p] = nxt[l]; return ;}
int mid = (l + r) >> 1; build(l, mid, lc(p)), build(mid + 1, r, rc(p));
tr[p] = min(tr[lc(p)], tr[rc(p)]); return ;
}
inline int query(int l, int r, int p, int L, int R)
{
if(L <= l && r <= R) return tr[p];
int res = 1e9, mid = (l + r) >> 1;
if(mid >= L) res = min(res, query(l, mid, lc(p), L, R));
if(mid < R) res = min(res, query(mid + 1, r, rc(p), L, R)); return res;
}
map<int, int> mp;
set<int> s[N];
int cnt, tmp[N], sum[N], eq[N];
inline bool find(int t, int l, int r)
{
if(!mp[t]) return 0;
int po = mp[t];
if(s[po].lower_bound(l) == s[po].end()) return 0;
if(*s[po].lower_bound(l) > r) return 0;
return 1;
}
signed main()
{
int B = 100;
n = read(), q = read();
for (int i = 1; i <= n; i++) a[i] = read(), sum[i] = (sum[i - 1] + a[i]) % mod, eq[i] = eq[i - 1] + (a[i] == a[i - 1]);
for (int i = 1; i <= n; i++)
if(!mp[a[i]]) mp[a[i]] = ++cnt;
for (int i = 1; i <= n; i++) s[mp[a[i]]].insert(i);
for (int i = 1; i <= cnt; i++) tmp[i] = n + 1;
for (int i = n; i >= 1; i--)
nxt[i] = tmp[mp[a[i]]], tmp[mp[a[i]]] = i;
build(1, n, 1);
for (int i = 1; i <= q; i++)
{
int l = read(), r = read(), d = read(), len = (r - l + 1);
if(l == r) {puts("Yes"); continue;}
if(query(1, n, 1, l, r) <= r && d) {puts("No"); continue;}
if(!d)
{
if(eq[r] - eq[l] == r - l) puts("Yes");
else puts("No"); continue;
}
int su = (sum[r] - sum[l - 1] + mod) % mod, t = (su - len * (len - 1) / 2 % mod * d % mod + mod) % mod;
// cout << su << " " << t << endl;
t = t * Pow(len, mod - 2) % mod; int sb = (t + (len - 1) * d) % mod;
if(!find(t, l, r)) {puts("No"); continue;}
bool fl = 0;
for (int j = 1; j <= B; j++)
{
int x = l + rand() % len;
if(a[x] == sb) continue;
if(!find((a[x] + d) % mod, l, r))
{
puts("No"); fl = 1; break;
}
}
if(!fl) puts("Yes");
}
return 0;
}
```