TOJ 4325 RMQ with Shifts（线段树的单点更新）

小鱼儿 2022-06-12 04:12 99阅读 0赞

## RMQ with Shifts ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 41 Accepted: 18  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

In the traditional RMQ (Range Minimum Query) problem, we have a static array A. Then for each query (L, R) (L<=R), we report the minimum value among A\[L\], A\[L+1\], …, A\[R\]. Note that the indices start from 1, i.e. the left-most element is A\[1\].

In this problem, the array A is no longer static: we need to support another operation shift(i1, i2, i3, …, ik) (i1<i2<...<ik, k>1): we do a left “circular shift” of A\[i1\], A\[i2\], …, A\[ik\].

For example, if A=\{6, 2, 4, 8, 5, 1, 4\}, then shift(2, 4, 5, 7) yields \{6, 8, 4, 5, 4, 1, 2\}. After that, shift(1,2) yields \{8, 6, 4, 5, 4, 1, 2\}.

## Input ##

There will be only one test case, beginning with two integers n, q (1<=n<=100,000, 1<=q<=120,000), the number of integers in array A, and the number of operations. The next line contains n positive integers not greater than 100,000, the initial elements in array A. Each of the next q lines contains an operation. Each operation is formatted as a string having no more than 30 characters, with no space characters inside. All operations are guaranteed to be valid. Warning: The dataset is large, better to use faster I/O methods.

## Output ##

For each query, print the minimum value (rather than index) in the requested range.

## Sample Input ![copy.gif][] ##

7 5
    6 2 4 8 5 1 4
    query(3,7)
    shift(2,4,5,7)
    query(1,4)
    shift(1,2)
    query(2,2)

##     ##

## Sample Output ##

1
    4
    6

题解：

题目很水，就是题目意思理解了半天，就是询问的话询问区间最小值，shift就是把shift中的坐标全部左移，比如shift（2,4,6）,那么a\[4\]就到a\[2\],a\[6\]就到a\[2\],a\[2\]就到a\[6\],就是一个单点更新加询问的题

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    const int N=100005;
    struct node
    {
        int l,r;
        int minn;//区间最小值
    }t[N*4];
    int a[N],d;
    void Build(int l,int r,int num)//日常建树
    {
        t[num].l=l;
        t[num].r=r;
        if(l==r)
        {
            scanf("%d",&t[num].minn);
            a[d]=t[num].minn;//用一个数组存起来到时候交换就方便了
            d++;
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
        t[num].minn=min(t[num*2].minn,t[num*2+1].minn);//更新
    }
    int query(int l,int r,int num)//日常询问
    {
        if(l==t[num].l&&r==t[num].r)
        {
            return t[num].minn;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            return query(l,r,num*2);
        else if(l>mid)
            return query(l,r,num*2+1);
        else
        {
            return min(query(l,mid,num*2),query(mid+1,r,num*2+1));
        }
    }
    void update(int pos,int x,int num)//日常更新
    {
        if(t[num].l==pos&&t[num].r==pos)
        {
            t[num].minn=x;
            return;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(pos<=mid)
            update(pos,x,num*2);
        else
        {
            update(pos,x,num*2+1);
        }
        t[num].minn=min(t[num*2].minn,t[num*2+1].minn);
    }
    int main()
    {
        int n,q,i,j,l,r,tag,tot;
        d=1;
        int b[35];
        char s[105];
        scanf("%d%d",&n,&q);
        Build(1,n,1);//日常建树
        for(i=0;i<q;i++)
        {
            tot=0;
            memset(b,0,sizeof(b));//用于保存区间数据
            scanf("%s",s);//拆一下字符串
            if(s[0]=='q')
                tag=0;
            else
                tag=1;
            for(j=0;j<strlen(s);j++)//理解下拆
            {
                if(s[j]>='0'&&s[j]<='9')
                {
                    b[tot]=b[tot]*10+s[j]-'0';
                }
                else if(s[j]==','||s[j]==')')
                {
                    tot++;
                }
            }
            if(!tag)//如果是询问
            {
                printf("%d\n",query(b[0],b[1],1));
            }
            else//更新
            {
                update(b[tot-1],a[b[0]],1);//先更新最后一个
                for(j=1;j<tot;j++)//前面的覆盖掉后面的
                {
                    update(b[j-1],a[b[j]],1);
                }
                int temp=a[b[0]];
                for(j=0;j<tot-1;j++)//更新下数组
                {
                    a[b[j]]=a[b[j+1]];
                }
                a[b[tot-1]]=temp;
            }
        }
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1260&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1260&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1260&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif