题目（洛谷）
首先看题，求区间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;
}
Comments NOTHING