[kuangbin带你飞7]线段树

kuangbin带你飞7

前言

作为一名acm选手,不能连线段树都不会,练就完事了。而且我越发觉得在赛场上不能卡机,中档题才是区分牌子的题目。只有慢慢思索的题目才能真正地提高自己,立下一个flag,每十天完成一个kuangbin专题。现在时间9/6。必须在9/16完成这个线段树专题,就算是困死也得完成。

感想

  1. 左右区间还是注意一下,保不准出题人恶趣味。

  2. 初始化不能想当然$n$多大树多大,有可能他是一个范围,$n$只是代表着式子的个数罢了。

  3. 数组居然还是又一次忘记开4倍。
  4. lazy数组忘记初始化,或者lazy可以为0但是还是初始化为0了。

A.敌兵布阵

题意

这如果我没有记错,应该是人生中第一个线段树题目,很是经典。单点修改,区间查询。

题解

线段树。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 10;
int T,n;
int sum[maxn<<2],lazy[maxn<<2],a[maxn];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void pushdown(int rt,int len){
if(lazy[rt]){
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
sum[rt<<1] += lazy[rt]*(len/2);
sum[rt<<1|1] += lazy[rt]*(len-len/2);
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
sum[rt] = a[l];
return ;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] += val;
sum[rt] += val*(r-l+1);
return ;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R) return sum[rt];
pushdown(rt,r-l+1);
int mid = l+r>>1;
int ans = 0;
if(L <= mid) ans += query(L,R,lson);
if(mid < R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("a.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d",&n);
rep(i,1,n+1) scanf("%d",a+i);
build(1,n,1);
char op[20];
printf("Case %d:\n",test_case);
while(scanf("%s",op) && op[0]!='E'){
if(op[0]=='A' || op[0] =='S'){
int l,val;scanf("%d%d%d",&l,&val);
if(op[0] == 'A') update(val,l,l,1,n,1);
else update(-val,l,l,1,n,1);
}else{
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",query(l,r,1,n,1));
}
}
}

return 0;
}

B.I Hate It

题意

单点修改,区间最值。

题解

