CF390-E. Inna and Large Sweet Matrix（区间更新＋区间查询）

题意很好理解，不说了

题解就是每次把值压缩成一维，比如x上，这样就可以求出任意宽度的整个竖条的和。

如这张图，求的是s5-(s1+s3+s7+s9)

因为可以求出一整竖条和一整横条，我们可以求出是s2+s5+s8 也可以求出s4+s5+s6 当然也很容易求出总面积S

那么S-(s2+s5+s8)-(s4+s5+s6) = s1+s3+s7+s9-s5

对，答案已经出来了，很简单。

以后看到这种求解公式十分奇怪的题，就要算一算是不是能构造出很简单的公式。

注意这题用cin cout 会超时！因为codeforce是单样例，所以都忘了这点，t了好多次……T^T

区间更新＋区间查询，线段树＋lazy操作 （514ms

#include <stdio.h>

typedef long long ll;

const int N = ;

ll tx[N<<], ty[N<<], fx[N<<], fy[N<<];

int yl, yr, yv;

#define lson (o<<1)

#define rson ((o<<1)+1)

void pushdown(ll tr[], ll fg[], int o, int l, int r)

{

    if (fg[o]) {

        fg[lson] += fg[o];

        fg[rson] += fg[o];

        int m = (l+r) >> ;

        tr[lson] += fg[o] * (m-l+);

        tr[rson] += fg[o] * (r-m);

        fg[o] = ;

    }

}

void add(ll tr[], ll fg[], int o, int l, int r)

{

    if (l == r) {

        tr[o] += yv;

        return ;

    }

    if (yl <= l && yr >= r) {

        tr[o] += (ll)yv * (r-l+);

        fg[o] += yv;

        return ;

    }

    pushdown(tr, fg, o, l, r);

    int m = (l+r) >> ;

    if (yl <= m) add(tr, fg, lson, l, m);

    if (yr > m) add(tr, fg, rson, m+, r);

    tr[o] = tr[lson] + tr[rson];

}

ll query(ll tr[], ll fg[], int o, int l, int r)

{

    if (l >= yl && r <= yr) {

        return tr[o];

    }

    pushdown(tr, fg, o, l, r);

    int m = (l+r) >> ;

    ll ans = ;

    if (m >= yl) ans += query(tr, fg, o<<, l, m);

    if (m < yr) ans += query(tr, fg, (o<<)+, m+, r);

    return ans;

}

int main()

{

    int n, m, w;

    scanf("%d%d%d", &n, &m, &w);

    int op;

    int x1, x2, y1, y2;

    ll v;

    ll tot, ans;

    while (w--) {

        scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);

        if (op) {

            yl = , yr = n;

            tot = query(tx, fx, , , n);

            ans = ;

            yl = x1, yr = x2;

            ans += query(tx, fx, , , n);

            yl = y1, yr = y2;

            ans += query(ty, fy, , , m);

            printf("%lld\n", ans-tot);

        } else {

            scanf("%lld", &v);

            yl = x1, yr = x2, yv = v*(y2-y1+);

            add(tx, fx, , , n);

            yl = y1, yr = y2, yv = v*(x2-x1+);

            add(ty, fy, , , m);

        }

    }

    return ;

}

顺便学习了一下树状数组的区间操作（202ms 时间空间都优于线段树

#include <stdio.h>

typedef long long ll;

const int MAXN = ;

int lowbit(int x) { return x&-x; }

struct tree_array {

    struct tree_array_single {

        int N;

        ll arr[MAXN];

        void add(int x, ll v) { while(x <= N) arr[x] += v, x += lowbit(x); }

        ll sum(int x) { ll sum = ; while(x) sum+=arr[x], x-=lowbit(x); return sum; }

    } T1, T2;

    void add(int x, ll v) { T1.add(x, v); T2.add(x, x*v); }

    void update(int L, int R, ll v) { add(L, v); add(R+, -v); }

    ll sum(int x) { return (x+)*T1.sum(x)-T2.sum(x); }

    ll query(int L,int R) { return sum(R)-sum(L-); }

} tx, ty;

int main()

{

    //freopen("in.txt", "r", stdin);

    int n, m, w;

    scanf("%d%d%d", &n, &m, &w);

    int op;

    int x1, x2, y1, y2;

    ll v;

    tx.T1.N = tx.T2.N = n;

    ty.T1.N = ty.T2.N = m;

    ll tot = ;

    while (w--) {

        scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);

        if (op) {

            ll ans = tx.query(x1, x2) + ty.query(y1, y2);

            printf("%lld\n", ans-tot);

        } else {

            scanf("%lld", &v);

            tot += (y2-y1+)*(x2-x1+)*v;

            tx.update(x1, x2, v*(y2-y1+));

            ty.update(y1, y2, v*(x2-x1+));

        }

    }

    return ;

}