No Pain No Game

思路：数组data[]，从后往前遍历，遍历到data[i]的时候，枚举data[i]的约数，假设约数j；

pre[j]数组记录的是约数j最近出现的下标，那么,在询问的区间左端点等于i时，约数j影响的区间是pre[j]~最后，利用线段树更新；

代码：

1 #include 
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 const int maxn=50010;  7 int pre[maxn];//保存当前约数的最近位置  8 int data[maxn];  9 int tree[maxn*4];//线段树 10 int lz[maxn*4];//延迟数组 11 int res[maxn]; 12 struct node 13 { 14     int l; 15     int r; 16     int xh; 17 }que[maxn];//询问 18 bool cmp(struct node a,struct node b) 19 { 20     return a.l>b.l; 21 } 22 void push(int w) 23 { 24     tree[w]=max(tree[w<<1],tree[w<<1|1]); 25 } 26 void build(int l,int r,int w) 27 { 28     lz[w]=0; 29     tree[w]=1; 30     if(l==r) 31         return ; 32     int m=(l+r)/2; 33     build(l,m,w<<1); 34     build(m+1,r,w<<1|1); 35 } 36 void update(int l,int r,int w,int L,int R,int x) 37 { 38     if(L<=l&&R>=r) 39     { 40         lz[w]=max(lz[w],x);//标记 41         tree[w]=max(tree[w],x); 42         return ; 43     } 44     if(lz[w]!=0) 45     { 46          47         lz[w<<1]=max(lz[w<<1],lz[w]);//传递标记 48         lz[w<<1|1]=max(lz[w<<1|1],lz[w]); 49         tree[w<<1]=max(tree[w<<1],lz[w<<1]); 50         tree[w<<1|1]=max(tree[w<<1|1],lz[w<<1|1]); 51         lz[w]=0;//取消标记 52     } 53     int m=(l+r)>>1; 54     if(R<=m) 55         update(l,m,w<<1,L,R,x); 56     else if(L>m) 57         update(m+1,r,w<<1|1,L,R,x); 58     else 59     { 60         update(l,m,w<<1,L,m,x); 61         update(m+1,r,w<<1|1,m+1,R,x); 62     } 63     push(w); 64 } 65 int query(int l,int r,int w,int L,int R) 66 { 67     if(L<=l&&R>=r) 68     { 69         return tree[w]; 70     } 71     if(lz[w]!=0) 72     { 73         lz[w<<1]=max(lz[w<<1],lz[w]); 74         lz[w<<1|1]=max(lz[w<<1|1],lz[w]); 75         tree[w<<1]=max(tree[w<<1],lz[w<<1]); 76         tree[w<<1|1]=max(tree[w<<1|1],lz[w<<1|1]); 77         lz[w]=0; 78     } 79     int m=(l+r)>>1; 80     if(R<=m) 81         return query(l,m,w<<1,L,R); 82     else if(L>m) 83         return query(m+1,r,w<<1|1,L,R); 84     else 85         return max(query(l,m,w<<1,L,m),query(m+1,r,w<<1|1,m+1,R)); 86 } 87  88 int main() 89 { 90  91      92     int T; 93     scanf("%d",&T); 94     while(T--) 95     { 96         int n; 97         scanf("%d",&n); 98         int i,j; 99         for(i=1; i<=n; i++)100         {101             scanf("%d",&data[i]);102         }103         build(1,n,1);104         int Q;105         scanf("%d",&Q);106         for(i=0;i
          
           0; i--)//从右往左遍历115         {116             for(j=1; j*j<=data[i]; j++)//枚举约数117             {118                 if(data[i]%j==0)119                 {120                     if(pre[j]!=-1)121                     {122                         update(1,n,1,pre[j],n,j);123                     }124 125                     pre[j]=i;126                     int u=data[i]/j;127                     if(u!=j)128                     {129                         if(pre[u]!=-1)130                         {131                             update(1,n,1,pre[u],n,u);132                         }133 134                         pre[u]=i;135                     }136                 }137 138             }139             while(k