uva 12299 线段树点相关的操作模板

http://uva.onlinejudge.org/index.php option=com_onlinejudge&Itemid=8&category=502&page=show_problem&problem=3720

唯一值得一说的就是shift，变成更新点就行

这道题主要是测试下我做的算法模板

先贴模板

/****************************************************************\
 2014.4 By Pilgrim  测试数据--uva 12299
 1、注意宏定义
 2、数组a里存储原始数据，从下标1到下标n
 3、使用时先调用build(1,n,1); MAXN是n的上限，在const int调整
 4、稍改动后可用于max,min,sum这些的单点查询，更新
    max：注意build的时候，最初赋为下限
    sum: 注意build的时候，最初赋为上限
    可以在query update 加参数kind，确定是查询max,min,sum，
    从而实现一棵线段树同时多种查询功能
 5、a[],n不可再用
\****************************************************************/

#define lson(i) l , mid , (i)*2
#define rson(i) mid + 1 , r , ((i)*2 +1)
#define ll rt*2
#define rr (rt*2+1)

const int MAXN = 100010;

struct Node{
    int l,r;
    int mmin;
}nodes[MAXN*4];

int a[MAXN],n;

void PushUp(int rt)
{
    nodes[rt].mmin = min(nodes[ll].mmin,nodes[rr].mmin);
}

void Build(int l,int r,int rt)
{
    nodes[rt].l = l;
    nodes[rt].r = r;
    nodes[rt].mmin = MAXN;/*******改***********/
    if(l == r)
    {
        nodes[rt].mmin = a[l];
        return;
    }
    int mid = (l+r)>>1;
    Build(lson(rt));
    Build(rson(rt));
    nodes[rt].mmin = min(nodes[ll].mmin,nodes[rr].mmin);
}

void Update(int rt, int p,int v)/*a[]中下标为p的值改为v*/
{
    if(nodes[rt].l == nodes[rt].r){nodes[rt].mmin = v;return;}
    int mid = (nodes[rt].l+nodes[rt].r)>>1;
    if(p<=mid)
    {
        Update(ll,p,v);
    }
    else
    {
        Update(rr,p,v);
    }
    PushUp(rt);
}

int Query(int l,int r,int rt)
{
    if(l == nodes[rt].l && r == nodes[rt].r)
    {
        return nodes[rt].mmin;
    }
    int mid=(nodes[rt].l+nodes[rt].r)>>1;
    if(r<=mid)
    {
        return Query(l,r,ll);
    }
    else
    {
        if(l>mid)
        {
           return Query(l,r,rr);
        }
        else
        {
           int tmp1 = Query(l,mid,ll);
           int tmp2 = Query(mid+1,r,rr);
           return min(tmp1,tmp2);
        }
    }
}

再贴代码

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define lson(i) l , mid , (i)*2 #define rson(i) mid + 1 , r , ((i)*2 +1) #define ll rt*2 #define rr (rt*2+1) const int MAXN = 100010; const int ORDERSIZE = 35; struct Node{ int l,r; int mmin; }nodes[MAXN*4]; int a[MAXN],shift[MAXN]; int n; void PushUp(int rt) { nodes[rt].mmin = min(nodes[ll].mmin,nodes[rr].mmin); } void Build(int l,int r,int rt) { nodes[rt].l = l; nodes[rt].r = r; nodes[rt].mmin = MAXN;////////////////////////////////////////////////////////// if(l == r) { nodes[rt].mmin = a[l]; return; } int mid = (l+r)>>1; Build(lson(rt)); Build(rson(rt)); nodes[rt].mmin = min(nodes[ll].mmin,nodes[rr].mmin); } void Update(int rt, int p,int v)/*下标为p的值改为v*/ { if(nodes[rt].l == nodes[rt].r){nodes[rt].mmin = v;return;} int mid = (nodes[rt].l+nodes[rt].r)>>1; if(p<=mid) { Update(ll,p,v); } else { Update(rr,p,v); } PushUp(rt); } int Query(int l,int r,int rt) { if(l == nodes[rt].l && r == nodes[rt].r) { return nodes[rt].mmin; } int mid=(nodes[rt].l+nodes[rt].r)>>1; if(r<=mid) { return Query(l,r,ll); } else { if(l>mid) { return Query(l,r,rr); } else { int tmp1 = Query(l,mid,ll); int tmp2 = Query(mid+1,r,rr); return min(tmp1,tmp2); } } } int main() { int q,t; int cnt = 0;/*记录需要移动的数量*/ char order[51]; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); Build(1,n,1); for(int i=0;i

uva 12299 线段树 点相关的操作模板