[luoguP4256]【公主の#19准备月考】

发布于 2018-03-03  27 次阅读



题目(洛谷)
 
首先看题,求区间gcd和lcm,我们可以将这个区间内的每个数分解质因数,gcd的话对每个质数个数取min,lcm的话取max,然而直接线段树上每个节点存该质数出现多少次的话铁定MLE。
这题的数据范围很神奇:每个值在[1,100]以内,而且题目只让求gcd和lcm(S操作可以通过求gcd求得),所以这就启发我们:将质数压起来。
我们发现:2^6=64, 2^7=128>100,所以一个区间内2的个数不超过6,而6可以用三个二进制位表示(6=4+2+0,即110);同理,3^4=81, 3^5>100,所以一个区间内3的个数不超过4,也用三个二进制位表示(4=4+0+0,即100);这样以此类推,可以得到一个区间内所有质数及其个数可以用31个二进制位表示。
而这31个二进制位,正好对应一个int的范围。所以每个节点存两个int:lcm和gcd,表示当前区间取gcd时的质数及其个数,取lcm时的质数及其个数。
然后就是普通的区间修改、区间查询了。不过还是有一些细节要注意。
...而且我被我一开始的大常数吓着了QAQ

#include <stdio.h>
#include <string.h>
#include <cctype>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
    e=0;int ck=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ck=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
    e*=ck;
}
inline int max(int a,int b){if(a>b)return a;else return b;}
inline int min(int a,int b){if(a>b)return b;else return a;}
const int N=300050;int p;
inline int mi(int a,int b){ //快速幂
    int ret=1;
    while(b){
        if(b&1)ret=(ret*a
        a=(a*a
        b>>=1;
    }
    return ret;
}
int n,Q,a[N],b[25],c1[25],c2[25],cnt[25];
//cnt,c1,c2都是用于保存当前值分解质因数后每个质数出现次数,
//不同地方用的数组不同
//a数组为原数组,b数组含义见main函数
int pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};//素数打表
#define ls id<<1
#define rs id<<1|1
inline int cal(int tmp){ //对当前数分解质因数
    int i=0;memset(cnt,0,sizeof cnt);
    while(tmp>1){
        if(tm
            tmp/=pri[i];
            cnt[i]++;
            continue;
        }
        i++;
    }
    int v=0;
    for(register int i=0;i<=24;++i)v|=(cnt[i]<<b[i]);
    return v;
}
/*线段树开始*/
struct seg{
    int l,r;
    int gcd,lcm,lazy;
}t[N<<2];
inline int callcm(int v1,int v2){ //对v1和v2求lcm
    int ret=0,p1,p2;memset(c1,0,sizeof c1);memset(c2,0,sizeof c2);memset(cnt,0,sizeof cnt);
    c1[0]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;
    c1[1]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;
    c1[2]+=(1&v1)+(2&v1);v1>>=2;
    c1[3]+=(1&v1)+(2&v1);v1>>=2;
    for(register int i=p1=4;i<=24;++i,++p1){c1[i]+=(v1&1);v1>>=1;if(!v1)break;}if(p1==25)--p1;
    c2[0]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;
    c2[1]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;
    c2[2]+=(1&v2)+(2&v2);v2>>=2;
    c2[3]+=(1&v2)+(2&v2);v2>>=2;
    for(register int i=p2=4;i<=24;++i,++p2){c2[i]+=(v2&1);v2>>=1;if(!v2)break;}if(p2==25)--p2;
    int mx=max(p1,p2);
    for(register int i=0;i<=mx;++i)cnt[i]=max(c1[i],c2[i]);
    for(register int i=0;i<=mx;++i)ret|=(cnt[i]<<b[i]);
    return ret;
}
inline int calgcd(int v1,int v2){ //对v1和v2求gcd
    int ret=0,p1,p2;memset(c1,0,sizeof c1);memset(c2,0,sizeof c2);memset(cnt,0,sizeof cnt);
    c1[0]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;//质数2占的位
    c1[1]+=(1&v1)+(2&v1)+(4&v1);v1>>=3;//质数3占的位
    c1[2]+=(1&v1)+(2&v1);v1>>=2;//质数5占的位
    c1[3]+=(1&v1)+(2&v1);v1>>=2;//质数7占的位
    for(register int i=p1=4;i<=24;++i,++p1){c1[i]+=(v1&1);v1>>=1;if(!v1)break;}if(p1==25)--p1;
    c2[0]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;//质数2占的位
    c2[1]+=(1&v2)+(2&v2)+(4&v2);v2>>=3;//质数3占的位
    c2[2]+=(1&v2)+(2&v2);v2>>=2;//质数5占的位
    c2[3]+=(1&v2)+(2&v2);v2>>=2;//质数7占的位
    for(register int i=p2=4;i<=24;++i,++p2){c2[i]+=(v2&1);v2>>=1;if(!v2)break;}if(p2==25)--p2;
    int mn=min(p1,p2);
    for(register int i=0;i<=mn;++i)cnt[i]=min(c1[i],c2[i]);
    for(register int i=0;i<=mn;++i)ret|=(cnt[i]<<b[i]);
    return ret;
}
inline void pushup(int id){
    t[id].gcd=calgcd(t[ls].gcd,t[rs].gcd);
    t[id].lcm=callcm(t[ls].lcm,t[rs].lcm);
}
inline void pushdown(int id){
    if(t[id].lazy){
        t[ls].lazy=t[rs].lazy=t[id].lazy;
        if(t[id].lazy==1)t[ls].gcd=t[ls].lcm=t[rs].gcd=t[rs].lcm=0;
		//若当前值为1,则gcd和lcm都为1,但线段树中的gcd和lcm中存的都是质数,
		//所以将值设为0
        else t[ls].gcd=t[ls].lcm=t[rs].gcd=t[rs].lcm=cal(t[id].lazy);
        t[id].lazy=0;
    }
}
void build(int l,int r,int id){ //线段树建树
    t[id].l=l,t[id].r=r;t[id].lazy=0;
    if(l==r){
        if(a[l]==1){t[id].gcd=t[id].lcm=0;return;}
        t[id].gcd=t[id].lcm=cal(a[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);build(mid+1,r,rs);
    pushup(id);
}
void change(int L,int R,int v,int vv,int id){ //v为要改变的值,vv为v分解质因数后的值
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R){
        t[id].lazy=v;
        if(v==1){t[id].gcd=t[id].lcm=0;return;}
        t[id].gcd=t[id].lcm=vv;
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)change(L,R,v,vv,ls);
    else if(L>mid)change(L,R,v,vv,rs);
    else{
        change(L,mid,v,vv,ls);
        change(mid+1,R,v,vv,rs);
    }
    pushup(id);
}
int qgcd(int L,int R,int id){ //查询gcd
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R)return t[id].gcd;
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)return qgcd(L,R,ls);
    else if(L>mid)return qgcd(L,R,rs);
    else return calgcd(qgcd(L,mid,ls),qgcd(mid+1,R,rs));
}
int qlcm(int L,int R,int id){ //查询lcm
    int l=t[id].l,r=t[id].r;
    if(l>=L&&r<=R)return t[id].lcm;
    pushdown(id);
    int mid=(l+r)>>1;
    if(R<=mid)return qlcm(L,R,ls);
    else if(L>mid)return qlcm(L,R,rs);
    else return callcm(qlcm(L,mid,ls),qlcm(mid+1,R,rs));
}
/*线段树结束*/
int main(){
    b[0]=0,b[1]=3;b[2]=6,b[3]=8;int bit=10;
    for(register int i=4;i<=24;++i)b[i]=bit++; //计算当前质数在二进制位上的位置
    read(n),read(Q);
    for(register int i=1;i<=n;++i)read(a[i]);
    build(1,n,1); //建树
    while(Q--){
        char opt[2];int x,y;
        scanf(
        switch(opt[0]){
            case 'L':{
                int tmp=qlcm(x,y,1),ans=1,pos;memset(cnt,0,sizeof cnt);
                //pos为常数优化用的变量
                cnt[0]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数2占的位
                cnt[1]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数3占的位
                cnt[2]+=(1&tmp)+(2&tmp);tmp>>=2;//质数5占的位
                cnt[3]+=(1&tmp)+(2&tmp);tmp>>=2;//质数7占的位
                for(register int i=pos=4;i<=24;++i,++pos){
                    cnt[i]+=(tmp&1);tmp>>=1;if(!tmp)break;
                }
                if(pos==25)--pos;
                /*这一部分为神奇的常数优化,因为从第5个质数开始,一个区间内仅会出现1个,所以不需要快速幂计算*/
                ans*=mi(pri[0],cnt[0]);
                ans*=mi(pri[1],cnt[1]);
                ans*=mi(pri[2],cnt[2]);
                ans*=mi(pri[3],cnt[3]);
                an
                for(register int i=4;i<=pos;++i){
                	if(cnt[i])ans*=pri[i],an
				}
				/*常数优化结束*/
                printf(
                break;
            }
            case 'G':{
                int tmp=qgcd(x,y,1),ans=1,pos;memset(cnt,0,sizeof cnt);
                //pos为常数优化用的变量
                cnt[0]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数2占的位
                cnt[1]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数3占的位
                cnt[2]+=(1&tmp)+(2&tmp);tmp>>=2;//质数5占的位
                cnt[3]+=(1&tmp)+(2&tmp);tmp>>=2;//质数7占的位
                for(register int i=pos=4;i<=24;++i,++pos){
                    cnt[i]+=(tmp&1);tmp>>=1;if(!tmp)break;
                }
                if(pos==25)--pos;
                /*这一部分为神奇的常数优化,因为从第5个质数开始,一个区间内仅会出现1个,所以不需要快速幂计算*/
                ans*=mi(pri[0],cnt[0]);
                ans*=mi(pri[1],cnt[1]);
                ans*=mi(pri[2],cnt[2]);
                ans*=mi(pri[3],cnt[3]);
                an
                for(register int i=4;i<=pos;++i){
                	if(cnt[i])ans*=pri[i],an
				}
				/*常数优化结束*/
                printf(
                break;
            }
            case 'C':{
            	int vv=cal(p);//先计算一步,优化时间
                change(x,y,p,vv,1);
                break;
            }
            case 'S':{
                int tmp=qgcd(x,y,1),ans=1,pos;memset(cnt,0,sizeof cnt);
                //pos为常数优化用的变量
                cnt[0]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数2占的位
                cnt[1]+=(1&tmp)+(2&tmp)+(4&tmp);tmp>>=3;//质数3占的位
                cnt[2]+=(1&tmp)+(2&tmp);tmp>>=2;//质数5占的位
                cnt[3]+=(1&tmp)+(2&tmp);tmp>>=2;//质数7占的位
                for(register int i=pos=4;i<=24;++i,++pos){
                    cnt[i]+=(tmp&1);tmp>>=1;if(!tmp)break;
                }
                for(register int i=0;i<=pos;++i){
                    if(cnt[i])ans=an
                    //计算答案,答案为每个质数出现次数+1之积
                }
                printf(
                break;
            }
            default:{
                break;
            }
        }
    }
    return 0;
}