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