目录

• 前置芝士
• Description
• Solution
• Code

前置芝士

• 线段树

Description

简述题意：

给你一段序列 \(a\)，要求支持下面 \(4\) 种操作，设操作完后的序列为 \(c\)，输出操作完后的序列 \(c\)。
1、全局加 \(x\)；
2、全局减 \(x\)；
3、全局乘 \(x\)；
4、全局加上该位置的起始值乘 \(x\)；
还有一个限制值域 \([L,R]\)，如果某个元素操作完后值 \(>R\)，将该元素值变为 \(R\)，如果 \(<L\)，变为 \(L\)。

Solution

四个操作都挺好说，但加上值域限制后就……

发现对原序列排序不会造成影响。

我们将其从小到大排序。
并且我们发现，不论执行那个操作，排序后序列每个元素之间的大小关系仍然是不变的。

所以每次操作后，大于 \(R\) 或者小于 \(L\) 的元素只会聚集在左右端点，对他们进行区间覆盖操作即可。

这里提供一个操作的小 trick，我们设一个更新函数 \(f(p, k_1, k_2, k_3)\) 表示 \(c_i = c_i * k_1 + a_i * k_2 + k_3\)。

更新的时候可以方便的对应五个操作（包含区间覆盖）

• 全局加减，\(f(p,1,0,x)\)；
• 全局乘，\(f(p,x,0,0)\)；
• 全局加起始值的 \(x\) 倍，\(f(p,1,x,0)\)；
• 区间覆盖，\(f(p,0,0,L/R)\)。

时间复杂度 \(O(n \log n)\)。

Code

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

struct node {
    int opt, val;
}q[MAXN];

struct Node {
    int val, bh;
    bool operator < (const Node &b) const { return val < b.val; }
}a[MAXN];

int n, m, limL, limR;
int ans[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

namespace Seg {
    #define lson i << 1
    #define rson i << 1 | 1
    struct Tree {
        int l, r, min, max, lazy1, lazy2, lazy3;
    }tree[MAXN << 2];
    void Push_up(int i) {
        tree[i].max = tree[rson].max;
        tree[i].min = tree[lson].min;
    }
    void Push_now(int i, int k1, int k2, int k3) {
        tree[i].lazy1 = tree[i].lazy1 * k1;
        tree[i].lazy2 = tree[i].lazy2 * k1 + k2;
        tree[i].lazy3 = tree[i].lazy3 * k1 + k3;
        tree[i].max = tree[i].max * k1 + a[tree[i].r].val * k2 + k3;
        tree[i].min = tree[i].min * k1 + a[tree[i].l].val * k2 + k3;
        return ;
    }
    void Push_down(int i) {
        Push_now(lson, tree[i].lazy1, tree[i].lazy2, tree[i].lazy3);
        Push_now(rson, tree[i].lazy1, tree[i].lazy2, tree[i].lazy3);
        tree[i].lazy1 = 1, tree[i].lazy2 = tree[i].lazy3 = 0;
    }
    void Build(int i, int l, int r) {
        tree[i].l = l, tree[i].r = r, tree[i].lazy1 = 1, tree[i].lazy2 = tree[i].lazy3 = 0;
        if(l == r) { tree[i].max = tree[i].min = a[l].val; return ; }
        int mid = (l + r) >> 1;
        Build(lson, l, mid), Build(rson, mid + 1, r);
        Push_up(i);
    }
    void Modify1(int i, int l, int r) {
        if(l == r) { Push_now(i, 0, 0, limL); return ; }
        Push_down(i);
        int mid = (l + r) >> 1;
        if(tree[rson].min < limL) Push_now(lson, 0, 0, limL), Modify1(rson, mid + 1, r);
        else Modify1(lson, l, mid);
        Push_up(i);
    }
    void Modify2(int i, int l, int r) {
        if(l == r) { Push_now(i, 0, 0, limR); return ; }
        Push_down(i);
        int mid = (l + r) >> 1;
        if(tree[lson].max > limR) Push_now(rson, 0, 0, limR), Modify2(lson, l, mid);
        else Modify2(rson, mid + 1, r);
        Push_up(i);
    }
    void Query(int i, int l, int r) {
        if(l == r) { ans[a[l].bh] = tree[i].max; return ; }
        Push_down(i);
        int mid = (l + r) >> 1;
        Query(lson, l, mid), Query(rson, mid + 1, r);
    }
}

signed main()
{   
    n = read(), limL = read(), limR = read();
    for(int i = 1; i <= n; ++i) {
        char opt; cin >> opt;
        if(opt == '+') q[i].opt = 1;
        else if(opt == '-') q[i].opt = 2;
        else if(opt == '*') q[i].opt = 3;
        else q[i].opt = 4;
        q[i].val = read();
    }
    m = read();
    for(int i = 1; i <= m; ++i) a[i].val = read(), a[i].bh = i;
    sort(a + 1, a + m + 1);
    Seg::Build(1, 1, m);
    for(int i = 1; i <= n; ++i) {
//        cout<<Seg::tree[1].max<<" "<<Seg::tree[1].min<<"\n";
        if(q[i].opt == 1) Seg::Push_now(1, 1, 0, q[i].val);
        else if(q[i].opt == 2) Seg::Push_now(1, 1, 0, -q[i].val);
        else if(q[i].opt == 3) Seg::Push_now(1, q[i].val, 0, 0);
        else Seg::Push_now(1, 1, q[i].val, 0);
        if(Seg::tree[1].min < limL) Seg::Modify1(1, 1, m);
        if(Seg::tree[1].max > limR) Seg::Modify2(1, 1, m);
    }
    Seg::Query(1, 1, m);
    for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
    return 0;
}