[HDU 5634] Rikka with Phi

维护一个数据结构，支持区间覆盖，区间取phi，区间查询和。
区间取phi，理论分析，对于一个偶数取phi变为原来的一半，奇数取phi变为偶数。所以最多log次，就可以将一个数变成1。而phi(1)=1，所以可以通过维护区间最大值，若一段区间最大值已经是1，那么就不必修改了，这个时候时间复杂度为\(O(\log^2n)\)
而两个操作结合起来，就有点麻烦，因为覆盖之后不好取phi，所以需要引入一个标记，记录一个区间所有值是否相等，这样的话一次覆盖最多遍历log个区间，修改复杂度也得到了保证。

#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<iostream>
#include<queue>
#include<cctype>
using namespace std;

#define A(x) cout << #x << " " << x << endl;
#define AA(x,y) cout << #x << " " << x << #y << " " << y << endl;
#define B cout << "Break" << endl;
#define ll long long
#define inf 1000000000

int read()
{
    int c = getchar();
    int x = 0,f = 1;
    while(!isdigit(c))
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c))
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return f * x;
}
#define N 300010
int sum[N << 2],lazy[N << 2],mx[N << 2],tag[N << 2],seq[N];
#define MAX 10000010
int pr[MAX],pn,phi[MAX],vis[MAX];
int n,m;
void sieve()
{
    phi[1] = 1;
    for(int i = 2;i <= MAX - 10;++i)
    {
        if(!vis[i])
        {
            phi[i] = i - 1;
            pr[++pn] = i;
        }
        for(int j = 1;j <= pn && i * pr[j] <= MAX - 10;++i)
        {
            vis[i * pr[j]] = 1;
            if(i % pr[j] == 0)
            {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
            phi[i * pr[j]] = phi[i] * phi[pr[j]];
        }
    }
}
#define mid (l + r >> 1)
#define ls x << 1,l,mid
#define rs x << 1 | 1,mid + 1,r
void push_up(int x)
{
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    mx[x] = max(mx[x << 1],mx[x << 1 | 1]);
    tag[x] = (tag[x << 1] && tag[x << 1 | 1] && mx[x << 1] == mx[x << 1 | 1]);
    return;
}
void build(int x,int l,int r)
{
    sum[x] = mx[x] = tag[x] = lazy[x] = 0;
    if(l == r)
    {
        sum[x] = mx[x] = seq[l];
        tag[x] = 1;
        return;
    }
    build(ls);
    build(rs);
    push_up(x);
}
void add(int x,int l,int r,int k)
{
    lazy[x] = mx[x] = k;
    tag[x] = 1;
    sum[x] = (r - l + 1) * k;
    return;
}
void push_down(int x,int l,int r)
{
    if(!lazy[x]) return;
    add(ls,lazy[x]);
    add(rs,lazy[x]);
    lazy[x] = 0;
    return;
}
void to_phi(int x,int l,int r,int p,int q)
{
    if(mx[x] <= 1) return;
    if(p <= l && r <= q && tag[x])
    {
        lazy[x] = mx[x] = phi[mx[x]];
        sum[x] = (r - l + 1) * mx[x];
        return;
    }
    push_down(x,l,r);
    if(p <= mid) to_phi(ls,p,q);
    if(q > mid) to_phi(rs,p,q);
    push_up(x);
    return;
}
void modify(int x,int l,int r,int p,int q,int k)
{
    if(p <= l && r <= q)
    {
        tag[x] = 1;
        lazy[x] = mx[x] = k;
        sum[x] = (r - l + 1) * k;
        return;
    }
    push_down(x,l,r);
    if(p <= mid) modify(ls,p,q,k);
    if(q > mid) modify(rs,p,q,k);
    push_up(x);
    return;
}
int query(int x,int l,int r,int p,int q)
{
    if(p <= l && r <= q) return sum[x];
    int ret = 0;
    push_down(x,l,r);
    if(p <= mid) ret += query(ls,p,q);
    if(q > mid) ret += query(rs,p,q);
    return ret;
}
int main()
{
    sieve();
    int T = read();
    while(T--)
    {
        int n = read(),m = read();
        for(int i = 1;i <= n;++i) seq[i] = read();
        build(1,1,n);
        while(m--)
        {
            int op = read(),l = read(),r = read();
            if(op == 1) to_phi(1,1,n,l,r);
            if(op == 2)
            {
                int k = read();
                modify(1,1,n,l,r,k);
            }
            if(op == 3) printf("%d\n",query(1,1,n,l,r));
        }

    }
}

[HDU 5634] Rikka with Phi

原文：https://www.cnblogs.com/lijilai-oi/p/12409521.html