话说这题正解是 CDQ 分治，但我不会……
借用了和我同样不会 CDQ 的人的思路：
横坐标离散化并 BIT 套指针版平衡树。
于是由于是 FHQ Treap 而被洛谷卡常……
加了一些信仰与女装优化后过去了。
可能是人生第一次 BZOJ 过了但在洛谷被卡常。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
using namespace std;
const int BUFF_SIZE = 3 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
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));
}
}