记录编号	353367	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	Drench	是否通过	通过
代码语言	C++	运行时间	3.915 s
提交时间	2016-11-17 22:44:14	内存使用	31.57 MiB

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <ctime>
inline void getd(int &x){
    char ch = getchar();
    while(!isdigit(ch))ch = getchar();
    x = ch - '0';
    while(isdigit(ch = getchar()))x = x * 10 - '0' + ch;
}
using namespace std;
const int maxn = 200003, maxw = 500003;
 
struct OPT{
    bool NotQ;//1:Add;0:Query
    int val, x, y, T;
    operator int ()const{return x;}
    inline void init(int a, int b, int c, int t){
        x = a, y = b, val = c, T = t;
        NotQ = 1;
    }
    inline void init(int a, int b, int t){
        x = a, y = b, val = 0, T = t;
        NotQ = 0;
    }
}Opt[maxn<<2], *opt[maxn<<2], *Begin[maxn];
 
struct Fenwick{
    #define lowbit(x) (x & -x)
    int len, A[maxn<<2], ind[maxn<<2], cnt;
    inline void init(int l){len = l;memset(A, 0, sizeof(int) * (len + 1));}
    inline void getind(OPT **L, OPT **R){
        static int tmp[maxn<<2], i;i = 0;cnt = 1;
        while(L < R){tmp[i++] = (*L)->y;++L;}
        sort(tmp, tmp + len);
        ind[cnt] = tmp[0];
        for(i = 1;i < len;++i)
            if(tmp[i] != ind[cnt])ind[++cnt] = tmp[i];
        ++cnt;
    }
    inline void Add(int i, int x){
        i = lower_bound(ind + 1, ind + cnt, i) - ind;
        while(i <= len){
            A[i] += x;
            i += lowbit(i);
        }
    }
    inline int Sum(int i){
        i = lower_bound(ind + 1, ind + cnt, i) - ind;
        int ans = 0;
        while(i){
            ans += A[i];
            i ^= lowbit(i);
        }
        return ans;
    }
}F;
 
int W, N, Qcnt = 0, End;
 
inline void init(){
    getd(W), getd(N);
    int i, j, t, a, b, c, d;
    for(i = 0,j = 0;i < N;++i){
        getd(t);
        getd(a), getd(b), getd(c);
        if(t == 1){(opt[j] = Opt + j)->init(a, b, c, j);++j;}
        else{
            getd(d);
            Begin[Qcnt++] = Opt + j;
            (opt[j] = Opt + j)->init(a-1, b-1, j);++j;
            (opt[j] = Opt + j)->init(a-1, d, j);++j;
            (opt[j] = Opt + j)->init(c, b-1, j);++j;
            (opt[j] = Opt + j)->init(c, d, j);++j;
        }
    }
    End = j;
}
 
inline void Solve(int L, int R){
    static OPT *tmp[maxn<<2];
    int len = R - L, mid;
    OPT **it1, **it2;
    if(len == 1)return;
    mid = (L + R) >> 1, it1 = opt + L, it2 = opt + mid;
    if(len == 2){
        if(**it1 > **it2)swap(*it1, *it2);
        else if((*it2)->NotQ==0 && (*it1)->NotQ && (*it1)->y <= (*it2)->y)
            (*it2)->val += (*it1)->val;
        return;
    }
    Solve(L, mid);Solve(mid, R);
    OPT **m = opt + mid, **end = opt + R;
    for(int i = 0;i < len;++i){//merge sort
        if(it1 == m)tmp[i] = *(it2++);
        else if(it2 == end)tmp[i] = *(it1++);
        else if(**it1 > **it2)tmp[i] = *(it2++);
        else tmp[i] = *(it1++);
    }
    it1 = opt + L;
    F.init(len);
    F.getind(tmp, tmp + len);
    for(int i = 0;i < len;++i,++it1){
        *it1 = tmp[i];
        if((*it1)->T < mid && (*it1)->NotQ)
            F.Add((*it1)->y, (*it1)->val);
        else if((*it1)->T >= mid && !(*it1)->NotQ)
            (*it1)->val += F.Sum((*it1)->y);
    }
}
 
int main(){
    freopen("locust.in", "r", stdin);
    freopen("locust.out", "w", stdout);
    init();
    Solve(0, End);
    int a, b, c, d;
    OPT **it = Begin;
    for(int i = 0;i < Qcnt;++i,++it){
        a = (*it)->val;
        b = (*it+1)->val;
        c = (*it+2)->val;
        d = (*it+3)->val;
        printf("%d\n", a - b - c + d);
    }
    return 0;
}