luogu4203 [NOI2008]糖果雨

OI 数学
文章目录

ref and ref

神仙数形结合……

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
#include <iostream>
#include <cstdio>
using namespace std;
int n, len, len2, len4, cc[2][2005][4005], x[1000005], y[1000005], opt, t;
int lb(int x){
return x & -x;
}
int sum(int o, int a, int b){
if(a<0 || b<0) return 0;
a++; b++;
int re=0;
a = min(a, len2+1);
b = min(b, len4+1);
for(; a; a-=lb(a))
for(int i=b; i; i-=lb(i))
re += cc[o][a][i];
return re;
}
int query(int o, int xu, int yu, int xv, int yv){
return sum(o, xv, yv)-sum(o, xu-1, yv)-sum(o, xv, yu-1)+sum(o, xu-1, yu-1);
}
void add(int o, int a, int b, int v){
a++; b++;
for(; a<=len2; a+=lb(a))
for(int i=b; i<=len4; i+=lb(i))
cc[o][a][i] += v;
}
int main(){
cin>>n>>len;
len2 = len << 1;
len4 = len << 2;
while(n--){
scanf("%d %d", &opt, &t);
if(opt==1){
int c, l, r, d;
scanf("%d %d %d %d", &c, &l, &r, &d);
x[c] = (t - d * l + len2 )% len2;
y[c] = r - l;
add(0, x[c], y[c]+x[c], 1);
add(1, x[c], y[c]-x[c]+len2, 1);
}
else if(opt==2){
int l, r;
scanf("%d %d", &l, &r);
t %= len2;
int k=(r==len);
int ans=query(0, t, l+t, r+t, len4)+query(0, 0, t+l-len2, t+r-len2-k, len4)+query(1, t-r+len2+k, l-t, len2, len4)+query(1, t-r, l-t+len2, t-1, len4);
printf("%d\n", ans);
}
else{
int c;
scanf("%d", &c);
add(0, x[c], y[c]+x[c], -1);
add(1, x[c], y[c]-x[c]+len2, -1);
}
}
return 0;
}