第二题类似为第一题的加强版。
这好像也就是吉司机线段树。
1.上帝造题7分钟
题意
给定两种操作，给定 \(k,l,r\)：
-
当 \(k=0\)，将 \([l,r]\) 的所有数 \(x\leftarrow \left\lfloor \sqrt{x} \right\rfloor\)；
-
当 \(k=1\)，求 \([l,r]\) 所有数的和。
思路
势能线段树
我们发现，数列中的数最大不超过 \(10^{12}\)，对其取根号 \(6\) 次便能取到 \(1\)，而 \(1\) 取根号还是本身。
因此不难发现，当一段数最大值即为 \(1\) 时便无需操作，节省大量时间。
所以考虑用线段树维护区间最值和区间和即可；修改操作时，当最大值为 \(1\) 直接 return 即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=3e5+9,M=1e6+9;
ll n,m,a[N],T,op,l,r;
struct SegT
{struct node{ll ma,sum;}T[N<<4];void pushup(ll u){T[u].ma=max(T[u<<1].ma,T[u<<1|1].ma);T[u].sum=T[u<<1].sum+T[u<<1|1].sum;}void build(ll u,ll l,ll r){if(l==r){T[u].ma=T[u].sum=a[l];return;}ll mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}void modify(ll u,ll l,ll r,ll ql,ll qr){if(T[u].ma<=1)return;if(l==r){a[l]=sqrt(a[l]);T[u].ma=T[u].sum=a[l];return;}ll mid=(l+r)>>1;if(ql<=mid)modify(u<<1,l,mid,ql,qr);if(qr>mid)modify(u<<1|1,mid+1,r,ql,qr);pushup(u);}ll query(ll u,ll l,ll r,ll ql,ll qr){if(ql<=l&&r<=qr)return T[u].sum;ll mid=(l+r)>>1;ll sum=0;if(ql<=mid)sum+=query(u<<1,l,mid,ql,qr);if(qr>mid)sum+=query(u<<1|1,mid+1,r,ql,qr);return sum;}
}A;
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);A.build(1,1,n);scanf("%lld",&m);while(m--){scanf("%lld%lld%lld",&op,&l,&r);if(l>r)swap(l,r);if(op==0)A.modify(1,1,n,l,r);else printf("%lld\n",A.query(1,1,n,l,r));}return 0;
}
2.吊打
题意
多了一种操作，使 \(x\leftarrow x^2\)；在最后查询数列所有数的和。
开方即用如上思路，但是考虑到平方比较大，所以先把平方操作数 \(pw\) 记下来，当做懒标记；因为每次把 \(pw\) 给原数次方都会巨大，考虑标记永久化，遇到开放操作可以直接维护 \(pw\)：
如果遇到平方操作，令 \(pw+1\)；
如果遇到开方操作，若 \(pw>0\) 则令 $pw-1；否则就按上一题的思路开方。
最后记得使用欧拉定理降幂科技，预处理 \(2\) 的幂次，即可快速下放标记计算。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=2e5+9,mod=998244353;
ll n,m,a[N];
ll qpow(ll x,ll k,ll mod)
{ll ret=1;while(k){if(k&1)ret=ret*x%mod;x=x*x%mod;k>>=1;}return ret;
}
struct SegT
{struct node{ll ma,pw,tag;//pw:幂次 }T[N<<4];void pushup(ll u){T[u].ma=max(T[ls].ma,T[rs].ma);T[u].pw=min(T[ls].pw,T[rs].pw);}void pushdown(ll u){T[ls].pw+=T[u].tag;T[ls].tag+=T[u].tag;T[rs].pw+=T[u].tag;T[rs].tag+=T[u].tag;T[u].tag=0;}void build(ll u,ll l,ll r){T[u].pw=0;if(l==r){T[u].ma=a[l];return;}ll mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void srt(ll u,ll l,ll r,ll ql,ll qr){if(T[u].ma<=1)return;if(qr<l||r<ql)return;if(T[u].pw&&ql<=l&&r<=qr){T[u].pw--;T[u].tag--;return;}if(l==r){if(T[u].pw)T[u].pw--;else T[u].ma=sqrt(T[u].ma);return;}pushdown(u);ll mid=(l+r)>>1;if(ql<=mid)srt(ls,l,mid,ql,qr);if(qr>mid)srt(rs,mid+1,r,ql,qr);pushup(u);}void squ(ll u,ll l,ll r,ll ql,ll qr){if(T[u].ma<=1)return;if(qr<l||r<ql)return;if(ql<=l&&r<=qr){T[u].pw++;T[u].tag++;return;}pushdown(u);ll mid=(l+r)>>1;if(ql<=mid)squ(ls,l,mid,ql,qr);if(qr>mid)squ(rs,mid+1,r,ql,qr);pushup(u);}ll Sum(ll u,ll l,ll r){if(l==r){if(T[u].pw)return qpow(T[u].ma,qpow(2,T[u].pw,mod-1),mod)%mod;return T[u].ma;}pushdown(u);ll mid=(l+r)>>1,ret=(Sum(ls,l,mid)+Sum(rs,mid+1,r))%mod;return ret;}
}A;
int main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);A.build(1,1,n);while(m--){ll op,l,r;scanf("%lld%lld%lld",&op,&l,&r);if(op==1)A.srt(1,1,n,l,r);else A.squ(1,1,n,l,r);}printf("%lld",A.Sum(1,1,n));return 0;
}