P5906 【模板】回滚莫队不删除莫队

模板】回滚莫队不删除莫队"/>

P5906 【模板】回滚莫队不删除莫队

        这一题，虽说在洛谷标的是模板题，但可能没有“历史研究”那一题更加模板。

        这一题相对于回滚莫队的模板题，可能在回滚的处理上稍微复杂了一点。对于回滚莫队就不多解释了，可以看一下 回滚莫队模板题 这一篇博客，稍微简单的解释了一下。

        当整个询问区间都在一个块儿内的时候，只需要按顺序暴力解决即可，处理完之后把状态清空。

        当整个询问区间不在一个块儿的时候，按照回滚莫队的思路，按顺序向右更新区间状态。暴力处理当前区间。问题就是按顺序向右更新，只需要记录每个颜色第一次出现的位置即可，就能求出来最大间距。但是从中间位置向左暴力处理当前块儿的时候会发现之前的条件不足以找到最大间距，所以在之前的时候需要记录一下每个颜色最右边的位置即可。然后把结果记录，回滚状态。

int n, m, len;
int o[N], st[N], f[N], sr[N];
struct LSH // 用于离散化处理
{int a, id;
} ls[N];
struct Query // 询问列表
{int l, r, id;
} q[N];inline int get(int a) // 得到块儿号
{return a / len;
}
bool cmp(Query a, Query b) // 排序函数
{int i = get(a.l), j = get(b.l);if(i != j) return i < j;return a.r < b.r;
}
inline void lsh_init() // 离散化处理
{stable_sort(ls, ls + n, [&](LSH a, LSH b){return a.a < b.a;});int pr = -1, s = 0;for(int i = 0; i < n; i ++){if(ls[i].a == pr) o[ls[i].id + 1] = s;else o[ls[i].id + 1] = ++ s;pr = ls[i].a;}
}
inline void add(int a, int& res)
{if(!st[o[a]]) st[o[a]] = a;sr[o[a]] = a;res = max(res, a - st[o[a]]);
}
inline void sovle()
{cin >> n;len = sqrt(n); for(int i = 0; i < n; i ++){int a;cin >> a;ls[i] = {a, i};}lsh_init();cin >> m;for(int i = 0; i < m; i ++){int a, b;cin >> a >> b;q[i] = {a, b, i};}stable_sort(q, q + m, cmp);for(int x = 0; x < m; ){int y = x;while(y < m && get(q[y].l) == get(q[x].l)) y ++;int right = get(q[x].l) * len + len - 1;// 整个区间都在块儿内while(x < y && q[x].r <= right){	int id = q[x].id, l = q[x].l, r = q[x].r, res = 0;for(int i = l; i <= r; i ++) add(i, res);f[id] = res;for(int i = l; i <= r; i ++) st[o[i]] = 0, sr[o[i]] = 0; // 回滚状态，需要把用到的st以及sr回滚状态x ++;}// 不在一个块儿的询问int i = right + 1, j = right, res = 0;stack<int> yi;while(x < y){int id = q[x].id, l = q[x].l, r = q[x].r;while(j < r) add(++ j, res); // 从中间位置向右顺序遍历int backup = res; // 记录res 用于暴力处理之后的回滚while(i > l) // 从中间向左暴力处理{i --;if(!sr[o[i]]) // 如果这个颜色在区间内没出现过{yi.push(o[i]); // 记录一下暴力处理过程中用到的sr，之后全部回滚sr[o[i]] = i; // 记录这个颜色最右边的位置，就是当前位置}res = max(res, sr[o[i]] - i);}while(yi.size()) // 回滚状态{int a = yi.top();sr[a] = 0;yi.pop();}f[id] = res; // 记录答案res = backup; // 回滚res状态x ++;i = right + 1; // 回滚左端点}memset(st, 0, sizeof st); // 清空memset(sr, 0, sizeof sr);}for(int i = 0; i < m; i ++)cout << f[i] << endl;
}