上海教育网站前置审批,科技网站设计,信融网站建设网站开发,如何自己建站网站制作这一题#xff0c;虽说在洛谷标的是模板题#xff0c;但可能没有“历史研究”那一题更加模板。 这一题相对于回滚莫队的模板题#xff0c;可能在回滚的处理上稍微复杂了一点。对于回滚莫队就不多解释了#xff0c;可以看一下 回滚莫队模板题 这一篇博客#xff0c;稍微简单… 这一题虽说在洛谷标的是模板题但可能没有“历史研究”那一题更加模板。 这一题相对于回滚莫队的模板题可能在回滚的处理上稍微复杂了一点。对于回滚莫队就不多解释了可以看一下 回滚莫队模板题 这一篇博客稍微简单的解释了一下。 当整个询问区间都在一个块儿内的时候只需要按顺序暴力解决即可处理完之后把状态清空。 当整个询问区间不在一个块儿的时候按照回滚莫队的思路按顺序向右更新区间状态。暴力处理当前区间。问题就是按顺序向右更新只需要记录每个颜色第一次出现的位置即可就能求出来最大间距。但是从中间位置向左暴力处理当前块儿的时候会发现之前的条件不足以找到最大间距所以在之前的时候需要记录一下每个颜色最右边的位置即可。然后把结果记录回滚状态。 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;stackint 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;
}
