一段时间不写线段树标记，有些生疏了
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 level if(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 ",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 */