记录编号	357280	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.927 s
提交时间	2016-12-10 10:20:24	内存使用	27.25 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
using namespace std;
//%%%
namespace IO
{
    char buf[1<<18], *fs, *ft;
    inline char readc()
    {
        return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin), fs==ft))?0:*fs++;
    }
    inline int fast_read()
    {
        char c = readc();
        int r = 0;
        bool sig = false;
        while(c > '9' || c < '0')
        {
            if(c == '-')sig = true;
            c = readc();
        }
        while(c >= '0' && c <= '9')
        {
            r = (r<<3)+(r<<1)+(c^0x30);
            c = readc();
        }
        return sig?-r:r;
    }
}using IO::fast_read;
#define MAXN 500001
typedef long long LL;
struct FenwickTree
{
    LL S[MAXN];
    int N;
    void set_N(int n)
    {
        N = n;
    }
    void add(int x, int v)
    {
        for(; x <= N; x += x&-x)S[x] += v;
    }
    LL query(int x)
    {
        LL r = 0;
        for(; x; x -= x&-x)
            r += S[x];
        return r;
    }
}fwt;
struct node
{
    int id, x, y, v, t;
    bool operator<(const node &od)const
    {
        if(x == od.x && y == od.y)return t < od.t;
        if(x == od.x)return y < od.y;
        return x < od.x;
    }
}q[MAXN], tmp[MAXN];
LL ans[MAXN];
void merge(int l, int r)
{
    if(l == r)return;
    int m = (l+r)>>1;
    for(int i = l; i <= r; i++)
    {
        if(q[i].id <= m && !q[i].t)  //前半段的修改操作
            fwt.add(q[i].y, q[i].v);
        if(q[i].id > m && q[i].t)
            ans[q[i].t] += fwt.query(q[i].y)*q[i].v;   //后半段的查询操作
    }
    for(int i = l; i <= r; i++)
        if(q[i].id <= m && !q[i].t)
            fwt.add(q[i].y, -q[i].v);   //消除操作的影响
    int j = l, k = m+1;  //merge_sort
    for(int i = l; i <= r; i++)
    {
        if(q[i].id <= m)tmp[j++] = q[i];
        else tmp[k++] = q[i];
    }
    for(int i = l; i <= r; i++)q[i] = tmp[i];
    merge(l, m);
    merge(m+1, r);
}
int cnt = 0;
int qes = 0;
void insert(int x, int y, int v, int t)
{
    q[++cnt] = (node){cnt, x, y, v, t};
}
int W;
int main()
{
    //freopen("test_data.txt", "r", stdin);
    freopen("locust.in", "r", stdin);
    freopen("locust.out", "w", stdout);
    W = fast_read();
    int m = fast_read();
    while(m--)
    {
        int op = fast_read();
        if(op == 1)
        {
            int x = fast_read();
            int y = fast_read();
            int v = fast_read();
            insert(x, y, v, 0);
        }else
        {
            int x1 = fast_read();
            int y1 = fast_read();
            int x2 = fast_read();
            int y2 = fast_read();
            ++qes;
            insert(x1-1, y1-1, 1, qes);
            insert(x1-1, y2, -1, qes);
            insert(x2, y1-1, -1, qes);
            insert(x2, y2, 1, qes);
        }
    }
    fwt.set_N(W);
    sort(q+1, q+cnt+1);
    merge(1, cnt);
    for(int i = 1; i <= qes; i++)
        printf("%lld\n", ans[i]);
    return 0;
}