Pot!!(2019银川G题)

链接:https://nanti.jisuanke.com/t/42387
题意:给定多个操作,MULTIPLY操作为:区间 全部乘于 ,MAX操作为:查询区间的分解质因数后单个质数的次数最高为多少
题解:乘于x相当于,2,3,5,7加若干值,所以写4个线段树,然后依次更新,查询

#include <bits/stdc++.h>
#define mid (left+right)/2
#define ls (2*rt)
#define rs ((2*rt)+1)
using namespace std;
const int N= 1e5+10;

//四个线段树分别维护2,3,5,7
struct str{
    int lazy;
    int num;
}tree1[N<<2],tree2[N<<2],tree3[N<<2],tree4[N<<2];


void pushdown(int rt){
    tree1[ls].lazy += tree1[rt].lazy;
    tree1[rs].lazy += tree1[rt].lazy;
    tree1[ls].num += tree1[rt].lazy;
    tree1[rs].num += tree1[rt].lazy;
    tree1[rt].lazy = 0;

    tree2[ls].lazy += tree2[rt].lazy;
    tree2[rs].lazy += tree2[rt].lazy;
    tree2[ls].num += tree2[rt].lazy;
    tree2[rs].num += tree2[rt].lazy;
    tree2[rt].lazy = 0;

    tree3[ls].lazy += tree3[rt].lazy;
    tree3[rs].lazy += tree3[rt].lazy;
    tree3[ls].num += tree3[rt].lazy;
    tree3[rs].num += tree3[rt].lazy;
    tree3[rt].lazy = 0;

    tree4[ls].lazy += tree4[rt].lazy;
    tree4[rs].lazy += tree4[rt].lazy;
    tree4[ls].num += tree4[rt].lazy;
    tree4[rs].num += tree4[rt].lazy;
    tree4[rt].lazy = 0;
}

void update(int rt,int left,int right,int l,int r,int c){
    if(left >= l && right <= r){
        if(c == 2){
            tree1[rt].lazy += 1;
            tree1[rt].num += 1;
        }else if(c == 3){
            tree2[rt].lazy += 1;
            tree2[rt].num += 1;
        }else if(c == 5){
            tree3[rt].lazy += 1;
            tree3[rt].num += 1;
        }else if(c == 7){
            tree4[rt].lazy += 1;
            tree4[rt].num += 1;
        }
        return;
    }
    pushdown(rt);
    if(l <= mid) update(ls,left,mid,l,r,c);
    if(r > mid) update(rs,mid+1,right,l,r,c);
    tree1[rt].num = max(tree1[ls].num,tree1[rs].num);
    tree2[rt].num = max(tree2[ls].num,tree2[rs].num);
    tree3[rt].num = max(tree3[ls].num,tree3[rs].num);
    tree4[rt].num = max(tree4[ls].num,tree4[rs].num);
}


int query(int rt,int left,int right,int l,int r){
    if(left >= l && right <= r){
        int ans = 0;
        ans = max(ans,tree1[rt].num);
        ans = max(ans,tree2[rt].num);
        ans = max(ans,tree3[rt].num);
        ans = max(ans,tree4[rt].num);
        return ans;
    }
    int ans = 0;
    pushdown(rt);
    if(l <= mid) ans = max(ans,query(ls,left,mid,l,r));
    if(r > mid) ans = max(ans,query(rs,mid+1,right,l,r));
    return ans;
}

void build(int rt,int left,int right){
    tree1[rt].lazy = tree1[rt].num = 0;
    if(left == right) return;
    build(ls,left,mid);
    build(rs,mid+1,right);
}

int main(){

    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--){
        char s[15];
        int l,r,x;
        scanf("%s%d%d",s,&l,&r);
        if(s[0] == 'M' && s[1] == 'U'){
            scanf("%d",&x);
            for(int i = 2;i <= x;i++){
                if(x%i == 0){
                    while(x%i==0){
                        update(1,1,n,l,r,i);
                        x /= i;
                    }
                }
            }
        }else printf("ANSWER %d\n",query(1,1,n,l,r));
    }
    return 0;
}