51nod1463 找朋友

[传送门]

写的时候一直没有想到离线解法，反而想到两个比较有趣的解法。
一是分块，$f[i][j]$表示第$i$块块首元素到第$j$个元素之间满足条件的最大值(即对$B_l + B_r \in K$的$A_l + A_r$的最大值)。这个可以$O(nm\sqrt n)$预处理，查询就$l$属于的块$p$得到$f[p+1][r]$和暴力$l$到$min(r,R[p])$的最大值合并一下，但是不知道为啥狂T QAQ，51nod好像没开O2，开O2第一组T的数据跑了1.4s，不开O2跑了5s，难道真是复杂度不对？还是写丑了？很难受。
第二个想法是从“画”样例得来的
对于每一个数$B_i$，可以预处理出$B_j$满足$B_i + a = B_j\left(a \in K\right)$的位置以及对应的$A$之和(只需要往大的方向找即可)
比如样例的
$A$: 1 2 3 4
$B$: 3 2 1 4
$i = 1$：0 0 0 5
$i = 2$：3 0 0 0
$i = 3$：0 5 0 7
$i = 4$：0 0 0 0
那么我要查询$\left[l,r\right]$之间满足条件的最大值，相当于在这个二维矩阵里$RMQ$，比如样例查询$\left[1, 4\right]$就是在矩阵$(1,1)$$(4,4)$里查询其最大值得到$7$，另一个样例在$(2,2)$$(3,3)$里查询得到$5$，那么就可以动态开点二维线段树$RMQ$，复杂度应该是$O(nlog^2n)$。至此，我已经不想写了。
看了题解发现可以离线加扫描线处理，就是把所有询问按右端点排序，新加入一个点就枚举这个点所有符合的元素的位置，如果位置在当前扫描线之前，就可以把它们的$A$之和加到对应位置上，如果比原位置的值大则更新。而扫描线用来扫右端点，未到下一个右端点则更新，到了直接查询当前线段树上的$[l,r]$区间。
其实这个本质就是二维矩阵$RMQ$，因为不带修改，那么可以通过扫描线来减少一维。终于懂了QAQ

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5 + ;

struct Seg {

    #define lp p << 1

    #define rp p << 1 | 1

    ll tree[N << ];

    inline void pushup(int p) {

        tree[p] = max(tree[lp], tree[rp]);

    }

    void update(int p, int l, int r, int pos, ll val) {

        if (l == r) {

            tree[p] = max(tree[p], val);

            return;

        }

        int mid = l + r >> ;

        if (pos <= mid) update(lp, l, mid, pos, val);

        else update(rp, mid + , r, pos, val);

        pushup(p);

    }

    ll query(int p, int l, int r, int x, int y) {

        if (x <= l && y >= r) return tree[p];

        int mid = l + r >> ;

        ll ans = ;

        if (x <= mid) ans = max(ans, query(lp, l, mid, x, y));

        if (y > mid) ans = max(ans, query(rp, mid + , r, x, y));

        return ans;

    }

} seg;

struct Query {

    int l, r, id;

    inline bool operator < (const Query &rhs) const {

        return r < rhs.r;

    }

} query[N];

ll a[N], ans[N];

int b[N], k[N], pos[N];

int main() {

    int n, q, m;

    scanf("%d%d%d", &n, &q, &m);

    for (int i = ; i <= n; i++)

        scanf("%lld", &a[i]);

    for (int i = ; i <= n; i++)

        scanf("%d", &b[i]), pos[b[i]] = i;

    for (int i = ; i <= m; i++)

        scanf("%d", &k[i]);

    for (int i = ; i <= q; i++)

        scanf("%d%d", &query[i].l, &query[i].r), query[i].id = i;

    sort(query + , query +  + q);

    int now = ;

    for (int i = ; i <= q; i++) {

        while (now < query[i].r) {

            now++;

            ll mx = ;

            for (int j = ; j <= m; j++) {

                int temp = b[now] - k[j];

                if (temp >  && temp <= n && pos[temp] < now) seg.update(, , n, pos[temp], a[now] + a[pos[temp]]);

                temp = b[now] + k[j];

                if (temp <= n && temp >  && pos[temp] < now) seg.update(, , n, pos[temp], a[now] + a[pos[temp]]);

            }

        }

        ans[query[i].id] = seg.query(, , n, query[i].l, query[i].r);

    }

    for (int i = ; i <= q; i++)

        printf("%lld\n", ans[i]);

    return ;

}

巴特西

51nod1463 找朋友

最新文章

热门文章