线段树。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5 + 10;
int n,m;
int mmax[maxn<<2],a[maxn];
void pushup(int rt){
mmax[rt] = max(mmax[rt<<1],mmax[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
mmax[rt] = a[l];
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int val,int p,int l,int r,int rt){
if(l==r && l==p){
mmax[rt] = val;
return;
}
int mid = l+r>>1;
if(p <= mid) update(val,p,lson);
if(mid < p) update(val,p,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R) return mmax[rt];
int mid = l+r>>1;
int ans = 0;
if(L <= mid) ans = max(ans,query(L,R,lson));
if(mid < R) ans = max(ans,query(L,R,rson));
return ans;
}
int main(){
#ifdef LOCAL
freopen("b.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&m)){
rep(i,1,n+1) scanf("%d",a+i);
build(1,n,1);
rep(i,0,m){
char op[20];int x,y;
scanf("%s%d%d",op,&x,&y);
if(op[0] == 'Q'){
printf("%d\n",query(x,y,1,n,1));
}else{
update(y,x,1,n,1);
}
}
}
return 0;
}

C - A Simple Problem with Integers

题意

区间查询,区间修改。

题解

线段树

lazy需也要开两倍

AC代码

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
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
ll sum[maxn<<2],a[maxn],lazy[maxn<<2];
int n,q;
void pushup(int rt){
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,ll len){
if(lazy[rt]){
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
sum[rt<<1] += lazy[rt]*(len-len/2);
sum[rt<<1|1] += lazy[rt]*(len/2);
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
if(l==r){
sum[rt] = a[l];
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(ll val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] += val;
sum[rt] += val*(r-l+1);
return;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
return sum[rt];
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
ll ans = 0;
if(L <= mid) ans += query(L,R,lson);
if(mid < R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("c.in","r",stdin);
#endif
scanf("%d%d",&n,&q);
rep(i,1,n+1) scanf("%lld",a+i);
build(1,n,1);
rep(i,0,q){
char op[20];int a,b,c;
scanf("%s",op);
if(op[0] == 'C'){
scanf("%d%d%d",&a,&b,&c);
update(c,a,b,1,n,1);
}else{
scanf("%d%d",&a,&b);
printf("%lld\n",query(a,b,1,n,1));
}
}
return 0;
}

D - Mayor’s posters

题意

贴线段,每次贴都会覆盖掉前面的线。问贴到最后能看到多少种不同的线。

题解

线段树+离散化

覆盖线段的范围是1e8,无法建树所以需要离散化,把线段长度按照排序的顺序重新赋值。由于有$2n$个长度所以记得$maxn$要开两倍。

区间修改,单点查询。

AC代码

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
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5 + 20;
int vis[maxn],lx[maxn],rx[maxn],lazy[maxn<<2],mmax[maxn<<2];
int T,n;
void pushdown(int rt){
if(lazy[rt]){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
mmax[rt<<1] = mmax[rt<<1|1] = lazy[rt];
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
mmax[rt] = 0;
return ;
}
int mid = l+r>>1;
build(lson); build(rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
mmax[rt] = val;
return ;
}
pushdown(rt);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
}
int query(int p,int l,int r,int rt){
if(l==r && l==p){
return mmax[rt];
}
int mid = l+r>>1;
pushdown(rt);
if(p <= mid) return query(p,lson);
if(mid < p) return query(p,rson);
}
int main(){
#ifdef LOCAL
freopen("d.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d",&n);
vector<int>x;
rep(i,1,n+1){
int l,r;scanf("%d%d",lx+i,rx+i);
x.push_back(lx[i]);x.push_back(rx[i]);
}
sort(x.begin(),x.end());
x.erase(unique(x.begin(),x.end()),x.end());
rep(i,1,n+1){
lx[i] = lower_bound(x.begin(),x.end(),lx[i])-x.begin()+1;
rx[i] = lower_bound(x.begin(),x.end(),rx[i])-x.begin()+1;
}
int len = x.size();
build(1,len,1);
rep(i,1,n+1){
update(i,lx[i],rx[i],1,len,1);
}
memset(vis,0,sizeof(vis));
int ans = 0;
rep(i,1,len+1){
int x = query(i,1,len,1);
if(vis[x] == 0){
ans ++;
vis[x] = 1;
}
}
printf("%d\n",ans);
}
return 0;
}

E - Just a Hook

题意

区间修改,区间查询

题解

线段树

ac代码

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
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int sum[maxn<<2],a[maxn],lazy[maxn<<2];
int n,q,T;
void pushup(int rt){
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int len){
if(lazy[rt]){
lazy[rt<<1] = lazy[rt];
lazy[rt<<1|1] = lazy[rt];
sum[rt<<1] = lazy[rt]*(len-len/2);
sum[rt<<1|1] = lazy[rt]*(len/2);
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
sum[rt] = 1;
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
sum[rt] = val*(r-l+1);
return;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L <= mid) update(val,L,R,lson);
if(mid < R) update(val,L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
return sum[rt];
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
ll ans = 0;
if(L <= mid) ans += query(L,R,lson);
if(mid < R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("e.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d%d",&n,&q);
build(1,n,1);
rep(i,0,q){
int l,r,val; scanf("%d%d%d",&l,&r,&val);
update(val,l,r,1,n,1);
}
printf("Case %d: The total value of the hook is %d.\n",test_case,query(1,n,1,n,1));
}
return 0;
}

F.Count the Colors

题意

在一条线上区间涂颜色。

问所有颜色出现的区间块的数量。

题解

线段树+懒惰标记

需要注意的是,$n$不代表着数据的范围,8000才是数据的范围,并且由于区块间有空隙,所以离散化还有点不好做。虽然数据也只有8000。注意的是初始化的范围要覆盖到8000,不能以为到$n$就好了。


+5 $n$当坐范围

+3 误以为build函数能够初始化所有的点,但其实是要memset(vis,-1,sizeof(vis));

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head -------------------------
const int maxn = 8e3+10;
int n;
int a[maxn<<2],lazy[maxn<<2],ans[maxn<<2],id[maxn<<2],vis[maxn<<2];
void pushdown(int rt){
if(lazy[rt]!=-1){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
a[rt<<1] = a[rt<<1|1] = lazy[rt];
lazy[rt] = -1;
}
}
void build(int l,int r,int rt){
lazy[rt] = -1;
if(l==r){
a[rt] = -1;
return;
}
int mid = l+r>>1;
build(lson);build(rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
a[rt] = val;
lazy[rt] = val;
return;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
void query(int l,int r,int rt){
if(l==r){
vis[l] = a[rt];
return;
}
int mid = l+r>>1;
pushdown(rt);
query(lson);
query(rson);
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
while(scanf("%d",&n)!=EOF){
build(1,8000,1);
memset(ans,0,sizeof(ans));
memset(vis,0,sizeof(vis));
memset(id,0,sizeof(id));
rep(i,1,n+1){
int l,r,x;scanf("%d%d%d",&l,&r,&x);
if(l>=r) continue;
update(x,l+1,r,1,8000,1);
}
query(1,8000,1);
int last = -1;
//int i = 1;
rep(i,1,maxn){
while(vis[i]==-1) i++,last=-1;
if(i>=maxn) break;
if(vis[i] != last){
last = vis[i];
ans[vis[i]]++;
}
}
rep(i,0,8000+1){
if(ans[i]==0) continue;
printf("%d %d\n",i,ans[i]);
}
puts("");
}
return 0;
}

G.Balanced Lineup

题意

求区间最大值和最小值的差

题解

可以用ST表预处理,也可以用树状数组或者是线段树,线段树的常数比较大,但他们的复杂度均是$O(nlogn)$

AC代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+20;
int mmax[maxn],mmin[maxn];
int a[maxn];
int n,q;
int lowbit(int x){
return x&-x;
}
void update(int x){
for(int i=x;i<=n;i+=lowbit(i)){
mmax[i] = a[i];
mmin[i] = a[i];
for(int j=1;j<lowbit(i);j<<=1){
mmax[i] = max(mmax[i],mmax[i-j]);
mmin[i] = min(mmin[i],mmin[i-j]);
}
}
}
int query_min(int l,int r){
int res = INF;
while(r>=l){
res = min(a[r],res);
r--;
for(;r-lowbit(r)>=l;r-=lowbit(r))
res = min(mmin[r],res);
}
return res;
}
int query_max(int l,int r){
int res = -INF;
while(r>=l){
res = max(a[r],res);
r--;
for(;r-lowbit(r)>=l;r-=lowbit(r))
res = max(mmax[r],res);
}
return res;
}
int solve(int l,int r){
return query_max(l,r)-query_min(l,r);
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d%d",&n,&q);
rep(i,1,n+1) mmin[i]=INF,mmax[i]=-INF;
rep(i,1,n+1){
scanf("%d",a+i);
update(i);
}
while(q--){
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",solve(l,r));
}
return 0;
}

H.Can you answer the queries?

题意

区间数字根号,区间查询数字和。

题解

线段树+智力门槛

因为所有数字最多根号8次就会变成1。所以我们只需要处理一下当数字为1就不用再更新区间内的数了。


acm还是靠智力和眼力啊,我想了半天都没想出来什么数学方法,原来只需要看出规律和找到最关键的突破点就ok了。

+1超时忘记开4倍数组了。。

+1 虚伪的看到了提醒要注意l,r的大小关系,妈的,这都卡,是不是人啊。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int n,q;
ll sum[maxn<<2],mmax[maxn<<2];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
mmax[rt] = max(mmax[rt<<1],mmax[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
ll x;scanf("%lld",&x);
mmax[rt] = sum[rt] = x;
return;
}
int mid = l+r>>1;
build(lson);build(rson);
pushup(rt);
}
void update(int L,int R,int l,int r,int rt){
if(mmax[rt]==1) return;
if(l==r){
mmax[rt] = sqrt(mmax[rt]);
sum[rt] = sqrt(sum[rt]);
return;
}
int mid = l+r>>1;
if(L<=mid) update(L,R,lson);
if(mid<R) update(L,R,rson);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R) return sum[rt];
int mid = l+r>>1;
ll ans = 0;
if(L<=mid) ans += query(L,R,lson);
if(mid<R) ans += query(L,R,rson);
return ans;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int test_case = 1;
while(~scanf("%d",&n)){
build(1,n,1);
scanf("%d",&q);
printf("Case #%d:\n",test_case++);
while(q--){
int l,r,op;scanf("%d%d%d",&op,&l,&r);
if(l>r){
int temp = l;
l = r;
r = temp;
}
if(op==0){
update(l,r,1,n,1);
}else{
printf("%lld\n",query(l,r,1,n,1));
}
}
puts("");
}
return 0;
}

I Tunnel Warfare(前面写过了)

题意

题解

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
const int maxn = 5e4+20;
int bit[maxn];
int lowbit(int x){
return x&-x;
}
int query(int x){
int ans = 0;
for(int i = x;i;i-=lowbit(i)){
ans += bit[i];
}
return ans;
}
int query(int l,int r){
return query(r)-query(l-1);
}
void add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
bit[i] += val;
}
}
int solve_left(int l,int r){
int mid = l+r>>1;int ans = r;
while(l<=r){
mid = l+r>>1;
if(query(mid,r)==r-mid+1) r = mid-1,ans = mid;
else l = mid+1;
}
return ans;
}
int solve_right(int l,int r){
int mid,ans = l;
while(l<=r){
mid = l+r>>1;
if(query(l,mid)==mid-l+1) l=mid+1,ans = mid;
else r = mid-1;
}
return ans;
}
int vis[maxn];
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m)!=EOF){
stack<int> st;
memset(bit,0,sizeof(bit));
memset(vis,0,sizeof(vis));
rep(i,1,n+1) add(i,1);
while(m--){
char op[20];scanf("%s",op);
if(op[0]=='D'){
int x;scanf("%d",&x);
st.push(x);
if(vis[x]) continue;
vis[x] = 1;
add(x,-1);
}else if(op[0]=='Q'){
int x;scanf("%d",&x);
if(query(x,x)==0) puts("0");
else printf("%d\n",solve_right(x,n)-solve_left(1,x)+1);
}else{
add(st.top(),1);
vis[st.top()] = 0;
st.pop();
}
}
}
return 0;
}

J.Assign the task

题意

dfs序+线段树模板题

题解

同上


+1 lazy数组没有初始化,没适应无build建树

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+10;
int T,n,clk;
int on[maxn],in[maxn],ind[maxn],a[maxn<<2],lazy[maxn<<2];
vector<int> G[maxn];
void init(){
clk = 0;
memset(on,0,sizeof(on));
memset(in,0,sizeof(in));
memset(ind,0,sizeof(ind));
memset(a,-1,sizeof(a));
memset(lazy,-1,sizeof(lazy));
rep(i,0,n+1) G[i].clear();
}
void dfs(int u,int fa){
for(auto v:G[u]){
if(v==fa) continue;
in[v] = ++clk;
dfs(v,u);
}
on[u] = clk;
}
void pushdown(int rt){
if(lazy[rt]!=-1){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
a[rt<<1] = a[rt<<1|1] = lazy[rt];
lazy[rt] = -1;
}
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
a[rt] = val;
return ;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
int query(int p,int l,int r,int rt){
if(l==r && p==l) return a[rt];
int mid = l+r>>1;
pushdown(rt);
if(p<=mid) return query(p,lson);
else return query(p,rson);
}
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d",&n);
init();
rep(i,0,n-1){
int u,v;scanf("%d%d",&u,&v);
G[v].push_back(u);
ind[u]++;
}
int root = 0;
rep(i,1,n+1) if(ind[i]==0){
root = i;
break;
}
in[root] = ++clk;
dfs(root,-1);
int q;scanf("%d",&q);
printf("Case #%d:\n",test_case);
while(q--){
char op[20];int x,y;
scanf("%s",op);
if(op[0]=='C'){
scanf("%d",&x);
printf("%d\n",query(in[x],1,n,1));
}else{
scanf("%d%d",&x,&y);
update(y,in[x],on[x],1,n,1);
}
}
}

return 0;
}

