标签: 线段树 - CheaSim Blog
发表更新acm5 分钟读完 (大约678个字)

[hdoj6406]Taotao Picks Apple

Taotao Picks Apples

题意

一段序列，从中挑选的子序列是这样规定的

能取就取，而且取得数字一定要比上一次取得数字要大。

已知一段序列，问如果改变序列中的一个数字，那么取得数字的个数是多少。

题解

每次查询将数组分为两部分$[1,p-1],[p+1,n]$，前半部分的最长长度就是可以通过预处理得到。很容易想到先处理出从头到$i$的最大长度$dl[i]$。然后针对后半段，我们要得到的是置换的$q$，然后大于他的第一个数字到末尾的最大长度。

有一个细节就是，如果置换的数字小于前面最大的数字，那么就是从前面最大的数字到$[p+1,n]$中间大于这个数字的第一个数字开始。

如果置换的数字大于前面最大的数字，那么答案就是$dl([1,p-1])+1+dr([p+1,n])$这个意思。

寻找第一个比该数字大的最前数字用的是线段树。

+1 判断最大值的时候直接用mmax判断，应该用a[x]判断

+1 得到dr数组的时候范围搞错了，应该是[i,n]的范围内比a[i]大的第一个数字。

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
#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+100;
int n,m;
int a[maxn];
struct Segtree{
    int mmax[maxn<<2]={0},id[maxn<<2]={0},cur=0;
    void pushup(int rt){
        int x = id[rt<<1],y = id[rt<<1|1];
        id[rt] = a[x]>a[y]?x:y;
        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];
            id[rt] = l;
            return;
        }
        int mid = l+r>>1;
        build(lson); build(rson);
        pushup(rt);
    }
    void query1(int val,int L,int R,int l,int r,int rt){
        if(l==r){
            if(mmax[rt]>val) cur = min(cur,id[rt]);
            return;
        }
        int mid = l+r>>1;
        if(L<=l && r<=R){
            if(mmax[rt<<1]>val) query1(val,L,R,lson);
            else if(mmax[rt<<1|1]>val) query1(val,L,R,rson);
            return;
        }
        if(L<=mid) query1(val,L,R,lson);
        if(mid<R) query1(val,L,R,rson);
    }
    void query2(int L,int R,int l,int r,int rt){
        if(L<=l && r<=R){
            if(mmax[rt]>a[cur]) cur = id[rt];
            return;
        }
        int mid = l+r>>1;
        if(L<=mid) query2(L,R,lson);
        if(mid<R) query2(L,R,rson);
    }
}st;
int dl[maxn],dr[maxn];
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        rep(i,1,n+1) scanf("%d",a+i);
        st.build(1,n,1);
        int mx = 0;
        memset(dr,0,sizeof(dr));
        memset(dl,0,sizeof(dl));
        rep(i,1,n+1){
            if(a[i]>mx){
                mx = a[i];
                dl[i] = dl[i-1]+1;
            }else{
                dl[i] = dl[i-1];
            }
        }
        per(i,1,n+1){
            st.cur = n+1;
            st.query1(a[i],i,n,1,n,1);
            if(st.cur>n) st.cur = 0;
            dr[i] = dr[st.cur]+1;
        }
        while(m--){
            int p,q;scanf("%d%d",&p,&q);
            int ans = 0; st.cur = 0;
            if(p>1) st.query2(1,p-1,1,n,1);
            ans += dl[st.cur];
            if(q > a[st.cur]) ans ++;
            if(q <= a[st.cur]) q = a[st.cur];
            st.cur = n+1;
            if(p<n) st.query1(q,p+1,n,1,n,1);
            if(st.cur<=n) ans += dr[st.cur];
            printf("%d\n",ans);
        }
    }
    
    return 0;
}
发表更新线段树1 分钟读完 (大约139个字)

Codeforces 833B - The Bakery

Codeforces 833B - The Bakery

题意

将一段数字分成最多50个区间，每个区间的价值是区间内不同数字的个数，问怎么样分区间使得价值总和最大。

题解

$dp$加线段树。

$dp[i][j]$表示第$j$个坐标分成$i$块最大的价值。

转移方程

  • $dp[i][j] = max(dp[i][j],dp[i-1][x] + restofx)$，其中$x$是从1到$j$。

因为每次要获得剩下的x中数字不同的个数，暴力的做法是$O(n^2*k)$，

ac代码

发表更新acm5 分钟读完 (大约702个字)

[hdoj1540]Tunnel Warfare

Tunnel Warfare

题意

在一条线上有二种操作

  • 删掉一个点
  • 恢复一个点

