No Pain No Game

思路：数组data[]，从后往前遍历，遍历到data[i]的时候，枚举data[i]的约数，假设约数j；
pre[j]数组记录的是约数j最近出现的下标，那么,在询问的区间左端点等于i时，约数j影响的区间是pre[j]~最后，利用线段树更新；
代码：
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  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<Q;i++)
107         {
108             scanf("%d%d",&que[i].l,&que[i].r);
109             que[i].xh=i;
110         }
111         sort(que,que+n,cmp);
112         memset(pre,-1,sizeof(pre));
113         int k=0;
114         for(i=n; 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<Q&&que[k].l==i)//询问以i为左端点的最优解
140             {
141                 res[que[k].xh]=query(1,n,1,i,que[k].r);
142                 if(que[k].l==que[k].r)//注：左右端点相等时结果为0
143                 res[que[k].xh]=0;
144                 k++;
145             }
146         }
147         for(i=0;i<Q;i++)
148         {
149             printf("%d
",res[i]);
150         }
151 
152     }
153     return 0;
154 }
View Code