K.Transformation

题意

有四种操作。

  1. 将$[l,r]$区间的数字加上$val$.
  2. 将$[l,r]$区间的数字乘上$val$
  3. 将$[l,r]$区间的数字变成$val$
  4. 求区间$[l,r]$内所有数字$[1,2,3]$次方的和。

题解

线段树

对于线段树的懒惰标记和取模运算细节要求很高。

相信对于sum数组的转化大家都能够推得出来,但是关于pushdown的操作是另有玄机。

首先他的顺序很重要。得先将lazy[1]递推下去,也就是操作3把数字变成$val$,之后再进行乘法和加法的操作。对于乘法很重要的一点是你在lazy[2]标记递推的时候,其实你把子树中的加法也相当于乘了$val$,所以递推不仅要递推乘法标记,还要递推加法标记。


+3 更新Pushdown中你也要更新lazy数组的值

+1 更新的次序也有关系

+1初始化 有的要1.

+1 少写一个|1 rt[rt<<1|1]写成了rt<<1

+10000 有一个r-l+1写错了,下次写成 len 。不然很容易出错妈了个鸡

AC代码

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
155
156
157
158
159
160
161
162
163
164
165
166
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
template <typename T>
inline bool read (T &ret) {
char c;
int sgn;
if (c = getchar(), c == EOF) return 0; //EOF
while (c != '-' && (c < '0' || c > '9') ) {
if((c = getchar()) == EOF) return 0;
}
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const ll maxn = 1e5 + 20;
const ll mod = 1e4 + 7;
ll pp[mod+20][4],sum[4][maxn<<2];
ll lazy[maxn<<2][4];
int n,m,x,y,val;
void init(){
memset(sum,0,sizeof(sum));
memset(lazy,0,sizeof(lazy));
rep(i,0,maxn){
lazy[i][2] = 1;
}
}
void pushup(int rt){
rep(i,1,4){
sum[i][rt] = (sum[i][rt<<1] + sum[i][rt<<1|1])%mod;
}
}
void pushdown(int rt,ll len){
if(lazy[rt][3]){
ll c = lazy[rt][3]%mod;
lazy[rt<<1][1] = lazy[rt<<1|1][1] = 0;
lazy[rt<<1][2] = lazy[rt<<1|1][2] = 1;
lazy[rt<<1][3] = lazy[rt<<1|1][3] = c;
sum[1][rt<<1] = c*(len-len/2);
sum[1][rt<<1|1] = c*(len/2);
sum[2][rt<<1] = pp[c][2]*(len-len/2)%mod;
sum[2][rt<<1|1] = pp[c][2]*(len/2)%mod;
sum[3][rt<<1] = pp[c][3]*(len-len/2)%mod;
sum[3][rt<<1|1] = pp[c][3]*(len/2)%mod;
lazy[rt][3] = 0;
rep(i,1,4){
sum[i][rt<<1] %= mod;
sum[i][rt<<1|1] %= mod;
}
}
if(lazy[rt][2]!=1){
ll c = lazy[rt][2]%mod;
rep(i,1,4){
sum[i][rt<<1] *= pp[c][i];
sum[i][rt<<1|1] *= pp[c][i];
}
rep(i,1,3){
lazy[rt<<1][i] = (lazy[rt<<1][i]%mod)*c%mod;
lazy[rt<<1|1][i] = (lazy[rt<<1|1][i]%mod)*c%mod;
}
lazy[rt][2] = 1;
rep(i,1,4){
sum[i][rt<<1] %= mod;
sum[i][rt<<1|1] %= mod;
}
}
if(lazy[rt][1]){
ll c = lazy[rt][1]%mod;
lazy[rt<<1][1] += c;
lazy[rt<<1|1][1] += c;
lazy[rt<<1][1] %= mod;
lazy[rt<<1|1][1] %= mod;
sum[3][rt<<1] += 1ll*3*sum[2][rt<<1]%mod*c%mod + c*c%mod*c%mod*(len-len/2)%mod + 3*sum[1][rt<<1]%mod*c%mod*c%mod;
sum[3][rt<<1|1] += 1ll*3*sum[2][rt<<1|1]%mod*c%mod + 3*sum[1][rt<<1|1]*c%mod*c%mod + c*c%mod*c%mod*(len/2)%mod;
sum[2][rt<<1] += 1ll*2*sum[1][rt<<1]%mod*c%mod + c*c%mod*(len-len/2)%mod;
sum[2][rt<<1|1] += 1ll*2*sum[1][rt<<1|1]%mod*c%mod + c*c%mod*(len/2)%mod;
sum[1][rt<<1] += c*(len-len/2);
sum[1][rt<<1|1] += c*(len/2);
lazy[rt][1] = 0;
}
rep(i,1,4){
sum[i][rt<<1] %= mod;
sum[i][rt<<1|1] %= mod;
lazy[rt<<1|1][i] %= mod;
lazy[rt<<1][i] %= mod;
}
}
void update(int op,ll c,ll L,ll R,ll l,ll r,ll rt){
if(L<=l && r<=R){
if(op==1){
sum[3][rt] += 1ll*3*sum[2][rt]*c%mod+1ll*3*sum[1][rt]*c%mod*c%mod+c*c%mod*c%mod*(r-l+1)%mod;
sum[2][rt] += sum[1][rt]%mod*c%mod*2%mod+c*c%mod*(r-l+1)%mod;
sum[1][rt] += 1ll*(r-l+1)*c%mod;
lazy[rt][1] += c;
lazy[rt][1] %= mod;
}else if(op==2){
rep(i,1,4) sum[i][rt] *= pp[c][i];
lazy[rt][2] *= c;
lazy[rt][2] %= mod;
lazy[rt][1] *= c;
lazy[rt][1] %= mod;
}else{
rep(i,1,4) sum[i][rt] = pp[c][i]*(r-l+1)%mod;
lazy[rt][3] = c;
lazy[rt][1] = 0;lazy[rt][2] = 1;
}
rep(i,1,4) sum[i][rt] %= mod;
return;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
if(L<=mid) update(op,c,L,R,lson);
if(mid<R) update(op,c,L,R,rson);
pushup(rt);
}
ll query(int op,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
return sum[op][rt];
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
ll ans = 0;
if(L<=mid) (ans += query(op,L,R,lson)%mod)%=mod;
if(mid<R) (ans += query(op,L,R,rson)%mod)%mod;
pushup(rt);
return ans%mod;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
//freopen("2.out","w",stdout);
#endif
rep(i,1,mod+1) pp[i][1] = i%mod;
rep(i,1,mod+1){
rep(j,2,4){
pp[i][j] = (ll)pp[i][j-1]*i%mod;
}
}
while(~scanf("%d%d",&n,&m)){
init();
rep(i,0,m){
int op;read(op); read(x);read(y);read(val);
if(op==4){
printf("%lld\n",query(val,x,y,1,n,1));
}else{
update(op,val,x,y,1,n,1);
}
}
}
#ifdef LOCAL
fclose(stdin);
fclose(stdout);
#endif
return 0;
}

L - Vases and Flowers

题意

做过 在我之前博客里面有。

题解

做过


+2 忘记掉可能初始不能放在A点,所以要加入一个全局变量flag,初始化maxl。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,now,maxl,maxr,flag;
const int maxn = 5e4+20;
int sum[maxn<<2],lazy[maxn<<2];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void pushdown(int rt,int len){
if(lazy[rt] != -1){
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
sum[rt<<1] = lazy[rt]*(len-len/2);
sum[rt<<1|1] = lazy[rt]*(len/2);
lazy[rt] = -1;
}
}
void build(int l,int r,int rt){
lazy[rt] = -1;
if(l==r){
sum[rt] = 0;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
pushup(rt);
}
void update1(int p,int l,int r,int rt){
if(now == 0) return;
int len = r-l+1;
if(sum[rt] == len) return;
if(l>=p && sum[rt] == 0 && len <= now){
now -= len;
sum[rt] = len;
lazy[rt] = 1;
if(flag == 0)
maxl = l,flag = 1;
maxr = max(maxr,r);
return;
}
pushdown(rt,len);
int mid = l+r>>1;
if(p<=mid) update1(p,lson);
update1(p,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = 0;
int temp = sum[rt];
sum[rt] = 0;
return temp;
}
pushdown(rt,r-l+1);
int mid = l+r>>1;
int ans = 0;
if(L<=mid) ans += query(L,R,lson);
if(mid<R) ans += query(L,R,rson);
pushup(rt);
return ans;
}
int main(){
#ifdef LOCAL
freopen("l.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
int m;scanf("%d%d",&n,&m);
build(1,n,1);
rep(i,0,m){
int op,x,y;scanf("%d%d%d",&op,&x,&y);
x++;
if(op==1){
now = y;
maxl = x;maxr = x;flag = 0;
update1(x,1,n,1);
if(now == y)
puts("Can not put any one.");
else
printf("%d %d\n",maxl-1,maxr-1);
}else{
y++;
printf("%d\n",query(x,y,1,n,1));
}
}
puts("");
}
return 0;
}

M - 约会安排

题意

对每一次查询寻找$val$长度的最前面空闲时间并占据他。

  • 如果是女神来查询,那么空闲的时间也包括基友的时间
  • 如果是基友来查询,那么只有空闲的时间可以选择
  • 如果想要学习$[l,r]$,那么$[l,r]$之间的时间都会被清空。

题解

线段树的区间合并。

这里由于要维护两个线段树,所以用结构体来构造树,不过确实使用结构体封装之后复用性高了很多。

  • 定义三个量$ll,rr,mm$分别表示从区间$[L,R]$最左边开始的最长长度和从区间最右边开始的最长长度和区间内横跨中点的最长长度。
  • 定义$maxlen$来表示区间内最长的长度来剪枝。

这样就可以更新了。

一棵树代表屌丝+女神占有的,一棵树代表女神占有的。

查询分为三种方向

  • 先查询左边开始的长度是否大于$val$,如果大于返回$L$,或者是递归左子树。
  • 再查询中间的部分长度是否大于$val$,如果大于返回$mid-rr[lc]+1$就是中点减掉从左半部分右边的长度。
  • 再查询递归右子树。

+1 区间合并中 更新父节点必须每个都更新,所以有时候你在return 之前也要更新一下。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head ----------------------------------------
const int maxn = 1e6+20;
int T,n,m;
struct sgt{
int maxlen[maxn<<2];
int ll[maxn<<2],rr[maxn<<2],mm[maxn<<2];
int lazy[maxn<<2];
void build(int l,int r,int rt){
lazy[rt] = -1;
if(l==r){
ll[rt] = rr[rt] = 0;
mm[rt] = 1;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
}
void init(){
lazy[1] = 1;
}
void pushup(int l,int r,int rt){
if(lazy[rt]>=0){
maxlen[rt] = ll[rt] = rr[rt] = mm[rt] = (lazy[rt]?(r-l+1):0);
}else{
int lc = rt<<1,rc = rt<<1|1,mid = l+r>>1;
ll[rt] = ll[lc];
if(ll[lc]==(mid-l+1)) ll[rt] += ll[rc];
mm[rt] = rr[lc] + ll[rc];
rr[rt] = rr[rc];
if(rr[rc] == r-mid) rr[rt] += rr[lc];
maxlen[rt] = max(maxlen[lc],max(maxlen[rc],mm[rt]));
}
}
void pushdown(int rt){
if(lazy[rt]>=0){
int lc=rt<<1,rc=rt<<1|1;
lazy[lc] = lazy[rc] = lazy[rt];
lazy[rt] = -1;
}
}
int query(int val,int l,int r,int rt){
pushup(l,r,rt);
//cout<<l<<' '<<r<<' '<<" ";
int lc = rt<<1,rc = rt<<1|1,mid = l+r>>1;
if(val>maxlen[rt]) return 0;
if(ll[rt] >= val) return l;
pushdown(rt);
pushup(rson);
int temp = query(val,lson);
if(temp) return temp;
if(mm[rt] >= val) return mid-rr[lc]+1;
return query(val,rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
pushup(l,r,rt);
return;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
else pushup(lson);
if(mid<R) update(val,L,R,rson);
else pushup(rson);
pushup(l,r,rt);
}
}all,ns;
char op[20];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
printf("Case %d:\n",test_case);
scanf("%d%d",&n,&m);
//all.build(1,n,1); ns.build(1,n,1);
all.init(); ns.init();
while(m--){
scanf("%s",op);
if(op[0]=='D'){
int x;scanf("%d",&x);
int ans = all.query(x,1,n,1);
if(ans){
all.update(0,ans,ans+x-1,1,n,1);
printf("%d,let's fly\n",ans);
}else{
puts("fly with yourself");
}
}else if(op[0]=='N'){
int x;scanf("%d",&x);
int ans = all.query(x,1,n,1);
if(!ans) ans = ns.query(x,1,n,1);
if(ans){
all.update(0,ans,ans+x-1,1,n,1);
ns.update(0,ans,ans+x-1,1,n,1);
printf("%d,don't put my gezi\n",ans);
}else{
puts("wait for me");
}
}else{
int x,y;scanf("%d%d",&x,&y);
all.update(1,x,y,1,n,1);
ns.update(1,x,y,1,n,1);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}

return 0;
}

Reference:https://www.cnblogs.com/DSChan/p/4861977.html

N.picture

题意

求多个矩形周长的并

题解

扫描线+线段树


这道题目没有离散化$X$坐标就可以做。而且例子也只有一个。。

ac代码

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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pb push_back
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxn = 2e4+100;
struct node{
int lx,rx,y;
int f;
node(){}
node(int _lx,int _rx,int _y,int _f){
lx = _lx; rx = _rx; y = _y; f = _f;
}
bool operator<(const node &s) const{
return y<s.y;
}
}L[maxn<<2];
int sum[maxn<<2],lb[maxn<<2],rb[maxn<<2],seg[maxn<<2];
int flag[maxn<<2];
void pushup(int rt,int l,int r){
if(flag[rt]){
sum[rt] = r-l+1;
lb[rt] = rb[rt] = 1;
seg[rt] = 2;
}else if(l==r){
sum[rt] = lb[rt] = rb[rt] = seg[rt] = 0;
}else{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
lb[rt] = lb[rt<<1];
rb[rt] = rb[rt<<1|1];
seg[rt] = seg[rt<<1] + seg[rt<<1|1];
if(lb[rt<<1|1]&&rb[rt<<1]) seg[rt]-=2;
}
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
flag[rt] += val;
}else{
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
pushup(rt,l,r);
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
while(~scanf("%d",&n)){
int cnt = 0;
int maxl = INF; int maxr = -INF;
rep(i,0,n){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
L[++cnt] = node(x1,x2,y1,1);
L[++cnt] = node(x1,x2,y2,-1);
maxl = min(maxl,x1);
maxr = max(maxr,x2);
}
sort(L+1,L+1+cnt);
int res = 0;
int last = 0;
rep(i,1,cnt+1){
update(L[i].f,L[i].lx,L[i].rx-1,maxl,maxr,1);
res += abs(sum[1]-last);
res += seg[1] * (L[i+1].y-L[i].y);
last = sum[1];
}
printf("%d\n",res);
}

return 0;
}