HDU 4902 (线段树）

Problem Nice boat（HDU 4902）

题目大意　

　　维护一个序列，两种操作。

　　第一种操作，将一段区间[l,r]赋值为x。

　　第二种操作，将一段区间[l,r]中大于等于x的数与x求gcd。

　　询问所有操作结束后的序列。

解题分析

　　用线段树开一个标记same，表示这段区间中的数是否相同，若相同则为该数，否则为-1。

　　对于第二种操作，对于覆盖区间内的same不为-1的子区间暴力修改。

　　虽然时限有15s，但貌似跑得挺快的，只用了1s，不知是数据水还是什么缘故。

参考程序

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define N 100008

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 int same[N*];

 int n;

 int gcd(int x,int y){

     return y ? gcd(y,x % y): x;

 }

 void pushup(int rt){

     if (same[rt<<]==same[rt<<|]) same[rt]=same[rt<<];

     else same[rt]=-;

 }

 void pushdown(int rt){

     if (~same[rt]){

         same[rt<<]=same[rt<<|]=same[rt];

         same[rt]=-;

     }

 }

 void build(int l,int r,int rt){

     same[rt]=-;

     if (l==r){

         scanf("%d",&same[rt]);

         return;

     }

     int m=(l+r) / ;

     build(lson);

     build(rson);

     pushup(rt);

 }

 void update_1(int L,int R,int val,int l,int r,int rt){

     if (L<=l && r<=R){

         same[rt]=val;

         return;

     }

     pushdown(rt);

     int m=(l+r) /;

     if (L<=m) update_1(L,R,val,lson);

     if (m< R) update_1(L,R,val,rson);

     pushup(rt);

 }

 void update_2(int L,int R,int val,int l,int r,int rt){

     if (L<=l && r<=R){

         if (~same[rt]){

             if (same[rt]>=val) same[rt]=gcd(same[rt],val);

             return;

         }

     }

     pushdown(rt);

     int m=(l+r) /;

     if (L<=m) update_2(L,R,val,lson);

     if (m< R) update_2(L,R,val,rson);

     pushup(rt);

 }

 void query(int l,int r,int rt){

     if (l==r){

         printf("%d ",same[rt]);

         return;

     }

     pushdown(rt);

     int m=(l+r) /  ;

     query(lson);

     query(rson);

 }

 int main(){

     int T;

     scanf("%d",&T);

     while (T--){

         scanf("%d",&n);

         build(,n,);

         int type,a,b,val,q;

         scanf("%d",&q);

         while (q--){

             scanf("%d %d %d %d",&type,&a,&b,&val);

             if (type==) update_1(a,b,val,,n,);

             if (type==) update_2(a,b,val,,n,);

         }

         query(,n,);

         printf("%\n");

     }

 }

巴特西

HDU 4902 (线段树）

最新文章

热门文章