下雪了

HDU1166 – 敌兵布阵(线段树模板)

重新写了一发模板(乖乖地push_up和push_down了……)

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int l;
    int r;
    int sum;
    int lazy;
};

unit tab[50005 << 2];
int num[50005];
int rt;
int cnt;

void pushdown(int x,int l,int r)
{
    if (tab[x].lazy)
    {
        tab[tab[x].l].lazy += tab[x].lazy;
        tab[tab[x].r].lazy += tab[x].lazy;
        tab[tab[x].l].sum += tab[x].lazy * (r - l + 1);//要看情况乘多少,例如取min的话只乘1,总和就要乘上区间长度
        tab[tab[x].r].sum += tab[x].lazy * (r - l + 1);
        tab[x].lazy = 0;
    }
}

void pushup(int x)
{
    tab[x].sum = tab[tab[x].l].sum + tab[tab[x].r].sum;
}

void build(int& x, int l, int r)
{
    x = ++cnt;
    tab[x].lazy = 0;
    if (l == r)
    {
        tab[x].sum = num[l];
        return;
    }
    int m = (l + r) >> 1;
    build(tab[x].l, l, m);
    build(tab[x].r, m + 1, r);
    pushup(x);
}

void update(int x, int L, int R, int l, int r,int value)
{
    if (L <= l && R >= r)
    {
        tab[x].sum += value * (r - l + 1);
        tab[x].lazy += value;
        return;
    }
    pushdown(x, l, r);
    int m = (l + r) >> 1;
    if (L <= m) update(tab[x].l, L, R, l, m, value);
    if (R > m) update(tab[x].r, L, R, m + 1, r, value);
    pushup(x);
}

int check(int x, int L, int R, int l, int r)
{
    if (L <= l && R >= r)
        return tab[x].sum;
    pushdown(x, l, r);
    int m = (l + r) >> 1;
    int sum = 0;
    if (L <= m) sum += check(tab[x].l, L, R, l, m);
    if (R > m) sum += check(tab[x].r, L, R, m + 1, r);
    pushup(x);
    return sum;
}


signed main()
{
    int T;
    cin >> T;
    ffor(c, 1, T)
    {
        cnt = 0;
        int n;
        cin >> n;
        ffor(i, 1, n)
            scanf("%lld", &num[i]);
        build(rt, 1, n);
        printf("Case %lld:\n", c);
        while (true)
        {
            char s[10];
            int x, y;
            scanf("%s", s);
            if (s[0] != 'E')
            {
                scanf("%lld%lld", &x, &y);
                if (s[0] == 'A')
                    update(rt, x, x, 1, n, y);
                else if (s[0] == 'S')
                    update(rt, x, x, 1, n, -y);
                else if (s[0] == 'Q')
                    printf("%lld\n", check(rt, x, y, 1, n));
            }
            else break;
        }
    }
    return 0;
}

 


Add Your Comment

* Indicates Required Field

Your email address will not be published.

*