Codeforces 627B Factory Repairs(树状数组)

Binary Indexed Tree

Posted by Scalpel on March 6, 2016

题目链接

题意:

一个工厂需要生产一些木材,每天可以生产a个,但是因为一些机器坏了,所以一天只能生产b个,可以选择某一天开始修复机器,修好需要k天,并且这段时间不能再生产,之后会恢复到产量a。在n天中,工厂会接一些订单,每个订单需要一个木材并且在当天生产完成。然后给出q个操作,有两种格式:
表示在第di天新增了个订单;
表示选择在第pi天修复机器。
输出对每个,最多可以满足总共多少订单。注意:修复只能修一次,相当于一次独立的查询

思路:

可以利用树状数组来维护修复前后的订单量,每增加订单,就对执行更新操作,因为修复前后每天的生产量不同,修复前最大为a,修复后最大为b,所以要维护两个不同的订单量,并且每次增加订单后,当天的生产量不能超过最大的生产量,所以更新时不能一直增加,用记录当天累积的订单量,用新增后当天的订单量和最大生产量的较小值,减去增加前的订单量和最大生产量的较小值来更新,即可保证维护的每天的订单量不会超过最大的生产量。最后输出这两个最大产量不同的区间和的和即可(注意利用树状数组求区间和时的端点)。

#include <iostream>
#include <algorithm>

using namespace std;

#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
const int INF = 0x3f3f3f3f;
const int MAXN = 200010;

int tree[2][MAXN];

int lowbit(int x)
{
    return x & (-x);
}
void update(int x, int add, int type)
{
    while (x <= MAXN)
    {
        tree[type][x] += add;
        x += lowbit(x);
    }
}
int sum(int x, int type)
{
    int s = 0;
    while (x)
    {
        s += tree[type][x];
        x -= lowbit(x);
    }
    return s;
}
int order[MAXN];
int main() 
{
    int n, k, a, b, q;
    cin >> n >> k >> a >> b >> q;
    for (int i = 0; i < q; ++i)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int day, num;
            cin >> day >> num;
            int previous = order[day];
            order[day] += num;
            update(day, min(b, order[day]) - min(b, previous), 0);
            update(day, min(a, order[day]) - min(a, previous), 1);
        }
        else
        {
            int p;
            cin >> p;
            cout << sum(p - 1, 0) + (sum(n, 1) - sum(p + k - 1, 1)) << endl;
        }
    }
    return 0;
}