HDU 5634 Rikka with Phi

Problem Description

Rikka and Yuta are interested in Phi function (which is known as Euler's totient function).

Yuta gives Rikka an array 

A[1..n] of positive integers, then Yuta makes 

m queries. 

There are three types of queries: 

1lr 

Change 

A[i] into 

φ(A[i]), for all 

i∈[l,r].

2lrx 

Change 

A[i] into 

x, for all 

i∈[l,r].

3lr 

Sum up 

A[i], for all 

i∈[l,r].

Help Rikka by computing the results of queries of type 3.

Input

T(T≤100) ——The number of the testcases. And there are no more than 2 testcases with 

n>105

For each testcase, the first line contains two numbers 

n,m(n≤3×105,m≤3×105)。

The second line contains 

n numbers 

A[i]

Each of the next 

m lines contains the description of the query. 

It is guaranteed that 

1≤A[i]≤107

Output

For each query of type 3, print one number which represents the answer.

Sample Input

1

10 10

56 90 33 70 91 69 41 22 77 45

1 3 9

1 1 10

3 3 8

2 5 6 74

1 1 8

3 1 9

1 2 10

1 4 9

2 8 8 69

3 3 9

Sample Output

80

122

86

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e7 + 10;
int T, euler[maxn], n, m, x, l, r, c;

void Init(){
  euler[1] = 1;
  for (int i = 2; i<maxn; i++) euler[i] = i;
  for (int i = 2; i<maxn; i++)
    if (euler[i] == i)
      for (int j = i; j<maxn; j += i) euler[j] = euler[j] / i*(i - 1);
}

struct Tree
{
  const static int maxn = 1e6 + 2e5 + 10;
  int F[maxn];
  LL sum[maxn];
  void build(int x, int l, int r)
  {
    if (l == r) { scanf("%d", &F[x]); sum[x] = F[x]; return; }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    if (F[x << 1] == F[x << 1 | 1]) F[x] = F[x << 1]; else F[x] = 0;
  }
  void pushdown(int x, int l, int mid, int r)
  {
    F[x << 1] = F[x << 1 | 1] = F[x];
    sum[x << 1] = (LL)F[x] * (mid - l + 1);
    sum[x << 1 | 1] = (LL)F[x] * (r - mid);
    F[x] = 0;
  }
  void make(int x, int l, int r, int ll, int rr, int c)
  {
    if (ll <= l&&r <= rr) { F[x] = c; sum[x] = (LL)(r - l + 1)*c; return; }
    int mid = l + r >> 1;
    if (F[x]) pushdown(x, l, mid, r);
    if (ll <= mid) make(x << 1, l, mid, ll, rr, c);
    if (rr > mid) make(x << 1 | 1, mid + 1, r, ll, rr, c);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    if (F[x << 1] == F[x << 1 | 1]) F[x] = F[x << 1]; else F[x] = 0;
  }
  void get(int x, int l, int r, int ll, int rr)
  {
    if (ll <= l&&r <= rr)
    {
      if (F[x]) { F[x] = euler[F[x]]; sum[x] = (LL)F[x] * (r - l + 1); return; }
      int mid = l + r >> 1;
      get(x << 1, l, mid, ll, rr);
      get(x << 1 | 1, mid + 1, r, ll, rr);
      sum[x] = sum[x << 1] + sum[x << 1 | 1];
      if (F[x << 1] == F[x << 1 | 1]) F[x] = F[x << 1]; else F[x] = 0;
      return;
    }
    int mid = l + r >> 1;
    if (F[x]) pushdown(x, l, mid, r);
    if (ll <= mid) get(x << 1, l, mid, ll, rr);
    if (rr > mid) get(x << 1 | 1, mid + 1, r, ll, rr);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    if (F[x << 1] == F[x << 1 | 1]) F[x] = F[x << 1]; else F[x] = 0;
  }
  LL putout(int x, int l, int r, int ll, int rr)
  {
    if (ll <= l&&r <= rr) return sum[x];
    int mid = l + r >> 1;
    LL ans = 0;
    if (F[x]) pushdown(x, l, mid, r);
    if (ll <= mid) ans+=putout(x << 1, l, mid, ll, rr);
    if (rr > mid) ans+=putout(x << 1 | 1, mid + 1, r, ll, rr);
    return ans;
  }
}tree;

int main()
{
  Init();
  cin >> T;
  while (T--)
  {
    scanf("%d%d", &n, &m);
    tree.build(1, 1, n);
    while (m--)
    {
      scanf("%d%d%d", &x, &l, &r);
      if (x == 1) tree.get(1, 1, n, l, r);
      if (x == 2) scanf("%d", &c), tree.make(1, 1, n, l, r, c);
      if (x == 3) printf("%lld\n", tree.putout(1, 1, n, l, r));
    }
  }
  return 0;
}