UVA12299 RMQ with Shifts 线段树查询单点更新

线段树的题目，不是特别难，掌握单点更新和区间查找即可，给一个数组，下标1到n,有一个shift操作，就是把它给你的下标最前面一个放到最后面一个，相应位置的值也发生改变，然后有询问query(l,r)求出闭区间[l,r]的最小值，因为shift这一命令语句题目说不超过30个字符，除去括号shift字符串还有逗号，数字部分最多也就13个，所以可以把这个强行用单点更新

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; const int N = 100000 + 5; typedef struct Node { int l,r,minn; }; Node tree[N * 6]; int a[N]; int Stack[N]; void clear() { memset(tree,0,sizeof(tree)); memset(a,0,sizeof(a)); memset(Stack,0,sizeof(Stack)); } void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; if(l == r) { tree[id].minn = a[l]; return; } int mid = (l + r) / 2; build(l,mid,id*2); build(mid+1,r,id*2 + 1); tree[id].minn = min(tree[id*2].minn,tree[id*2 + 1].minn); } int find(int l,int r,int id) { if(l == tree[id].l && r == tree[id].r) return tree[id].minn; int mid = (tree[id].l + tree[id].r)/2; if(r <= mid)return find(l,r,id*2); else if(mid < l)return find(l,r,id*2 + 1); return min(find(l,mid,id<<1),find(mid+1,r,id*2 + 1)); } void update(int pos,int val,int id) { if(tree[id].l == tree[id].r) { tree[id].minn = val; return; } int mid = (tree[id].l + tree[id].r) / 2; if(pos <= mid)update(pos,val,id*2); else update(pos,val,id*2 + 1); tree[id].minn = min(tree[id*2].minn,tree[id*2 + 1].minn); } int main() { int n,q; while(scanf(%d %d,&n,&q) ==2 ) { clear(); for(int i=1;i<=n;i++) scanf(%d,&a[i]); build(1,n,1); while(q--) { char c = '*'; int u,v; while(c != 'q' && c!= 's') c = getchar(); int mark = 5; while(mark--)getchar(); if(c == 'q') { scanf(%d,%d,&u,&v); printf(%d ,find(u,v,1)); continue; } int top = 0; while(true) { scanf(%d,&u); Stack[top++] = u; c = getchar(); if(c == ')')break; } for(int i=0;i

UVA12299 RMQ with Shifts 线段树查询 单点更新