专栏首页数据结构与算法codechef QCHEF(不删除莫队)

codechef QCHEF(不删除莫队)

题意

题目链接

给出长度为\(n\)的序列,每次询问区间\([l, r]\),要求最大化

\(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;
}
inline int read() {
    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);
    
    N = read(); K = read(); M = read(); block = sqrt(N); int mx = 0;
    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++) {
        int l = read(), r = read();
        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周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智...

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

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

    attack
  • AGC015 C Nuske vs Phantom Thnook(前缀和)

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

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

    饶文津
  • BZOJ4269: 再见Xor(线性基)

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

    attack
  • 挑战程序竞赛系列(30):3.4矩阵的幂

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

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

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

    attack
  • 数据结构之图论(续)

    在一个无向图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...

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

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

    刘开心_1266679

扫码关注云+社区

领取腾讯云代金券