LG 题解 P4041 [AHOI2014/JSOI2014]奇怪的计算器

• 前置芝士
• Description
• Solution
• Code

前置芝士

• 线段树

Description

简述题意：

给你一段序列 \(a\)，要求支持下面 \(4\) 种操作，设操作完后的序列为 \(c\)，输出操作完后的序列 \(c\)。
1、全局加 \(x\)；
2、全局减 \(x\)；
3、全局乘 \(x\)；
4、全局加上该位置的起始值乘 \(x\)；
还有一个限制值域 \([L,R]\)，如果某个元素操作完后值 \(>R\)，将该元素值变为 \(R\)，如果 \(，变为 \(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
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"<> 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< 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;
}