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;
}