BZOJ3878 [AHOI2014]奇怪的计算器

2015.03.04 16:35 Wed| 8 visits oi_2015| 2015_刷题日常| Text

Solution

对于这四个运算操作,显然可以直接利用线段树通过鼓捣根节点来维护。每一次操作后在线段树上找到溢出的区间,将其上的乘法标记设为 0,加法标记设为边界数值。这样便可以在 $\mathcal O(N\log N)$ 的时间内完成询问。详见代码。

由于下传标记的时候可能会不小心越界,我开了线段树八倍空间……

代码长度终于能看得过去了哈~我相信我的代码比较正常向 →_→

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define Q 800005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, m;
long long llimit, rlimit, a[Q], b[Q], c[Q], ans[N], mint[Q], maxt[Q];
pair<long long, int> opt[N], num[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void modify1(int pos, long long x)
{
    a[pos] += x;
    mint[pos] += x; maxt[pos] += x;
}

inline void modify2(int pos, long long x)
{
    a[pos] *= x; b[pos] *= x; c[pos] *= x;
    mint[pos] *= x; maxt[pos] *= x;
}

inline void modify3(int pos, long long x, int l, int r)
{
    b[pos] += x;
    mint[pos] += num[l].first * x; maxt[pos] += num[r].first * x;
}

void pushdown(int pos, int l, int r)
{
    if (c[pos] != 1)
        modify2(lson, c[pos]), modify2(rson, c[pos]);
    if (a[pos])
        modify1(lson, a[pos]), modify1(rson, a[pos]);
    int mid = (l + r) >> 1;
    if (b[pos])
        modify3(lson, b[pos], l, mid), modify3(rson, b[pos], mid + 1, r);
    a[pos] = b[pos] = 0; c[pos] = 1;
}

void change(int pos, long long x)
{
    a[pos] = x; b[pos] = 0; c[pos] = 0;
    mint[pos] = maxt[pos] = x;
}

void abandonl(int pos, int l, int r)
{
    mint[pos] = max(llimit, mint[pos]);
    maxt[pos] = max(llimit, maxt[pos]);
    pushdown(pos, l, r);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (maxt[lson] < llimit)
        change(lson, llimit), abandonl(rson, mid + 1, r);
    else if (mint[lson] < llimit)
        abandonl(lson, l, mid);
    mint[pos] = max(mint[pos], llimit);
}

void abandonr(int pos, int l, int r)
{
    mint[pos] = min(rlimit, mint[pos]);
    maxt[pos] = min(rlimit, maxt[pos]);
    pushdown(pos, l, r);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (mint[rson] > rlimit)
        change(rson, rlimit), abandonr(lson, l, mid);
    else if (maxt[rson] > rlimit)
        abandonr(rson, mid + 1, r);
    maxt[pos] = min(maxt[pos], rlimit);
}

void build(int pos, int l, int r)
{
    mint[pos] = num[l].first; maxt[pos] = num[r].first;
    a[pos] = 0; b[pos] = 0; c[pos] = 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
}

void getans(int pos, int l, int r)
{
    pushdown(pos, l, r);
    if (l == r) { ans[num[l].second] = mint[pos]; return; }
    int mid = (l + r) >> 1;
    getans(lson, l, mid);
    getans(rson, mid + 1, r);
}

void print(long long a[])
{
    for (int i = 1; i <= 1; ++i)
        cout << a[i] << " \n"[i == 5];
}

int main()
{
    cin >> n >> llimit >> rlimit;
    char str[3];
    for (int x, i = 1; i <= n; ++i)
    {
        scanf("%s", str); x = read();
        switch (str[0])
        {
        case '+' : opt[i] = make_pair(x , 1);   break;
        case '-' : opt[i] = make_pair(-x, 1);   break;
        case '*' : opt[i] = make_pair(x , 2);   break;
        case '@' : opt[i] = make_pair(x , 3);   break;
        }
    }
    cin >> m;
    for (int i = 1; i <= m; ++i)
        num[i] = make_pair(read(), i);
    sort(num + 1, num + m + 1);
    build(1, 1, m);
    for (int i = 1; i <= n; ++i)
    {
        switch (opt[i].second)
        {
        case 1: modify1(1, opt[i].first);   break;
        case 2: modify2(1, opt[i].first);   break;
        case 3: modify3(1, opt[i].first, 1, m); break;
        }
        abandonl(1, 1, m); abandonr(1, 1, m);
    }
    getans(1, 1, m);
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);
}