2015年4月

tagged-zkw.
稍后做一个教程。

namespace DEL
{
    const int INF = 1e9, maxn = 1 << 25;
    struct info
    {
        int Max;
        info(int x = -INF) : Max(x){}
    } A[maxn];
}
#include <cstdio>
#include <algorithm>
using namespace std;
using namespace DEL;
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        int t;
        for(t = 1; t <= n + 3; t <<= 1);
        for(int i = t + 1; i < t + 1 + n; i++)
        {
            int a;
            scanf("%d", &a);
            A[i] = info(a);
        }
        for(int i = t - 1; i > 0; i--)
            A[i].Max = max(A[i * 2].Max, A[i * 2 + 1].Max);
        while(m--)
        {
            static char c[maxn];int x, y;
            scanf("%s%d%d", &c, &x, &y);
            if(c[0] == 'Q')
            {
                int ans = 0;
                for(x += t - 1, y += t + 1; x ^ y ^ 1; x >>= 1, y >>= 1)
                {
                    if(~x & 1)
                        ans = max(ans, A[x ^ 1].Max);
                    if(y & 1)
                        ans = max(ans, A[y ^ 1].Max);
                }
                printf("%d\n", ans);
            }
            else
            {
                for(A[x += t] = info(y), x >>= 1; x > 0; x >>= 1)
                    A[x].Max = max(A[x * 2].Max, A[x * 2 + 1].Max);
            }
        }
    }
    return 0;
}

namespace DEL
{
    template<int max>
    class FenwickTree
    {
    private:
        int n;
        int a[max][max];
    public:
        void init(int _n)
        {
            n = _n;
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    a[i][j] = 0;
        }
        void update(int x, int y, int v)
        {
            for(int i = x; i <= n; i += (i & -i))
                for(int j = y; j <= n; j += (j & -j))
                    a[i][j] += v;
        }
        int query(int x, int y)
        {
            int ans = 0;
            for(int i = x; i >= 1; i -= (i & -i))
                for(int j = y; j >= 1; j -= (j & -j))
                    ans += a[i][j];
            return ans;
        }
        int work(int l, int b, int r, int t)
        {
            return query(r, t) - query(l - 1, t) - query(r, b - 1) + query(l - 1, b - 1);
        }
    };
}
#include <cstdio>
using namespace std;
DEL::FenwickTree<1025> ft;
int main()
{
    int op;
    while(scanf("%d", &op))
    {
        if(op == 0)
        {
            int n;
            scanf("%d", &n);
            ft.init(n);
        }
        else if(op == 1)
        {
            int x, y, a;
            scanf("%d%d%d", &x, &y, &a);
            x++, y++;
            ft.update(x, y, a);
        }
        else if(op == 2)
        {
            int l, b, r, t;
            scanf("%d%d%d%d", &l, &b, &r, &t);
            l++, b++, r++, t++;
            printf("%d\n", ft.work(l, b, r, t));
        }
    }
    return 0;
}