hdu 4777_有一个长度为 n 的序列 a 。进行 m 次询问,每组询问中给定 l,r ,求有多少组 i,j

#include 
   
   
    
    
 
const int N = 200000 + 5;
 
int n, m;
int a[N], left[N], right[N];
int sum[N << 2], mark[N << 2];
int answer[N], pos[N];
std::vector 
    
    
     
      buffer[N];
std::vector 
     
     
      
       factors[N];
std::pair 
      
      
       
       
         , int> p[N]; void prepare() { for (int i = 2; i < N; i ++) if ((int)factors[i].size() == 0) { for (int j = i; j < N; j += i) { factors[j].push_back(i); } } } void up(int o) { sum[o] = sum[o << 1] + sum[o << 1 | 1]; } void down(int o, int l, int r) { int mid = (l + r) >> 1; sum[o << 1] += mark[o] * (mid - l + 1); sum[o << 1 | 1] += mark[o] * (r - mid); mark[o << 1] += mark[o]; mark[o << 1 | 1] += mark[o]; mark[o] = 0; } void update(int o, int l, int r, int L, int R, int x) { if (L <= l && R >= r) { mark[o] += x; sum[o] += x * (r - l + 1); return ; } if (mark[o] != 0) { down(o, l, r); } int mid = (l + r) >> 1; if (L <= mid) { update(o << 1, l, mid, L, R, x); } if (R > mid) { update(o << 1 | 1, mid + 1, r, L, R, x); } up(o); } int query(int o, int l, int r, int x) { if (l == r) { return sum[o]; } if (mark[o] != 0) { down(o, l, r); } int mid = (l + r) >> 1; if (x <= mid) { return query(o << 1, l, mid, x); } else { return query(o << 1 | 1, mid + 1, r, x); } } void work() { for (int i = 1; i <= n; i ++) { buffer[i].clear(); } for (int i = 1; i <= n; i ++) { buffer[left[i]].push_back(i); } int now = 0; for (int i = 1; i <= 4 * n; i ++) { sum[i] = 0; mark[i] = 0; } for (int i = 1; i <= n; i ++) { for (int j = 0; j < (int)buffer[i].size(); j ++) { int l = buffer[i][j]; int r = right[buffer[i][j]]; update(1, 1, n, l, r, 1); } while (now < m && p[now].first.first == i) { answer[p[now].second] = query(1, 1, n, p[now].first.second); now ++; } if (now == m) { return ; } update(1, 1, n, i, right[i], -1); } } int main() { prepare(); while (scanf("%d%d", &n, &m) == 2 && n + m) { for (int i = 1; i <= n; i ++) { scanf("%d", &a[i]); } int maxv = *std::max_element(a + 1, a + n + 1); std::fill(pos, pos + maxv + 1, 0); for (int i = 1; i <= n; i ++) { left[i] = 1; for (int j = 0; j < (int)factors[a[i]].size(); j ++) { int x = factors[a[i]][j]; left[i] = std::max(left[i], pos[x] + 1); pos[x] = i; } } std::fill(pos, pos + maxv + 1, n + 1); for (int i = n; i >= 1; i --) { right[i] = n; for (int j = 0; j < (int)factors[a[i]].size(); j ++) { int x = factors[a[i]][j]; right[i] = std::min(right[i], pos[x] - 1); pos[x] = i; } } for (int i = 0; i < m; i ++) { int l, r; scanf("%d%d", &l, &r); p[i].first = {l, r}; p[i].second = i; } std::sort(p, p + m); work(); for (int i = 0; i < m; i ++) { printf("%d\n", answer[i]); } } return 0; }