# codechef QCHEF(不删除莫队)

## 题意

\(max |x − y| : L_i ≤ x, y ≤ R_i and A_x = A_y\)

## Sol

```#include<bits/stdc++.h>

const int MAXN = 1e5 + 10, INF = 1e9 + 7;
using namespace std;
template<typename A, typename B> inline bool chmax(A &x, B y) {
if(y > x) {x = y; return 1;}
else return 0;
}
template<typename A, typename B> inline bool chmin(A &x, B y) {
if(y < x) {x = y; return 1;}
else return 0;
}
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, K, M, a[MAXN], l[MAXN], r[MAXN], tl[MAXN], tr[MAXN], belong[MAXN], block, cnt, ans[MAXN];
struct query {
int l, r, id;
bool operator < (const query &rhs) const {
return belong[l] == belong[rhs.l] ? r < rhs.r : belong[l] < belong[rhs.l];
}
};
vector<query> q[MAXN];
int solve(int l, int r) {
for(int i = l; i <= r; i++) tl[a[i]] = INF, tr[a[i]] = 0;
int ans = 0;
for(int i = l; i <= r; i++) {
int x = a[i];
chmin(tl[x], i), chmax(tr[x], i);
chmax(ans, tr[x] - tl[x]);
}
return ans;
}
int update(int x) {
chmax(tr[a[x]], x);
chmin(tl[a[x]], x);
return tr[a[x]] - tl[a[x]];
}
int update2(int x) {
int v = a[x];
chmax(r[v], x);
chmin(l[v], x);
return max(tr[v] - l[v], r[v] - l[v]);
}
void LxlDuLiu(vector<query> v, int id) {
int base = id * block, ll = base, rr = ll - 1, pre = 0, now = 0;
memset(tr, 0, sizeof(tr)); memset(r, 0, sizeof(r));
memset(tl, 0x3f, sizeof(tl)); memset(l, 0x3f, sizeof(l));

for(auto &x : v) {
//memset(l, 0x3f, sizeof(l)); memset(r, 0, sizeof(r));
while(rr < x.r) chmax(now, update(++rr));
pre = now;
while(ll > x.l) chmax(now, update2(--ll));
chmax(ans[x.id], now);
while(ll < base) r[a[ll]] = 0, l[a[ll]] = INF, ll++;
now = pre;
}
}
int main() {
//  freopen("a.in", "r", stdin);
//freopen("b.out", "w", stdout);

for(int i = 1; i <= N; i++) a[i] = read(), belong[i] = (i - 1) / block + 1, chmax(mx, belong[i]);
for(int i = 1; i <= M; i++) {
if(belong[l] == belong[r]) ans[i] = solve(l, r);
else q[belong[l]].push_back({l, r, i});
}
for(int i = 1; i <= mx; i++) sort(q[i].begin(), q[i].end());
for(int i = 1; i <= mx; i++)
LxlDuLiu(q[i], i);
for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);

return 0;
}```

0 条评论

• ### P1018 乘积最大

题目描述 今年是国际数学联盟确定的“2000――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智...

• ### loj#6073. 「2017 山东一轮集训 Day5」距离(树链剖分 主席树)

首先对询问差分一下，我们就只需要统计\(u, v, lca(u, v), fa[lca(u, v)]\)到根的路径的贡献。

• ### 【校赛小分队之我们有个女生】训练赛1

校赛小分队之我们有个女生队——这是我、ljh学长、zk大神组的队，我取得闪亮亮的队名！

• ### BZOJ4269: 再见Xor(线性基)

给定N个数，你可以在这些数中任意选一些数出来，每个数可以选任意多次，试求出你能选出的数的异或和的最大值和严格次大值。

• ### 挑战程序竞赛系列（30）：3.4矩阵的幂

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### loj#6073. 「2017 山东一轮集训 Day5」距离(树链剖分 主席树)

首先对询问差分一下，我们就只需要统计\(u, v, lca(u, v), fa[lca(u, v)]\)到根的路径的贡献。

• ### 数据结构之图论（续）

在一个无向图G中，若将某个节点v去除之后后G所包含的连通域增多，则v称作切割节点（cut vertex或关节点（articulation point）。如果一个...

• ### ex_gcd(个人模版)

ex_gcd： 1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 in...

• ### 最大公约数和最小公倍数

辗转相除法（欧几里得算法）算是求最大公约数最简单高效的算法了，这几行代码用最简洁的方式写了这个算法，值得牢牢记住：