2016HUAS_ACM暑假集训2E

又是一个线段树的应用，不过跟上一题（D-排兵布阵）不同的是，这次是求某段区间上的最值，而不是某段区间和。当然，数据更新是必须的。D题注释已经很详细了，所以这题注释少点。

大致题意：给你N个已经排好的学生成绩，然后有M条指令，输出对应指令的结果。指令有两种：

1.Q i j：询问i到j的最值

2.U i j：把学生编号为i的成绩改为j

输入输出格式：

Sample Input

5 6 //第一行两个整数N,M，表示N个学生和M条指令( 0<N<=200000,0<M<5000 )

1 2 3 4 5 //第二行是N个学生的成绩（对应学生编号）

Q 1 5

U 3 6

Q 3 4

Q 4 5

U 2 9

Q 1 5

Sample Output

 #include<stdio.h>

 #include<string.h>

 int max(int a,int b)//首先定义一个取最大值的函数

 {

     return a>b?a:b;

 }

 struct tree

 {

     int l,r,s;

 };

 char s[];

 int m,n,x,y;

 tree t[];//一般存节点的数组是叶子节点的三倍就够了

 void Init(int l,int r,int k)//构造线段树

 {

     t[k].l=l;

     t[k].r=r;

     if(l==r)//叶子节点

     {

         int x;

         scanf("%d",&x);

         t[k].s=x;//输入该叶子节点（学生）的分数

         return ;

     }

     int mid=(l+r)/;

     Init(l,mid,k*);//构造左子树

     Init(mid+,r,k*+);//构造右子树

     t[k].s=max(t[k*].s,t[k*+].s);//更新父节点数据（取最大值）

 }

 void updata(int c,int x,int k)//数据的更新操作

 {

     if(t[k].l==t[k].r&&t[k].l==c)

     {

         t[k].s=x;

         return ;

     }

     if(c<t[k].l||c>t[k].r)

         return ;

     updata(c,x,k*);

     updata(c,x,k*+);

     t[k].s=max(t[k*].s,t[k*+].s);

 }

 int query(int l,int r,int k)//数据查询  注意范围落在哪个区间就行了

 {

     if(t[k].l==l&&t[k].r==r)

         return t[k].s;

     int mid=(t[k].l+t[k].r)/;

     if(r<=mid)

         return query(l,r,k*);

     else if(l>=mid+)

         return query(l,r,k*+);

     else

         return max(query(l,mid,k*),query(mid+,r,k*+));

 } 

 int main()

 {

     while(scanf("%d %d",&n,&m)!=EOF)

     {

         Init(,n,);

         while(m--)

         {

             scanf("%s %d %d",&s,&x,&y);

             if(s[]=='U')

                 updata(x,y,);

             else

                 printf("%d\n",query(x,y,));

         }

     }

     return ;

 }

巴特西

2016HUAS_ACM暑假集训2E - I Hate It

最新文章

热门文章