长乐7.18集训

线段树:

 

1.区间求和:http://noip.ybtoj.com.cn/contest/46/problem/1


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
#include<bits/stdc++.h>
using namespace std;

const int N=100005;
int n,m;
long long tree[N*4];

long long Query(int k,int l,int r,int x,int y)
{
    if(x<=l && y>=r) return tree[k];
    int mid=(l+r)/2;
    long long res=0;
    if(x<=mid) res+=Query(k*2,l,mid,x,y);
    if(y>mid) res+=Query(k*2+1,mid+1,r,x,y);
    return res;
}
void Change(int k,int l,int r,int x,int v)
{
    if(l==r)
    {
        tree[k]+=v;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid) Change(k*2,l,mid,x,v);
    else Change(k*2+1,mid+1,r,x,v);
    tree[k]=tree[k*2]+tree[k*2+1];
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int c,a,b;
        cin>>c>>a>>b;
        if(c==0)
        {
            Change(1,1,n,a,b);
        }
        else
        {
            cout<<Query(1,1,n,a,b)<<endl;
        }
    }
   

    return 0;
}

 

2.最大数:https://www.acwing.com/problem/content/1277/


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
#include<bits/stdc++.h>
using namespace std;

const int N=1000005;

int m,p;
struct node
{
    int l,r;
    int v;//区间[l,r]中的最大值
}tr[N*4];

void pushup(int u)//由子节点的信息,来计算父亲节点的信息
{
    tr[u].v=max(tr[u*2].v,tr[u*2+1].v);
}

void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r) return;
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
}

int query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].v;
    int mid=(tr[u].l+tr[u].r)/2;
    int v=0;
    if(l<=mid) v=query(u*2,l,r);
    if(r>mid) v=max(v,query(u*2+1,l,r));
    return v;
}

void modify(int u,int x,int v)
{
    if(tr[u].l==x && tr[u].r==x) tr[u].v=v;
    else
    {
        int mid=(tr[u].l+tr[u].r)/2;
        if(x<=mid) modify(u*2,x,v);
        else modify(u*2+1,x,v);
        pushup(u);
    }
}

int main()
{
    int n=0,last=0;
    cin>>m>>p;
    build(1,1,m);
   
    while(m--)
    {
        int x;
        char c;
        cin>>c>>x;
        if(c=='Q')
        {
            last=query(1,n-x+1,n);
            cout<<last<<endl;
        }
        else
        {
            modify(1,n+1,(last+x)%p);
            n++;
        }
    }
   
    return 0;
}

 

3.你能回答这些问题吗:https://www.acwing.com/problem/content/246/


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;

const int N=500005;

int n,m;
int a[N];
struct node
{
    int l,r;
    int sum;
    int lmax,rmax,tmax;
}tr[N*4];

void pushup(node &u,node &l,node &r)
{
    u.sum=l.sum+r.sum;
    u.lmax=max(l.lmax,l.sum+r.lmax);
    u.rmax=max(r.rmax,r.sum+l.rmax);
    u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
//重载函数 ↑↓
void pushup(int u)
{
    pushup(tr[u],tr[u*2],tr[u*2+1]);
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[r],a[r],a[r],a[r]};
    else
    {
        tr[u]={l,r};
        int mid=(l+r)/2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int x,int v)
{
    if(tr[u].l==x && tr[u].r==x) tr[u]={x,x,v,v,v,v};
    else
    {
        int mid=(tr[u].l+tr[u].r)/2;
        if(x<=mid) modify(u*2,x,v);
        else modify(u*2+1,x,v);
        pushup(u);
    }
}

node query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r) return tr[u];
    else
    {
        int mid=(tr[u].l+tr[u].r)/2;
        if(r<=mid) return query(u*2,l,r);
        else if(l>mid) return query(u*2+1,l,r);
        else
        {
            node left=query(u*2,l,r);
            node right=query(u*2+1,l,r);
            node res;
            pushup(res,left,right);
            return res;
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
   
    while(m--)
    {
        int k,x,y;
        cin>>k>>x>>y;
        if(k==1)
        {
            if(x>y) swap(x,y);
            cout<<query(1,x,y).tmax<<endl;
        }
        else
        {
            modify(1,x,y);
        }
    }
   

    return 0;
}

 

4.一个简单的整数问题2(即区间查改):https://www.acwing.com/problem/content/244/


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
#include<bits/stdc++.h>
using namespace std;

const int N=100005;

int n,m;
int a[N];
struct node
{
    int l,r;
    long long sum,add;
}tr[N*4];

void pushup(int u)
{
    tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}

void pushdown(int u)
{
    node &root=tr[u],&left=tr[u*2],&right=tr[u*2+1];
    if(root.add)
    {
        left.add+=root.add,left.sum+=(long long)(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(long long)(right.r-right.l+1)*root.add;
        root.add=0;
    }
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[r],0};
    else
    {
        tr[u]={l,r};
        int mid=(l+r)/2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l && tr[u].r<=r)
    {
        tr[u].sum+=(long long)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
    }
    else
    {
        pushdown(u);
        int mid=(tr[u].l+tr[u].r)/2;
        if(l<=mid) modify(u*2,l,r,d);
        if(r>mid) modify(u*2+1,l,r,d);
        pushup(u);
    }
}

long long query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
   
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
    long long sum=0;
    if(l<=mid) sum=query(u*2,l,r);
    if(r>mid) sum+=query(u*2+1,l,r);
    return sum;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
   
    while(m--)
    {
        char c;
        int l,r,d;
        cin>>c;
        if(c=='C')
        {
            cin>>l>>r>>d;
            modify(1,l,r,d);
        }
        else
        {
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }

    return 0;
}

 

The end.