求某一个点和与之相连点的个数。

题解

线段树设左右标志或者是树状数组二分

HDOJ可以线段树+二分。

Cnm hdoj 多组数据不给提示

如果是树状数组500ms，线段树+二分1500ms。

POJ卡了线段树+二分。HDOJ没有写多组输入害得我WA成sb了。

垃圾HDOJ还造假数据，毁坏多个碉堡。也是服了。

WA代码

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
#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 sum[maxn<<3],vis[maxn],last[maxn];
int n,q;
void pushup(int rt){
    sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        sum[rt] = 1;
        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){
        sum[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 sum[rt];
    }
    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;
}
bool check(int l,int r){
    if(query(l,r,1,n,1) == r-l+1) return true;
    return false;
}
int solve1(int l,int r,int rt){
    int mid;int st = n;
    while(l<=r){
        mid = l+r>>1;
        if(check(mid,r)) r = mid-1,st = mid;
        else l = mid+1;
    }
    return st;
}
int solve2(int l,int r,int rt){
    int mid ;int ed = n;
    while(l<=r){
        mid = l+r>>1;
        if(check(l,mid)) l = mid+1,ed = mid;
        else r = mid-1;
    }
    return ed;
    //cout<<ed<<' ';
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&q)){
    build(1,n,1);
    rep(i,1,n+1) vis[i] = 1;
    int top = 0;
    while(q--){
        char op[20];
        scanf("%s",op);
        if(op[0] == 'D'){
            int x; scanf("%d",&x);
            update(0,x,1,n,1);
            last[top++] = x;
        }else if(op[0] == 'R'){
            int x =last[--top];
            update(1,x,1,n,1);
        }else{
            int x;scanf("%d",&x);
            if(query(x,x,1,n,1)==0){
                puts("0");
                continue;
            }
            printf("%d\n",solve2(x,n,x)-solve1(1,x,x)+1);
        }
    }
    }

    return 0;
}

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
#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;
}
发表更新线段树4 分钟读完 (大约589个字)

[hdoj4614]Vases and Flowers

Vases and Flowers

题意

Alice去一排$n$的花盆中种花，有两种操作

  • 从$a$开始种花，如果该花盆有花就跳到下一个花盆。直到没有花种或者到了$n$盆
  • $[a,b]$区间的所有花都扔掉。

询问

  • 1操作中开始种花的盆和停止种花的盆
  • 2操作中丢掉的花

题解

线段树，$sum$表示花的个数，用$lazy$来懒惰标记。

妈的，我线段树还是不够熟悉，居然使用了$update(p,n,1)$这样子的形式，以为每个区间的$rt$都是随机的，其实线段树的区间都是固定的，你只能通过$lson,rson$来寻找每一个区间，不能自己xjb改区间。

寻找p开始位置的时候，需要思考一下。image一下中点和左端与p的关系就好了。

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
#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 = 5e5 + 10;
int m,n,T;
int now,ed,st;
bool flag = 0;
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] == 0){
        lazy[rt<<1] = lazy[rt<<1|1] = 0;
        sum[rt<<1] = sum[rt<<1|1] = 0;
        lazy[rt] = -1;
    }
    if(lazy[rt] == 1){
        lazy[rt<<1] = lazy[rt<<1|1] = 1;
        sum[rt<<1] = len-len/2;
        sum[rt<<1|1] = 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 update(int p,int l,int r,int rt){
    if(now == 0) return;
    if(r-l+1 == sum[rt]) return;
    if(sum[rt] == 0 && now >= r-l+1 && l>=p){
        sum[rt] = r-l+1;
        now -= (r-l+1);
        lazy[rt] = 1;
        if(!flag) st = l,flag = 1,ed = r;
        else ed = r;
        return;
    }
    pushdown(rt,r-l+1);
    int mid = l+r>>1;
    if(p <= mid) update(p,lson); 
    update(p,rson);
    pushup(rt);
}
void update(int L,int R,int l,int r,int rt){
    if(L<=l && r<=R){
        now += sum[rt];
        sum[rt] = 0;
        lazy[rt] = 0;
        return;
    }
    pushdown(rt,r-l+1);
    int mid = l+r>>1;
    if(L <= mid) update(L,R,lson);
    if(mid < R) update(L,R,rson);
    pushup(rt);
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        build(1,n,1);
        rep(i,0,m){
            int op,a,b;
            scanf("%d%d%d",&op,&a,&b);
            if(op==1){
                a++;
                now = b;st = ed = a; flag = 0;
                update(a,1,n,1);
                if(now==b){
                    puts("Can not put any one.");
                }else{
                    ed--;st--;
                    printf("%d %d\n",st,ed);
                }
            }else{
                now = 0;
                a++;b++;
                update(a,b,1,n,1);
                printf("%d\n",now);
            }
        }
        puts("");
    }
    return 0;
}
发表更新acm36 分钟读完 (大约5447个字)

