emmmm… 第一次考场做这么恶心的题还打错了。。。记录一下。。。
1. 题目
题意：维护一个序列，两种操作：
- 单点修改
- 询问一个区间排序后是否为等差序列
复杂度要求 $O(nlog_2n)$，强制在线
2. 题解
这是一道考试的题目，这题真™有毒。
考场我从 9 点打到 10 点，发现思路错了，但是能改（只要加个功能就行了），然后 10 点半打完功能，对拍，拍一下错一下，最后一个 BUG 是在 11:30 拍出来的，11:50 修改完过了对拍卡完了常，10 分钟打了后面三题暴力提交（我真是佩服我的手速）。
最后得分全是后三题的暴力，也就是说我一上午拿了 10 分钟的分。。。
第一题为什么挂了呢？因为我对拍的时候为了使得数据生成器更好写，我就把强制在线的异或关掉了。
提交的时候忘了开。
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
（以上 “哈哈” 使用倍增算法生成）
It’s easy to think, but it’s difficult to code. —— Cai
首先对于一个区间，排序后的等差序列的首项与末项一定分别为区间最小和最大。
然后区间和一定为首项加末项乘以项数除以二。
而且原序列的差分序列的区间 GCD 一定等于公差。（考场我想成了区间 GCD 与公差的 GCD 等于公差，然而这并不会影响答案）
最后还有区间内一定不能有重复的元素（除非公差等于 0）
那么我们只要维护：
- 区间最大
- 区间最小
- 区间和
- 差分序列的区间 GCD
- 区间内是否有重复元素
怎么维护 “区间内是否有重复元素” 呢？
考虑对于序列的第 $i$个元素 $a[i]$，维护它右边的与 $a[i]$相等的元素中的最小下标，设这个值为 $low[i]$，也就是 $low[i]=min(j),a[j]=a[i]$
这个怎么维护呢？对于每个数字离散化一下，然后到该数字离散化后对应的平衡树（set）里找一下它的后继即可。
然后再搞个线段树维护区间 $low[i]$的最小值，如果区间 $[l,r]$内最小的 $low$值 $\leq r$则说明区间内有重复元素。
这里离散化还要动态搞，得用 map。。。
然后细节特别多，比如修改一个数的时候要把原数删除，然后修改它前驱的 $low$值，然后插入，修改它自己的 $low$值，然后修改它插入后的前驱的 $low$值。。。等等等的。。。
考场上原本只开了 1 秒时限然后没说开不开 O2。。。于是我又去卡常，什么用 pbds 的 hashtable 替换 map 啊，用 tree 替换 set 啊。。。等等等等。。。（后面的代码因为 bzoj 不支持 pbds 就用的 map 和 set）
打了我一个上午结果忘了关对拍就 GG 了。。。
艹。。。
还是那句老话：
代码：
#include <bits/stdc++.h>
#define NS (300005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)
#define REG register
using namespace std;
typedef long long LL;
template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}
int n, m, arr[NS], dt[NS], pre[NS];
int mn[NS << 2], mx[NS << 2], mp[NS << 2], gc[NS << 2];
LL sum[NS << 2];
map<int, int> h;
set<int> pos[NS << 1];
struct Pac
{
int x, y, o; LL z;
Pac() {x = y = z = o = 0;}
Pac(REG int a, REG int b, REG LL c, REG int d) {x = a, y = b, z = c, o = d;}
};
int hs = 0;
inline int H(REG int a)
{
REG int tmp = h[a];
if (tmp != 0) return tmp;
h[a] = ++hs; return hs;
}
/*SGT1 for mn, mx, sum and min_pos*/
inline void pup1(REG int a)
{
REG int l = LS(a), r = RS(a);
sum[a] = sum[l] + sum[r], mp[a] = min(mp[l], mp[r]);
mn[a] = min(mn[l], mn[r]), mx[a] = max(mx[l], mx[r]);
}
void Build1(REG int l, REG int r, REG int a)
{
if (l == r)
{
mn[a] = mx[a] = sum[a] = arr[l], mp[a] = pre[l];
return;
}
REG int mid = (l + r) >> 1;
Build1(l, mid, LS(a)), Build1(mid + 1, r, RS(a)), pup1(a);
}
inline void Update1(REG int x, REG int d)
{
REG int a = 1, l = 1, r = n, mid;
while (l < r)
{
if (mid = (l + r) >> 1, x <= mid) a = LS(a), r = mid;
else a = RS(a), l = mid + 1;
}
mn[a] = mx[a] = sum[a] = d, a >>= 1;
while (a) pup1(a), a >>= 1;
}
inline void Update_mp(REG int x, REG int d)
{
REG int a = 1, l = 1, r = n, mid;
while (l < r)
{
if (mid = (l + r) >> 1, x <= mid) a = LS(a), r = mid;
else a = RS(a), l = mid + 1;
}
mp[a] = d, a >>= 1;
while (a) pup1(a), a >>= 1;
}
Pac Query1(int l, int r, int L, int R, int a)
{
if (l <= L && R <= r) return Pac(mn[a], mx[a], sum[a], mp[a]);
int Mid = (L + R) >> 1;
Pac res(INT_MAX, INT_MIN, 0, INT_MAX), tmp;
if (l <= Mid)
{
tmp = Query1(l, r, L, Mid, LS(a));
res.x = min(res.x, tmp.x);
res.y = max(res.y, tmp.y);
res.z += tmp.z, res.o = min(res.o, tmp.o);
}
if (r > Mid)
{
tmp = Query1(l, r, Mid + 1, R, RS(a));
res.x = min(res.x, tmp.x);
res.y = max(res.y, tmp.y);
res.z += tmp.z, res.o = min(res.o, tmp.o);
}
return res;
}
/*SGT2 for gcd*/
int gcd(REG int a, REG int b) {return b ? gcd(b, a % b) : a;}
inline void pup2(int a)
{
REG int l = LS(a), r = RS(a);
gc[a] = gcd(gc[l], gc[r]);
return;
}
void Build2(REG int l, REG int r, REG int a)
{
if (l == r) {gc[a] = dt[l]; return;}
REG int mid = (l + r) >> 1;
Build2(l, mid, LS(a)), Build2(mid + 1, r, RS(a)), pup2(a);
}
inline void Update2(REG int x, REG int d)
{
REG int a = 1, l = 1, r = n - 1, mid;
while (l < r)
{
if (mid = (l + r) >> 1, x <= mid) a = LS(a), r = mid;
else a = RS(a), l = mid + 1;
}
gc[a] = d, a >>= 1;
while (a) pup2(a), a >>= 1;
}
int Query2(REG int l, REG int r, REG int L, REG int R, REG int a)
{
if (l <= L && R <= r) return gc[a];
REG int Mid = (L + R) >> 1, res = -1;
if (l <= Mid)
{
if (res < 0) res = Query2(l, r, L, Mid, LS(a));
else res = gcd(res, Query2(l, r, L, Mid, LS(a)));
}
if (r > Mid)
{
if (res < 0) res = Query2(l, r, Mid + 1, R, RS(a));
else res = gcd(res, Query2(l, r, Mid + 1, R, RS(a)));
}
return res;
}
int main(int argc, char const* argv[])
{
IN(n), IN(m);
if (n == 1)
{
while (m--) puts("Yes");
return 0;
}
for (REG int i = 1; i <= n; i += 1) IN(arr[i]);
for (REG int i = n, j; i >= 1; i -= 1)
{
j = H(arr[i]);
if (pos[j].empty()) pre[i] = n + 1;
else pre[i] = *(pos[j].upper_bound(i));
pos[j].insert(i);
}
for (REG int i = 1; i < n; i += 1) dt[i] = abs(arr[i + 1] - arr[i]);
Build1(1, n, 1), Build2(1, n - 1, 1);
REG int op, x, y, k, tot = 0, h, g; Pac tmp; int cnt = 0;
REG set<int>::iterator it;
while (m--)
{
IN(op), IN(x), IN(y), x ^= tot, y ^= tot;
if (op == 1)
{
Update1(x, y), h = H(arr[x]), pos[h].erase(x);
it = pos[h].upper_bound(x);
if (it != pos[h].begin())
{
if (it == pos[h].end()) it--, Update_mp(*it, n + 1);
else
{
REG int tmp = *it; it--;
Update_mp(*it, tmp);
}
}
h = H(y), it = pos[h].insert(x).first, it++;
if (it != pos[h].end()) Update_mp(x, *it);
else Update_mp(x, n + 1);
it--; if (it != pos[h].begin()) it--, Update_mp(*it, x);
arr[x] = y;
if (x > 1) Update2(x - 1, abs(y - arr[x - 1]));
if (x < n) Update2(x, abs(arr[x + 1] - y));
}
else
{
++cnt;
if (x > y) swap(x, y);
IN(k), k ^= tot; if (x == y) {puts("Yes"), tot++; continue;}
tmp = Query1(x, y, 1, n, 1), g = Query2(x, y - 1, 1, n - 1, 1);
if (!k)
{
if (tmp.x == tmp.y) puts("Yes"), tot++;
else puts("No");
}
else if (g != k || tmp.o <= y) puts("No");
else if (tmp.y != (LL)(tmp.x) + 1ll * (y - x) * k) puts("No");
else if ((tmp.z << 1) != 1ll * (tmp.x + tmp.y) * (y - x + 1)) puts("No");
else puts("Yes"), tot++;
}
}
return 0;
}
2 条评论
XZY · 2018年7月31日 12:16 下午
评论邮件测试
XZYQvQ · 2018年7月31日 12:33 下午
mmp