SWUST 2530_牛客博客

公元2047年，人类已经无法阻止Ceph入侵地球了！上决╇ф凭借着他的黑科技，在公元2023年研制出了Nanosuit 1.0。二十三年过去了，Nanosuit已经进化到了Nanosuit 3.0版本，具有超强的隐身、护甲、力量等2015年的人不可想象的超人类功能，而且配备了最强大的武器：狩猎弓。上决╇ф为了拯救世界，决定装备上最强的Nanosuit 3.0成为Prophet。

上图为上决╇ф在SWUST之战中使用狩猎弓与很多的Ceph进行战斗，我们可以很清楚地看到，Ceph居然很***地站成了一排，毕竟外星人的世界我们懂不起。再看看，中间那个，体积这么大，肯定攻击力不同寻常，一定要先把这个Ceph干掉！但是，看下一张图，Nanosuit 3.0面罩反射的图:

这是有多少Ceph？不多，也就不超过100000只嘛。拿着狩猎弓慢慢射就行了。

现在的问题是，在这排成一排的Ceph中，上决╇ф想知道，在某个区间内，战斗力最强的Ceph在什么位置，以方便做出作战方案。但是，Ceph毕竟是外星人，战斗力是会变的！我们需要及时第更新数据，告诉上决╇ф他想知道的区间内最强Ceph的位置。

What are you prepared to sacrifice?

第一行，是一个正整数T，表示测试的组数。
对于每一组测试，第一行是一个正整数n，m（1 <= n <= 100000）。代表Ceph的数目和操作次数。
接下来一排，有n个正整数数Ai，（1 <= Ai <= 1000000），分别代表从左往右第i只Ceph的战斗力。
接下来是m次操作。
每次操作为一行，每行有三个正整数op a b。op只可能为1或者2。当op=1时，为询问区间[a,b]内战斗力最强Ceph的位置（1 <= a <= b <= n）。当op=2时，表示在a位置的Ceph战斗力变成了b（1 <= a <=n,1 <= b <= 1000000）。

对于每一次询问，输入区间内最强Ceph 的位置，如果区间内有多个最强Ceph，输入坐靠左边的那个位置。

1
3

题意：中问题，题意自看

思路：明显线段树，这里是查询一个区间里最值靠左的位置，直接记录一下区间最值和位置即可，放在线段树里面更新即可。

AC代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int nn = 100005;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int A[nn];
struct node{
   int l,r;
   int pos,ms;
}Tree[nn<<2];
//void Push_Up(int rt)
//{
//    Tree[rt].ms = max(Tree[rt<<1].ms,Tree[rt<<1|1].ms);
//    if(Tree[rt].ms==Tree[rt<<1].ms)
//    {
//        Tree[rt].pos = Tree[rt<<1].pos;
//    }
//    else
//    {
//        Tree[rt].pos = Tree[rt<<1|1].pos;
//    }
//}
void Push_Up(node &fa,node &ls,node &rs)
{
    fa.l=ls.l,fa.r=rs.r;
    fa.ms=max(ls.ms,rs.ms);
    if(fa.ms==ls.ms)
    {
        fa.pos=ls.pos;
        return ;
    }
    fa.pos=rs.pos;
}
void Build(int l,int r,int rt)
{
    Tree[rt].l=l,Tree[rt].r=r;
    if(l==r)
    {
        Tree[rt].ms = A[l];
        Tree[rt].pos = l;
        return ;
    }
    int m = (l+r)>>1;
    Build(lson);
    Build(rson);
    Push_Up(Tree[rt],Tree[rt<<1],Tree[rt<<1|1]);
}
void Update(int pos,int val,int rt)
{
    if(Tree[rt].l==Tree[rt].r)
    {
        Tree[rt].ms = val;
        return ;
    }
    int m =(Tree[rt].l+Tree[rt].r)>>1;
    if(pos<=m)
        Update(pos,val,rt<<1);
    else
        Update(pos,val,rt<<1|1);
    Push_Up(Tree[rt],Tree[rt<<1],Tree[rt<<1|1]);
}
//int query_ans(int l,int r,int rt)
//{
//    if(l<=Tree[rt].l&&Tree[rt].r<=r)
//    {
//        return Tree[rt].pos;
//    }
//    int t=0;
//    int m =(Tree[rt].l+Tree[rt].r)>>1;
//    node tmp[3];
//    if(l<=m) tmp[1].pos = query_ans(l,r,rt<<1),t++;
//    if(m<r)  tmp[2].pos = query_ans(l,r,rt<<1|1),t+=2;
//    if(t<3)return tmp[t].pos;
//    Push_Up(tmp[0],tmp[1],tmp[2]);
//    return tmp[0].pos;
//}
node query(int id,int l,int r)
{
    if(l<=Tree[id].l&&Tree[id].r<=r)
        return Tree[id];
    int mid=(Tree[id].l+Tree[id].r)>>1;
    node tmp[3];
    int t=0;
    if(mid>=l)
        tmp[1]=query(id<<1,l,r),t++;
    if(mid<r)
        tmp[2]=query(id<<1|1,l,r),t+=2;
    if(t<3)
        return tmp[t];
    Push_Up(tmp[0],tmp[1],tmp[2]);
    return tmp[0];
}
int main()
{
    int tt,n,q;
    int op,a,b;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
            scanf("%d",&A[i]);
        Build(1,n,1);
        while(q--)
        {
            scanf("%d%d%d",&op,&a,&b);
            if(op==1)
            {
                node ans=query(1,a,b);
                printf("%d\n",ans.pos);
            }
            else
                Update(a,b,1);
        }
    }
    return 0;
}

SWUST 2530

Input

Output