一段时间不写线段树标记，有些生疏了
codeforces 679e Bear and Bad Powers of 42 - CHADLZX - 博客园
关键点是：42的次幂，在long long范围内只有11个
考虑暴力修改
记录每个点距离下一个42次幂的距离，一般是负数
再记录每个点的等级，则有num=mi[lev+1]+val
特别地，当val=0的时候，num就是第lev个42的次幂
假如只有3操作，区间加，如果当前区间最大值大于等于0，
那么暴力下去升级：如果区间最大值大于等于0，就接着升级。如果升级途中，发现一个点的val==0，意味着还要再进行这个操作，flag记录一下
每个数只增不减，而且不会重复加太多次，大概每个点最多会被加O(logn)次，复杂度就是O(nlog^2n)
加上2操作，区间赋值会把很多数“拉回来”，而且一次性增加很多42次幂
但是权值种类会少很多，至少整个区间都是一个数
所以记录区间是否都是一个数，如果是一个数，就不用暴力修改了
增加了常数个42次幂的可能，也不会太多
这一步也就O(nlogn)
1的询问就是O(nlogn)
总复杂度正确
代码：
#include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') #define mid ((l+r)>>1) #define ls (x<<1) #define rs (x<<1|1) #define fi first #define se second using namespace std; typedef long long ll; il void rd(int &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x); } namespace Miracle{ const int N=100000+5; const ll inf=0x3f3f3f3f3f3f3f3f; int n,q; int U; ll a[N]; ll mi[11]; pair<ll,ll> zip(ll x){int p=lower_bound(mi,mi+U+1,x)-mi;--p;return make_pair(p,x-mi[p+1]); } ll num(int lev,ll dis){return mi[lev+1]+dis; } struct tr{ll mx;ll ad,chan; int same;int lev;ll val; }t[4*N];void pushup(int x){t[x].mx=max(t[x<<1].mx,t[x<<1|1].mx);if(t[x<<1].same&&t[x<<1|1].same&&t[x<<1].val==t[x<<1|1].val&&t[x<<1].lev==t[x<<1|1].lev){t[x].same=1;t[x].val=t[x<<1].val;t[x].lev=t[x<<1].lev;}else{t[x].same=0;} } pair<ll,ll>tmp; void pro(int &lev,ll &dis){ll now=num(lev,dis);tmp=zip(now);lev=tmp.fi;dis=tmp.se; } void build(int x,int l,int r){if(l==r){t[x].same=1;tmp=zip(a[l]);t[x].mx=t[x].val=tmp.se;t[x].lev=tmp.fi;t[x].chan=-inf;//warninig!!!! -inf represented no change t[x].ad=0;return;}t[x].ad=0;t[x].chan=-inf;build(ls,l,mid);build(rs,mid+1,r);pushup(x); } void pushdown(int x){for(reg i=0;i<=1;++i){int son=x<<1|i;if(t[x].chan!=-inf){ll c=t[x].chan;t[son].same=1;tmp=zip(c);t[son].lev=tmp.fi;t[son].val=tmp.se;t[son].ad=0;t[son].chan=c;t[son].mx=t[son].val;}else if(t[x].ad){ll c=t[x].ad;if(t[son].same){//if(t[x].mx+c==0) c+=c;//warning!!!if(t[son].chan!=-inf){t[son].chan+=c;}else{t[son].ad+=c;}t[son].val+=c;pro(t[son].lev,t[son].val);t[son].mx=t[son].val;}else{t[son].mx+=c;t[son].ad+=c;}}}t[x].ad=0;t[x].chan=-inf; } bool upda(int x,int l,int r){//bao li updaing levelif(l==r){if(t[x].val==0){return true;}return false;}else if(t[x].same){if(t[x].val==0) return true;return false;}pushdown(x);bool ret=false;if(t[ls].mx>=0) ret|=upda(x<<1,l,mid);if(t[rs].mx>=0) ret|=upda(x<<1|1,mid+1,r);pushup(x);//warinnig!!!! return ret; }int flag; void add(int x,int l,int r,int L,int R,ll c){if(L<=l&&r<=R){if(t[x].same){if(t[x].chan!=-inf){t[x].chan+=c;}else{t[x].ad+=c;}t[x].val+=c;pro(t[x].lev,t[x].val);t[x].mx=t[x].val;if(t[x].mx==0) flag=1;//need again }else{t[x].mx+=c;t[x].ad+=c;if(t[x].mx>=0){flag|=upda(x,l,r); // while(fl){ // fl=upda(x,l,r); // if(fl) { // t[x].mx+=c; // t[x].ad+=c; // } // if(t[x].mx>=0){ // fl=true; // }else{ // fl=false; // } // } }}return;}pushdown(x);if(L<=mid) add(x<<1,l,mid,L,R,c);if(mid<R) add(x<<1|1,mid+1,r,L,R,c);pushup(x); } void chan(int x,int l,int r,int L,int R,ll c){if(L<=l&&r<=R){t[x].same=1;tmp=zip(c);t[x].lev=tmp.fi;t[x].val=tmp.se;t[x].ad=0;t[x].chan=c;t[x].mx=t[x].val;return;}pushdown(x);if(L<=mid) chan(x<<1,l,mid,L,R,c);if(mid<R) chan(x<<1|1,mid+1,r,L,R,c);pushup(x); } ll query(int x,int l,int r,int p){if(l==r){return num(t[x].lev,t[x].val);}pushdown(x);if(p<=mid) return query(ls,l,mid,p);else return query(rs,mid+1,r,p); } int main(){rd(n);rd(q);for(reg i=1;i<=n;++i){scanf("%lld",&a[i]);}mi[0]=1;for(reg i=1;i<=10;++i) mi[i]=mi[i-1]*42;U=10;build(1,1,n);int op,l,r,p;ll c;while(q--){rd(op);if(op==1){rd(p);printf("%lld\n",query(1,1,n,p));}else if(op==2){rd(l);rd(r);scanf("%lld",&c);chan(1,1,n,l,r,c);}else{rd(l);rd(r);scanf("%lld",&c);flag=0;add(1,1,n,l,r,c);while(flag){flag=0;add(1,1,n,l,r,c);}}}return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle*Date: 2019/2/14 20:07:14 */