离线线段树 SPOJ - GSS2【Can you answer these queries II】

墨蓝 2021-11-22 15:04 207阅读 0赞

# 离线线段树 SPOJ - GSS2【Can you answer these queries II】 #

[https://cn.vjudge.net/contest/304248\#problem/H][https_cn.vjudge.net_contest_304248_problem_H]

## 题意 ##

给定 n 个整数（有负数）和 m 次操作，令 \\(q(l,r)\\) 为 l 到 r 之间所有数去重后的和，每次询问 \\(max(q(x,y)\[li \\leq x \\leq y \\leq ri\])\\) 。

## 分析 ##

我实在不知道怎么用莫队做，理论上是可以，但怎么 add() 和 del() 我写不出来。

然后我就去搜了题解，然后没有一个用莫队的，我惊了...

不过和莫队有共通点（离线），边更新边查询。

**需要两个懒惰标记，第一个用来正常的区间更新操作的；而第二个是用来更新最优解的，比如一个区间中下传了-5，但是在他的左儿子中有个懒惰标记为5，对于他的左儿子来说，直接加5才是最优解。**

也算是又学了一招（-……-）

## 代码 ##

#include <map>
    #include <set>
    #include <list>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <stack>
    #include <queue>
    #include <bitset>
    #include <cctype>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <cstdlib>
    #include <cstring>
    #include <fstream>
    #include <iomanip>
    #include <numeric>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const double PI = acos(-1.0);
    const double eps = 1e-6;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    
    const int maxn = 1e5+5;
    const int nn = 1e5;
    
    int n, m;
    ll a[maxn];
    int vis[maxn<<1];   // 负数要翻正（*2），用来记录上一次出现值x的位置
    ll res[maxn];
    
    struct Tree {
        ll sum, lazy, ans, prelazy; 
        // sum 记录区间去重和的最大后缀和
        // lazy 记录下传的值
        // ans 记录区间去重和的最大值
        // prelazy 记录下传的最大值
    }tree[maxn<<2];
    
    struct node{
        int l, r, id;
        bool operator < (const node &a) const {
            return r < a.r;     // 按区间右端点进行离线排序
        }
    }Q[maxn];
    
    void pushup(int rt) {   // 常规更新
        tree[rt].sum = max(tree[2*rt].sum, tree[2*rt+1].sum);
        tree[rt].ans = max(tree[2*rt].ans, tree[2*rt+1].ans);
    }
    
    void pushdown(int rt) { // 懒惰标记更新
        if(tree[rt].lazy || tree[rt].prelazy) { // 根据父节点更新子节点的各项值
            tree[2*rt].prelazy = max(tree[2*rt].prelazy, tree[2*rt].lazy + tree[rt].prelazy);
            tree[2*rt+1].prelazy = max(tree[2*rt+1].prelazy, tree[2*rt+1].lazy + tree[rt].prelazy);
            
            tree[2*rt].ans = max(tree[2*rt].ans, tree[2*rt].sum + tree[rt].prelazy);
            tree[2*rt+1].ans = max(tree[2*rt+1].ans, tree[2*rt+1].sum + tree[rt].prelazy);
            
            tree[2*rt].lazy += tree[rt].lazy;
            tree[2*rt+1].lazy += tree[rt].lazy;
            
            tree[2*rt].sum += tree[rt].lazy;
            tree[2*rt+1].sum += tree[rt].lazy;
        
            tree[rt].lazy = tree[rt].prelazy = 0;   // 标记还原
        }
    }
    
    void build(int l, int r, int rt) {
        tree[rt].sum = tree[rt].lazy = tree[rt].prelazy = tree[rt].ans = 0;
        if(l == r) {
            return ;
        }
        int mid = (l+r) >> 1;
        build(l, mid, 2*rt);
        build(mid+1, r, 2*rt+1);
        pushup(rt);
    }
    
    void update(int L, int R, int l, int r, int rt, ll val) {
        if(L <= l && r <= R) {
            tree[rt].sum += val;
            tree[rt].lazy += val;   // 区间更新需要更新懒惰标记
            tree[rt].ans = max(tree[rt].ans, tree[rt].sum);
            tree[rt].prelazy = max(tree[rt].prelazy, tree[rt].lazy);    // 取最大
            return ;
        }
        pushdown(rt);
        int mid = (l+r) >> 1;
        if(L <= mid) {
            update(L, R, l, mid, 2*rt, val);
        }
        if(R > mid) {
            update(L, R, mid+1, r, 2*rt+1, val);
        }
        pushup(rt);
    }
    
    ll query(int L, int R, int l, int r, int rt) {
        if(L <= l && r <= R) {
            return tree[rt].ans;
        }
        pushdown(rt);
        ll ans = (-1ll)*maxn*maxn;  // 因为 ans 有可能为负数（不过应该是没有影响的，0 也可以）
        int mid = (l+r) >> 1;
        if(L <= mid) {
            ans = max(ans, query(L, R, l, mid, 2*rt));
        }
        if(R > mid) {
            ans = max(ans, query(L, R, mid+1, r, 2*rt+1));
        }
        return ans;
    }
    
    int main() {
        // fopen("in.txt", "r", stdin);
        // fopen("out.txt", "w", stdout);
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        build(1, n, 1);
        scanf("%d", &m);
        for(int i = 1; i <= m; i++) {
            scanf("%d%d", &Q[i].l, &Q[i].r);
            Q[i].id = i;
        }
        sort(Q+1, Q+1+m);
        int cnt = 1; 
        for(int i = 1; i <= n; i++) {
            update(vis[a[i]+nn]+1, i, 1, n, 1, a[i]);   
            // L = 上一次出现该值的位置 + 1
            // R = 当前位置 i
            vis[a[i]+nn] = i;
            while(cnt <= m && Q[cnt].r == i) {
                // 当 Q[cnt].r == i 时，后续操作与当前查询无关，直接查询
                res[Q[cnt].id] = query(Q[cnt].l, Q[cnt].r, 1, n, 1);
                cnt ++;
            }
        }
        for(int i = 1; i <= m; i++) {
            printf("%lld\n", res[i]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Decray/p/10952508.html

[https_cn.vjudge.net_contest_304248_problem_H]: https://cn.vjudge.net/contest/304248#problem/H