No pain no game

区间最值 + 离线处理

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
#define lson rt << 1, l, mid           //左儿子：rt*2
#define rson rt << 1|1, mid + 1, r     //右儿子：rt*2+1
#define root 1, 1, N
const int MAXN = 5e4 + 5;
int T, N, A[MAXN], Q, pre[MAXN], Sum[MAXN << 2], ans[MAXN];
struct qeu {
  int l, r, id;
  bool operator < (const qeu & a) const {
    return r < a.r;
  }
} QS[MAXN];
vector<int>G[MAXN];
void init() {                          //求出所有的数字的因子，穷举法
  for(int i = 1; i < MAXN; i ++) {
    for(int j = i ; j < MAXN; j += i) {
      G[j].push_back(i);
    }
  }
}
void update(int p, int v, int rt, int l, int r) {       //pre，value，节点编号，左儿子，右儿子
  if(l == r) {                          //到达叶子节点
    Sum[rt] = max(Sum[rt], v);          //更新最大值
    return;
  }
  int mid = (l + r) >> 1;
  if(p <= mid) update(p, v, lson);      //递归左右子节点
  else update(p, v, rson);
  Sum[rt] = max(Sum[rt << 1], Sum[rt << 1|1]);          //该节点的值是左右子节点里的最大值
}
int query(int L, int R, int rt, int l, int r) {         //区间左，区间右，节点编号，左儿子，右儿子
  if(L <= l && r <= R) {                //完全覆盖
    return Sum[rt];                     //返回父节点
  }
  int mid = (l + r) >> 1;
  int ret = 0;
  if(L <= mid) ret = max(ret, query(L, R, lson));       //递归到最大公因数就返回，否则返回0
  if(R > mid) ret = max(ret, query(L, R, rson));
  return ret;
}
int main() {
  init();
  scanf("%d", &T);                      //测试次数
  while(T --) {
    scanf("%d", &N);                    //测试序列
    memset(Sum,0,sizeof(Sum));          //初始化0，（伪）建立线段树
    for(int i = 1; i <= N; i ++) {      //输入序列
      scanf("%d", &A[i]);
    }
    scanf("%d", &Q);                    //查询次数
    for(int i = 1; i <= Q; i ++) {      //离线处理
      scanf("%d%d", &QS[i].l, &QS[i].r);
      QS[i].id = i;
    }
    memset(pre, -1, sizeof(pre));       //初始化-1
    sort(QS + 1, QS + Q + 1);           //QS.r正序
    for(int i = 1, j = 1; i <= N && j <= Q; i ++) {
      for(int k = 0 ; k < G[A[i]].size(); k ++) {       //将序列里的元素因子单独遍历一遍
        int tmp = G[A[i]][k];           //元素里的因子
        if(pre[tmp] != -1) {            //有重复的因数
          update(pre[tmp], tmp, root);                  //更新节点
        }
        pre[tmp] = i;                   // 标记上当前因数
      }
      while(j <= Q && QS[j].r == i) {                   // 查询
        ans[QS[j].id] = query(QS[j].l, QS[j].r, root); 
        j ++;                           // 下一组
      }
    }
    for(int i = 1; i <= Q; i ++) {
      printf("%d\n", ans[i]);           //遍历输出结果
    }
  }
  return 0;
}

笔记：题意要求给出序列区间内的最大公因数，遇到计算量庞大使用离线，批量统一处理。解题思路：用穷举法得出“0 ~MAXN”的因数，QS[i]储存所有的查询空间，按照右区间安排查询顺序，序列里元素的因数出现过两次就放到线段树里，当元素满足查询区间就返回区间内的最大公因数