UVA 12299 线段树 （ 单点跟新 ， 区间查询）

题目链接：题意：在传统的RMQ的基础上加上一个操作：shift(i1,i2,i3...ik),表示将这些元素，依次向左移动一位（训练指南247页）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int maxn=100000+5;

int data[4*maxn],x[50],nsize,n,q;

char s[50];

void update(int k,int val)

{

    k+=nsize-2;

    data[k]=val;

    while(k>0)

    {

        k=(k-1)/2;

        data[k]=min(data[2*k+1],data[2*k+2]);

    }

}//第k个位置改为val

void build(int k,int l,int r)

{

   MM(data,inf);

   for(int i=l;i<r;i++)

    {

       scanf("%d",&data[nsize-2+i]);

       update(i,data[nsize-2+i]);

    }//直接读入节点的值，然后再向上更新

}

int query(int k,int l,int r,int a,int b)

{

    if(a<=l&&r<=b) return data[k];

    else if(r>a&&l<b)

    {

        int x=query(2*k+1,l,(l+r)>>1,a,b);

        int y=query(2*k+2,(l+r)>>1,r,a,b);

        return min(x,y);

    }

    else return inf;

}

int main()

{

    while(~scanf("%d %d",&n,&q))

    {

       for(int i=0;;i++)

       if((1<<i)>=n) {nsize=(1<<i);break;}//满二叉树的最下面一层

       build(0,1,nsize+1);

       for(int k=1;k<=q;k++)

       {

           scanf("%s",s);

           int len=strlen(s),cnt=0;

           if(s[0]=='s')

           {

               int cnt=0;

               for(int i=0;i<len;i++)

               {

                    int temp=0,flag=0;

                    while(s[i]>='0'&&s[i]<='9')

                        {

                            temp=temp*10+s[i]-'0';

                            i++;

                            flag=1;

                        }

                    if(flag) x[++cnt]=temp;

               }

              int val=data[nsize-2+x[1]];

               for(int i=1;i<=cnt-1;i++)

                   {

                       update(x[i],data[nsize-2+x[i+1]]);

                   }

               update(x[cnt],val);

           }

           else if(s[0]=='q')

           {

               int cnt=0;

               for(int i=0;i<len;i++)

               {

                    int temp=0,flag=0;

                    while(s[i]>='0'&&s[i]<='9')

                        {

                            temp=temp*10+s[i]-'0';

                            i++;

                            flag=1;

                        }

                    if(flag) x[++cnt]=temp;

               }

               printf("%d\n",query(0,1,nsize+1,x[1],x[2]+1));

           }

       }

    }

    return 0;

}

　　分析：看清题，字符串长度最多才30，直接暴力单点更新就好了，整理了下线段树模版，挑战的风格

真奇葩