HDU 4630 No Pain No Game 树状数组+离线查询

思路参考这里。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 const int MAXN = 50010;
  9 
 10 struct node
 11 {
 12     int l, r;
 13     int idx;
 14 };
 15 
 16 node Qry[MAXN];  //查询
 17 int C[MAXN];     //树状数组
 18 int vis[MAXN];   // i 的倍数上一次出现的位置
 19 int num[MAXN];   //原数组
 20 int ans[MAXN];   //答案
 21 int N, Q;
 22 
 23 bool cmp( node a, node b )
 24 {
 25     return a.l > b.l;
 26 }
 27 
 28 int lowbit( int x )
 29 {
 30     return x & (-x);
 31 }
 32 
 33 int query( int x )
 34 {
 35     int res = 0;
 36     while ( x > 0 )
 37     {
 38         res = max( res, C[x] );
 39         x -= lowbit(x);
 40     }
 41     return res;
 42 }
 43 
 44 void Add( int x, int val )
 45 {
 46     while ( x <= N )
 47     {
 48         C[x] = max( C[x], val );
 49         x += lowbit(x);
 50     }
 51     return;
 52 }
 53 
 54 int main()
 55 {
 56     int T;
 57     scanf( "%d", &T );
 58     while ( T-- )
 59     {
 60         scanf( "%d", &N );
 61         for ( int i = 1; i <= N; ++i )
 62             scanf( "%d", &num[i] );
 63 
 64         scanf( "%d", &Q );
 65         for ( int i = 0; i < Q; ++i )
 66         {
 67             scanf("%d%d", &Qry[i].l, &Qry[i].r );
 68             Qry[i].idx = i;
 69         }
 70 
 71         sort( Qry, Qry + Q, cmp );
 72         memset( C, 0, sizeof(C) );
 73         memset( vis, 0, sizeof(vis) );
 74 
 75         int i = 0, j = N;
 76         while ( i < Q )
 77         {
 78             while ( j > 0 && j >= Qry[i].l )
 79             {
 80                 for ( int k = 1; k*k <= num[j]; ++k )
 81                 {
 82                     if ( num[j] % k == 0 )
 83                     {
 84                         if ( vis[k] )
 85                         {
 86                             Add( vis[k], k );
 87                         }
 88                         vis[k] = j;
 89 
 90                         int tmp = num[j] / k;
 91                         if ( tmp != k )
 92                         {
 93                             if ( vis[tmp] )
 94                             {
 95                                 Add( vis[tmp], tmp );
 96                             }
 97                             vis[tmp] = j;
 98                         }
 99                     }
100                 }
101                 --j;
102             }
103 
104             ans[ Qry[i].idx ] = query( Qry[i].r );
105             ++i;
106         }
107 
108         for ( int i = 0; i < Q; ++i )
109         printf( "%d
", ans[i] );
110     }
111     return 0;
112 }

n个数，如果把n个数的约数全部写出来。查询[l,r]之间的gcd的最大值，就相当于找一个最大的数，使得这个数是[l,r]之间至少是两个的约数。

对于一个数n,在sqrt(n)内可以找出所有约数。

我的做法是对查询进行离线处理。

将每个查询按照 l 从大到小排序。

然后 i 从 n~0 ,表示从后面不断扫这些数。

对于数a[i],找到a[i]的所有约数，对于约数x,在x上一次出现的位置加入值x.

这样的查询的时候，只要查询前 r 个数的最大值就可以了。