HDU 5381 The sum of gcd

Description

,the length of 

 is 

Let 

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: 

First line has one integers 

Second line has 

 integers 

Third line has one integers 

,the number of questions 

Next there are Q lines,each line has two integers 

,

Output

Sample Input

251 2 3 4 53

1 3

2 3

1 4

4

4 2 6 9

3

1 3

2 4

2 3

Sample Output

961618

23

10

求一個區間裡全部子區間的gcd和。

有離線和線上兩種方法。

線上可以直接對n個點建立線段樹，

每個節點記錄左右端點開始的全部gcd的情況。

由于gcd本身是log的，每個節點記錄的值的數量不會很多。

合并的時候統計一下大區間的gcd，和，以及新的左右情況。

這樣對于每個詢問可以直接找到區間合并起來就行了。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 9973;
const int N = 3e5 + 10;
int T, n, m, l, r;

int gcd(int x, int y)
{
  return x%y ? gcd(y, x%y) : y;
}

struct point
{
  int g;
  LL sum;
  vector<pii> l, r;
  void clear()
  {
    sum = 0; l.clear(); r.clear();
  }
  void get()
  {
    in(g); sum = g;
    l.pb(mp(g, 1));
    r.pb(mp(g, 1));
  }
}f[N], ans;

point merge(point a, point b)
{
  point f;  f.clear();
  f.g = gcd(a.g, b.g);
  f.sum = a.sum + b.sum;
  rep(i, 1, a.l.size()) f.l.pb(a.l[i - 1]);
  rep(i, 1, b.l.size())
  {
    int q = gcd(a.g, b.l[i - 1].ff);
    if (q == f.l[f.l.size() - 1].ff) f.l[f.l.size() - 1].ss += b.l[i - 1].ss;
    else f.l.pb(mp(q, b.l[i - 1].ss));
  }
  rep(i, 1, b.r.size()) f.r.pb(b.r[i - 1]);
  rep(i, 1, a.r.size())
  {
    int q = gcd(b.g, a.r[i - 1].ff);
    if (q == f.r[f.r.size() - 1].ff) f.r[f.r.size() - 1].ss += a.r[i - 1].ss;
    else f.r.pb(mp(q, a.r[i - 1].ss));
  }
  rep(i, 1, a.r.size()) rep(j, 1, b.l.size())
  {
    int k = gcd(a.r[i - 1].ff, b.l[j - 1].ff);
    f.sum += a.r[i - 1].ss* b.l[j - 1].ss * k;
  }
  return f;
}

void build(int x, int l, int r)
{
  f[x].clear();
  if (l == r) { f[x].get(); return; }
  int mid = l + r >> 1;
  build(lson);  build(rson);
  f[x] = merge(f[x << 1], f[x << 1 | 1]);
}

void query(int x, int l, int r, int ll, int rr)
{
  if (ll <= l&&r <= rr)
  {
    if (ans.g) ans = merge(ans, f[x]);
    else ans = f[x];
  }
  else
  {
    int mid = l + r >> 1;
    if (ll <= mid) query(lson, ll, rr);
    if (rr > mid) query(rson, ll, rr);
  }
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--)
    {
      scanf("%d%d", &l, &r);
      ans.g = 0;
      query(1, 1, n, l, r);
      printf("%lld\n", ans.sum);
    }
  }
  return 0;
}      

離線可以考慮用莫隊算法，不過還是線段樹效率更高。

考慮從左往右不斷加入新的數字對于之前答案的影響。

記目前放入的是第i個數，記線段樹上每個節點的值j的含義是以j為起點的,終點分别從j到i的gcd的和。

放入第i個數之前，從1到i-1的節點值分别是對應節點到i-1的和，

放入第i個數相當于對這些區間分别加了一個對應的gcd(a[j],a[j+1]...a[i])的值。

我們可以根據相同的gcd合并log的得到第i個數對應于前面的log種不同的gcd值，然後加到對應的區間上。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,int>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 9973;
const int N = 3e5 + 10;
int T, n, m, x[N], y[N];
pii g[N];
LL ans[N], f[N], a[N];

int gcd(int x, int y)
{
  return x%y ? gcd(y, x%y) : y;
}

bool cmp(int x, int y)
{
  return g[x].ss < g[y].ss;
}

void clear(int x, int l, int r)
{
  f[x] = a[x] = 0;
  if (l == r) return;
  int mid = l + r >> 1;
  clear(lson);  clear(rson);
}

void pushdown(int x, int l, int r)
{
  int mid = l + r >> 1;
  a[x << 1] += a[x];  a[x << 1 | 1] += a[x];
  f[x << 1] += a[x] * (mid - l + 1);
  f[x << 1 | 1] += a[x] * (r - mid);
  a[x] = 0;
}

LL get(int x, int l, int r, int ll, int rr)
{
  if (a[x]) pushdown(x, l, r);
  if (ll <= l&&r <= rr) return f[x];
  LL mid = l + r >> 1, res = 0;
  if (ll <= mid) res += get(lson, ll, rr);
  if (rr > mid) res += get(rson, ll, rr);
  return res;
}

void add(int x, int l, int r, int ll, int rr, int v)
{
  if (a[x]) pushdown(x, l, r);
  if (ll <= l&&r <= rr)
  {
    a[x] += v;  f[x] += 1LL * (r - l + 1)*v;
  }
  else
  {
    int mid = l + r >> 1;
    if (ll <= mid) add(lson, ll, rr, v);
    if (rr > mid) add(rson, ll, rr, v);
    f[x] = f[x << 1] + f[x << 1 | 1];
  }
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", &x[i]);
    scanf("%d", &m);
    rep(i, 1, m) { in(g[i].ff); in(g[i].ss); y[i] = i; }
    sort(y + 1, y + m + 1, cmp);
    clear(1, 1, n);
    stack<pii> a, b;
    for (int i = 1, j = 1; i <= n; i++)
    {
      a.push(mp(x[i], 1));
      while (!a.empty()) b.push(mp(gcd(a.top().ff, x[i]), a.top().ss)), a.pop();
      int bef = 0;
      while (!b.empty())
      {
        pii q = b.top();  b.pop();
        add(1, 1, n, bef + 1, bef + q.ss, q.ff);  bef += q.ss;
        if (!a.empty() && a.top().ff == q.ff) q.ss += a.top().ss, a.pop();
        a.push(q);
      }
      for (; j <= m&&g[y[j]].ss == i; j++)
      {
        ans[y[j]] = get(1, 1, n, g[y[j]].ff, i);
      }
    }
    rep(i, 1, m) printf("%lld\n", ans[i]);
  }
  return 0;
}