• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

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

admin

11月 28, 2021

前置芝士

  • 线段树

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<<"
";
        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
", ans[i]);
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。