[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;
}
发表更新acm6 分钟读完 (大约926个字)

51Nod-1593 公园晨跑

51Nod-1593 公园晨跑

题意

给定一个环，环上有$n$个点，每个点有一个权值$h$代表着如果从$i$到$j$的话，你必须加上$2h_i+2h_j$。并且加上他们之间的距离$L$。并且在环上会有一个区间被占用导致只能从另外一个方向走。

题解

线段树维护区间最大最小值的坐标和特判相同处理。

首先，面对环和方向性，我们可以把环拆成链式。形成一个$[1,n] \cup [1.n]$的区间对于$X,Y$的查找可以看成两种情况，

  • 一种是$X\leq Y$，那么我们寻找的范围就是$[Y+1,X+n-1]$。
  • 对于$X>Y$的情况，我们寻找的范围就是$[Y+1,X-1]$。

定义$d[x]$为$x$点到第一个点的距离(线性)。

对于给定的两个点$X,Y$，我们获得的权值是确定的，为$d[Y]-d[X]+2h[X]+2h[Y]$，我们可以将这个算式分为$X$部分和$Y$部分。于是我们就可以将式子转化为

$target = (d[Y]+2h[Y]) - (d[X]-2h[X])$

这个式子求最大值，就是对于每个点求第一部分的最大值和第二部分的最小值。之后由于$X != Y$，所以对于线段树维护的是区间内最大最小值的坐标。当坐标相同时，寻找次一级的最小值或者次一级的最大值。

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
#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 ll INF = 1e11;
//head
const int maxn = 2e5 + 10;
ll h[maxn],d[maxn],A[maxn],B[maxn];
int mmax[maxn<<2],mmin[maxn<<2];
template <class T>
bool read(T &x){
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-') op = 1;
        else if(c == EOF) return 0;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op) x = -x;
    return 1;
}
inline int Max(int a,int b){
    return A[a] > A[b] ? a : b;
}
inline int Min(int a,int b){
    return B[a] < B[b] ? a : b;
}
inline ll Mmax(ll a,ll b){
    return a>b?a:b;
}
int m,n;
void pushup(int rt){
    mmax[rt] = Max(mmax[rt<<1],mmax[rt<<1|1]);
    mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        mmax[rt] = l;
        mmin[rt] = l;
        return ;
    }
    int mid = (r+l)>>1;
    build(lson);build(rson);
    pushup(rt);
}
int query_max(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R) return mmax[rt];
    int mid = (l+r) >> 1;
    ll res = 0;
    if(L <= mid) res = Max(res,query_max(L,R,lson));
    if(mid < R) res = Max(res,query_max(L,R,rson));
    return res;
}
int query_min(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R) return mmin[rt];
    int mid = (l+r) >> 1;
    ll res = 0;
    if(L <= mid) res = Min(res,query_min(L,R,lson));
    if(mid < R) res = Min(res,query_min(L,R,rson));
    return res;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,2,n+2) read(d[i]),d[n+i] = d[i];
    rep(i,2,n*2+1) d[i] += d[i-1];
    rep(i,1,n+1){
        ll hh;read(hh);
        h[i] = h[i+n] = hh;
    }
    A[0] = -INF;B[0] = INF;
    rep(i,1,n+n+1){
        A[i] = 2*h[i] + d[i];
        B[i] = d[i] - 2*h[i];
    }
    build(1,n*2,1);
    while(m--){
        int l,r;read(l);read(r);
        if(l<=r){
            int st = query_max(r+1,l+n-1,1,2*n,1);
            int ed = query_min(r+1,l+n-1,1,2*n,1);
            ll ans;
            if(st == ed){
                int st1 = Max(query_max(st+1,l+n-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
                int ed1 = Min(query_min(ed+1,l+n-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
                ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
            }else ans = A[st] - B[ed];
            printf("%lld\n",ans);
        }else{
            int st = query_max(r+1,l-1,1,2*n,1);
            int ed = query_min(r+1,l-1,1,2*n,1);
            ll ans;
            if(st == ed){
                int st1 = Max(query_max(st+1,l-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
                int ed1 = Min(query_min(ed+1,l-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
                ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
            }else ans = A[st] - B[ed];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

reference:https://blog.csdn.net/ZLH_HHHH/article/details/74887389

关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×