记录编号	505194	评测结果	AAAAAAEEEE
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	60
用户昵称	GKxx	是否通过	未通过
代码语言	C++	运行时间	2.523 s
提交时间	2018-08-11 21:46:51	内存使用	20.14 MiB

#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
 
namespace io
{
#define BUF_SIZE 5000010
    char buf[BUF_SIZE]; int cur = BUF_SIZE; FILE *in = stdin;
    inline char gnc()
    {
        if (cur == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); cur = 0; }
        return buf[cur++];
    }
    template <typename T>
    inline void read(T &dx)
    {
        dx = 0;
        int yc = gnc();
        bool nega = false;
        while (yc < '0' || yc > '9') { nega = (yc == '-' ? true : nega); yc = gnc(); }
        while (yc >= '0' && yc <= '9') { dx = (T)(dx * 10 + yc - '0'); yc = gnc(); }
        if (nega) { dx = -dx; }
    }
    void gc(char &a)
    {
        do a = gnc(); while (!isgraph(a));
    }
    void gss(char *c)
    {
        *c = gnc();
        while (!isgraph(*c)) *c = gnc();
        while (isgraph(*c)) *++c = gnc();
        *c = 0;
    }
}
using io::read;
 
#define npt NULL
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)
 
#ifdef WIN32
#define OUTLL "%I64d"
#else
#define OUTLL "%lld"
#endif
 
inline int lowbit(int x) { return x & -x; }
 
struct Command {
    int q, x, y, x1, y1, x2, y2;
    int a;
};
 
const int maxq = 2e5 + 100;
Command cmd[maxq];
int exes[maxq << 2];
int n, m, tot;
 
struct Node {
    int loc;
    int value, sum;
    Node *ch[2], *fa;
    explicit Node(int l = 0, int v = 0)
        : loc(l), value(v), sum(v), fa(npt) { ch[0] = ch[1] = npt; }
    int isc(int c) const { return fa && fa->ch[c] == this; }
    int isc() const { return fa ? isc(1) : -1; }
};
 
inline void update(Node*& x) {
    x->sum = x->value;
    rep(i, 0, 1) if (x->ch[i])
        x->sum += x->ch[i]->sum;
}
inline void rotate(Node*& x) {
    if (!x->fa) return;
    int d = x->isc();
    Node* f = x->fa;
    if (f->isc() != -1)
        f->fa->ch[f->isc()] = x;
    x->fa = f->fa;
    f->ch[d] = x->ch[d ^ 1];
    if (x->ch[d ^ 1]) x->ch[d ^ 1]->fa = f;
    x->ch[d ^ 1] = f;
    f->fa = x;
    update(f);
    update(x);
}
inline void splay(Node*& x, Node*& root) {
    if (x == root) return;
    Node* p = root->fa;
    while (x->fa != p) {
        Node* f = x->fa;
        if (f->fa == p) rotate(x);
        else {
            if (f->isc() == x->isc())
                rotate(f);
            else rotate(x);
            rotate(x);
        }
    }
    root = x;
}
inline void insertSplay(Node*& root, int pos, int val) {
    if (!root) {
        root = new Node(pos, val);
        return;
    }
    Node* curr = root;
    while (0207) {
    	curr->sum += val;
        if (pos == curr->loc) {
            curr->value += val;
            return;
        }
        int d = (pos > curr->loc);
        if (curr->ch[d]) curr = curr->ch[d];
        else {
            curr->ch[d] = new Node(pos, val);
            curr->ch[d]->fa = curr;
            curr = curr->ch[d];
            splay(curr, root);
            return;
        }
    }
}
inline int querySplay(Node* curr, int x) {
    if (!curr) return 0;
    int ret = 0;
    while (curr) {
        if (x < curr->loc) curr = curr->ch[0];
        else {
            if (curr->ch[0])
                ret += curr->ch[0]->sum + curr->value;
            else
                ret += curr->value;
            curr = curr->ch[1];
        }
    }
    return ret;
}
 
Node *root[maxq << 2];
 
inline void addBit(int x, int y, int v) {
    for (; x <= tot; x += lowbit(x)) insertSplay(root[x], y, v);
}
inline int queryBit(int x, int y) {
    int ans = 0;
    for (; x; x -= lowbit(x)) ans += querySplay(root[x], y);
    return ans;
}
 
int main() {
    freopen("mokia.in", "r", stdin);
    freopen("mokia.out", "w", stdout);
    { int zero; read(zero); }
    read(n);
    int q; read(q);
    while (q != 3) {
    	cmd[++m].q = q;
        if (q == 1) {
            read(cmd[m].x); read(cmd[m].y); read(cmd[m].a);
            exes[++tot] = cmd[m].x;
        } else {
            read(cmd[m].x1); read(cmd[m].y1); read(cmd[m].x2); read(cmd[m].y2);
            exes[++tot] = cmd[m].x1;
            exes[++tot] = cmd[m].x2;
        }
        read(q);
    }
    std::sort(exes + 1, exes + tot + 1);
    tot = std::unique(exes + 1, exes + tot + 1) - (exes + 1);
    rep(i, 1, m)
    	if (cmd[i].q == 1) {
    		cmd[i].x = std::lower_bound(exes + 1, exes + tot + 1, cmd[i].x) - exes;
    		addBit(cmd[i].x, cmd[i].y, cmd[i].a);
        } else {
            cmd[i].x1 = std::lower_bound(exes + 1, exes + tot + 1, cmd[i].x1) - exes;
            cmd[i].x2 = std::lower_bound(exes + 1, exes + tot + 1, cmd[i].x2) - exes;
            int w1 = queryBit(cmd[i].x2, cmd[i].y2);
            int w2 = queryBit(cmd[i].x2, cmd[i].y1 - 1);
            int w3 = queryBit(cmd[i].x1 - 1, cmd[i].y2);
            int w4 = queryBit(cmd[i].x1 - 1, cmd[i].y1 - 1);
            printf("%d\n", w1 - w2 - w3 + w4);
        }
    return 0;
}