BZOJ 1176 「BalkanOI 2007」Mokia

话说这题正解是 CDQ 分治，但我不会……

借用了和我同样不会 CDQ 的人的思路：
横坐标离散化并 BIT 套指针版平衡树。

于是由于是 FHQ Treap 而被洛谷卡常……
加了一些信仰与女装优化后过去了。

可能是人生第一次 BZOJ 过了但在洛谷被卡常。

代码：

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define lowbit(x) ((x) & -(x))
#define ls(p) p->lson
#define rs(p) p->rson
using namespace std;

const int BUFF_SIZE = 3 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
inline void read(int &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int W = 2e6;
const int U = 16e4;
const int Q = 1e4;
int w,n;
int op;
int ind[U + (Q << 1) + 10];
struct node
{
    int pos,val,rnd,sz,sum;
    node *lson,*rson;
} *c[U + (Q << 1) + 10];
inline node *new_node(int x,int v)
{
    node *ret = new node();
    ret->pos = x;
    ret->val = ret->sum = v;
    ret->rnd = rand();
    ret->sz = 1;
    ls(ret) = rs(ret) = NULL;
    return ret;
}
inline void up(node *p)
{
    p->sz = 1,p->sum = p->val;
    if(ls(p))
        p->sz += ls(p)->sz,p->sum += ls(p)->sum;
    if(rs(p))
        p->sz += rs(p)->sz,p->sum += rs(p)->sum;
}
void split(node *p,int k,node *&x,node *&y)
{
    if(!p)
    {
        x = y = NULL;
        return ;
    }
    if(p->pos <= k)
        x = p,split(rs(p),k,rs(p),y);
    else
        y = p,split(ls(p),k,x,ls(p));
    up(p);
}
node *merge(node *x,node *y)
{
    if(!x)
        return y;
    if(!y)
        return x;
    if(x->rnd < y->rnd)
    {
        rs(x) = merge(rs(x),y);
        up(x);
        return x;
    }
    else
    {
        ls(y) = merge(x,ls(y));
        up(y);
        return y;
    }
}
void add(node *&p,int pos,int val)
{
    node *x,*y,*z;
    split(p,pos,x,z);
    split(x,pos - 1,x,y);
    if(!y)
        y = new_node(pos,val);
    else
        y->val += val,y->sum += val;
    p = merge(merge(x,y),z);
}
int answer(node *&p,int pos1,int pos2)
{
    node *x,*y,*z;
    split(p,pos2,x,z);
    split(x,pos1 - 1,x,y);
    int ret = y ? y->sum : 0;
    p = merge(merge(x,y),z);
    return ret;
}
inline void update(int x,int y,int k)
{
    for(;x <= n;x += lowbit(x))
        add(c[x],y,k);
}
inline int query(int x,int y1,int y2)
{
    int ret = 0;
    for(;x;x -= lowbit(x))
        ret += answer(c[x],y1,y2);
    return ret;
}
struct s_commad
{
    int op,x1,y1,x2,y2,k;
} cmd[U + Q + 10];
int tot;
int main()
{
    srand(19260817);
    read(op),read(w);
    while(1)
    {
        read(op);
        if(op == 3)
            break;
        cmd[++tot].op = op;
        if(op == 1)
        {
            read(cmd[tot].x1),read(cmd[tot].y1),read(cmd[tot].k);
            ind[++n] = cmd[tot].x1;
        }
        else
        {
            read(cmd[tot].x1),read(cmd[tot].y1),read(cmd[tot].x2),read(cmd[tot].y2);
            ind[++n] = cmd[tot].x1;
            ind[++n] = cmd[tot].x2;
        }
    }
    sort(ind + 1,ind + n + 1);
    n = unique(ind + 1,ind + n + 1) - ind - 1;
    for(register int i = 1;i <= tot;++i)
    {
        cmd[i].x1 = lower_bound(ind + 1,ind + n + 1,cmd[i].x1) - ind;
        cmd[i].x2 = lower_bound(ind + 1,ind + n + 1,cmd[i].x2) - ind;
        if(cmd[i].op == 1)
            update(cmd[i].x1,cmd[i].y1,cmd[i].k);
        else
            printf("%d\n",query(cmd[i].x2,cmd[i].y1,cmd[i].y2) - query(cmd[i].x1 - 1,cmd[i].y1,cmd[i].y2));
    }
}