算法练习-1

2023-12-10 15:44:57

?
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
#include<iostream>
#include<stdio.h>
using namespace std;
int sum;
int ans;
struct Tree
{
    int a,b;
    int sum;
    int ans;
    Tree *lchile,*rchile;
};
int swap(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}
Tree *build(int l,int r)
{
    Tree *root=new Tree;
    root->a=l;
    root->b=r;
    root->sum=0;
    root->ans=-1;
    root->lchile=NULL;
    root->rchile=NULL;
    if(l<r)
    {
        int mid=(l+r)>>1;
        root->lchile=build(l,mid);
        root->rchile=build(mid+1,r);
    }
    return root;
}
void insert(Tree *root,int l,int k)
{
    if((root->a==l)&&(root->b==l))
    {
        root->ans=k;
        root->sum=k;
        return ;
    }
    int mid=(root->a+root->b)>>1;
    if(mid>=l)
    {
        insert(root->lchile,l,k);
    }
    else
    {
        insert(root->rchile,l,k);
    }
    root->sum=root->lchile->sum+root->rchile->sum;
    root->ans=swap(root->lchile->ans,root->rchile->ans);
}
void search(Tree *root,int l,int r)
{
    if(root->a>=l&&root->b<=r)
    {
        if(root->ans>ans)
            ans=root->ans;
        sum+=root->sum;
        return ;
    }
    int mid=(root->a+root->b)>>1;
    if(mid>=r)
    {
        search(root->lchile,l,r);
    }
    else if(mid<l)
    {
        search(root->rchile,l,r);
    }
    else
    {
        search(root->lchile,l,mid);
        search(root->rchile,mid+1,r);
    }
}
int main()
{
    Tree *root=new Tree;
    int n,m,i,s,c,b,t;
    cin>>n>>m;
    root=build(1,n);
    for(i=1;i<=n;i++)
    {
        cin>>t;
        insert(root,i,t);
    }
    for(i=1;i<=m;i++)
    {
        int ch;
         cin>>ch;
        if(ch==1)
        {
            cin>>s>>b;
            insert(root,s,b);
        }
        else
        {
            sum=0;
            ans=-1;
            cin>>s>>b;
            search(root,s,b);
            if(ch==2)
                cout<<sum<<endl;
            if(ch==3)
                cout<<ans<<endl;
        }
    }
    return 0;
}

算法练习-1

上一篇：Ubuntu下解压rar文件的方法


下一篇：Hibernate逆向工程全过程