B. Factory Repairs---cf627B（线段树）

题目链接：http://codeforces.com/problemset/problem/627/B

题意：有一个工厂生产零件，但是机器是不正常的，需要维修，维修时间是 k 天，在维修期间不能生产，如果是正常情况下每天可生产A个零件，不正常情况下也可以生产，但是只能生产B（B<A）件，

现有2个操作，1和2

1 x y 表示第x天分配的工作量是y；

2 x 表示假如在第x天进行维修机器，那么这n天共能生产多少个零件；

现在有q个这样的操作，问当2操作时当前的结果是多少；

由于数据范围比较大，所以不能暴力，用线段树

sum表示当前区间的所有工作量，sum1表示机器正常情况下所能生产的总工作量，sum2是不正常情况下的；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
#define PI 4*atan(1.0)
#define N 210500
#define met(a, b) memset(a, b, sizeof(a))

#define Lson r<<1
#define Rson r<<1|1

struct node
{
    int L, R, sum, sum1, sum2;///sum1是好的情况下，sum2是坏的情况下；
    int Mid(){ return (L+R)/2; }
}a[N*4];

int A, B;

void Build(int r, int L, int R)
{
    a[r].L = L, a[r].R = R;
    a[r].sum = a[r].sum1 = a[r].sum2 = 0;

    if(L == R)return ;

    Build(Lson, L, a[r].Mid());
    Build(Rson, a[r].Mid()+1, R);
}

void Update(int r, int pos, int num)
{
    if(a[r].L == a[r].R && a[r].L == pos)
    {
        a[r].sum += num;
        if(a[r].sum >= A)
        {
            a[r].sum1 = A;
            a[r].sum2 = B;
        }
        else if(a[r].sum < A && a[r].sum >= B)
        {
            a[r].sum1 = a[r].sum;
            a[r].sum2 = B;
        }
        else
            a[r].sum1 = a[r].sum2 = a[r].sum;
        return;
    }
    if(pos<=a[r].Mid())
        Update(Lson, pos, num);
    else
        Update(Rson, pos, num);

    a[r].sum = a[Lson].sum + a[Rson].sum;
    a[r].sum1 = a[Lson].sum1 + a[Rson].sum1;
    a[r].sum2 = a[Lson].sum2 + a[Rson].sum2;
}


int Query(int r, int L, int R, int op)
{
    if(L > R) return 0;

    if(a[r].L == L && a[r].R == R)
    {
        if(op == 1)
            return a[r].sum1;
        return a[r].sum2;
    }
    if(R<=a[r].Mid())
        return Query(Lson, L, R, op);
    else if(L>a[r].Mid())
        return Query(Rson, L, R, op);
    else
    {
        int ans1 = Query(Lson, L, a[r].Mid(), op);
        int ans2 = Query(Rson, a[r].Mid()+1, R, op);
        return ans1+ans2;
    }
}

int main()
{
    int n, k, q, op, x, y;
    while(scanf("%d %d %d %d %d", &n, &k, &A, &B, &q)!=EOF)
    {
        Build(1, 1, n);
        while(q--)
        {
            scanf("%d", &op);
            if(op==1)
            {
                scanf("%d %d", &x, &y);
                Update(1, x, y);
            }
            else
            {
                scanf("%d", &x);

                int ans1 = Query(1, 1, x-1, 0);///0没修好之前的；
                int ans2 = Query(1, x+k, n, 1);///1修好之后的；

                printf("%d
", ans1 + ans2);
            }
        }
    }
    return 0;
}