线段树水题-白红宇

线段树水题

阅读量：5089 次

发布时间：2019-06-13

本文共 1899 字，大约阅读时间需要 6 分钟。

1.洛谷p1351 https://www.luogu.org/problem/show?pid=1531

//单点修改区间询问 #include
     
      #include
      
       #include
       
        #define maxn 200001using namespace std;int n,m,x,y,z,ans1,ans2;char c;struct node{    int l,r,sum,max;}tree[maxn<<2];inline int init(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}void build(int now,int l,int r){    tree[now].l=l;tree[now].r=r;    if(l==r)    {        tree[now].sum=tree[now].max=init();        return;    }    int mid=(l+r)>>1;    build(now<<1,l,mid);build(now<<1|1,mid+1,r);    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;    tree[now].max=max(tree[now<<1].max,tree[now<<1|1].max);}int query(int now,int l,int r){    if(tree[now].l==l&&tree[now].r==r) return tree[now].max;    int mid=(tree[now].l+tree[now].r)>>1;    if(l>mid) return query(now<<1|1,l,r);    else if(r<=mid) return query(now<<1,l,r);    else return max(query(now<<1,l,mid),query(now<<1|1,mid+1,r));}int serch(int now,int pos){    if(tree[now].l==pos&&tree[now].r==pos) return tree[now].sum;    int mid=(tree[now].l+tree[now].r)>>1;    if(pos<=mid) return serch(now<<1,pos);    else if(pos>mid) serch(now<<1|1,pos);}void change(int now,int pos,int k){    int l=tree[now].l;int r=tree[now].r;    if(l==pos&&r==pos)    {        tree[now].sum=tree[now].max=k;        return;    }    int mid=(tree[now].l+tree[now].r)>>1;    if(pos>mid) change(now<<1|1,pos,k);    if(pos<=mid) change(now<<1,pos,k);    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;    tree[now].max=max(tree[now<<1].max,tree[now<<1|1].max);}int main(){    n=init();m=init();    build(1,1,n);    for(int i=1;i<=m;i++)    {        cin>>c;x=init();y=init();        if(c=='Q'){printf("%d\n",query(1,x,y));}        else if(serch(1,x)

转载于:https://www.cnblogs.com/L-Memory/p/6817937.html

你可能感兴趣的文章