传送门

今天子帧的一套模拟题的T3。

考试的时候其实已经想到了正解了，但是一些地方没有想清楚，就没敢写，只打了个暴力。

首先考虑用线段树维护区间信息。

先把每个值拆成两个信息，一是距离他最近的且大于他的$42$的整次幂，而是到距离他最近的且大于他的$42$的整次幂的距离。

操作1和操作2不需要细说。

对于操作3，每次加入一个数后check整棵线段树的Min，如果出现负数就逐个升级。如果出现了0就再次增加，直到不出现0为止。

因为每个数最多升级$logN$次，所以时间上是没有问题的。

另一个小细节（被卡了很长时间），在每次下传操作2的lazytag之前要先将下一个的操作3的lazytag清空。

//Codeforces 679E//by Cydiater//2017.1.20#include <iostream>#include <queue>#include <map>#include <ctime>#include <cstring>#include <string>#include <cmath>#include <ctime>#include <iomanip>#include <cstdlib>#include <cstdio>#include <bitset>#include <set>#include <vector>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define FILE		"bad42"const int MAXN=2e5+5;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}ll pw[MAXN],N,M,arr[MAXN];//little toolll Level(ll num){up(i,0,11)if(pw[i]>=num)return i;}ll Dist(ll num){up(i,0,11)if(pw[i]>=num)return pw[i]-num;}struct tree{	ll Min,tag1,tag2,level;	//tag1 -> opt2	//tag2 -> opt3}t[MAXN<<2];namespace SegmentTree{	inline void reload(int root){t[root].Min=min(t[root<<1].Min,t[root<<1|1].Min);}	inline void Uplevel(int root){		ll num=pw[t[root].level]-t[root].Min;		t[root].level=Level(num);		t[root].Min=Dist(num);	}	inline void Pushdown(int leftt,int rightt,int root){		if(t[root].tag1>0){			if(leftt!=rightt){				t[root<<1].level=Level(t[root].tag1);				t[root<<1].Min=Dist(t[root].tag1);				t[root<<1].tag1=t[root].tag1;				t[root<<1].tag2=0;							t[root<<1|1].level=Level(t[root].tag1);				t[root<<1|1].Min=Dist(t[root].tag1);				t[root<<1|1].tag1=t[root].tag1;				t[root<<1|1].tag2=0;			}			t[root].tag1=0;		}		if(t[root].tag2>0){			if(leftt!=rightt){				t[root<<1].Min-=t[root].tag2;				t[root<<1].tag2+=t[root].tag2;				t[root<<1|1].Min-=t[root].tag2;				t[root<<1|1].tag2+=t[root].tag2;			}			t[root].tag2=0;		}	}	void Build(int leftt,int rightt,int root){		if(leftt==rightt){			t[root].Min=Dist(arr[leftt]);t[root].level=Level(arr[leftt]);			t[root].tag1=-1;t[root].tag2=0;			return;		}		int mid=(leftt+rightt)>>1;		t[root].tag1=-1;t[root].tag2=0;		Build(leftt,mid,root<<1);		Build(mid+1,rightt,root<<1|1);		reload(root);	}	ll Realnum(int leftt,int rightt,int root,int pos){		Pushdown(leftt,rightt,root);		if(leftt==rightt||t[root].tag1==0)	return pw[t[root].level]-t[root].Min;		int mid=(leftt+rightt)>>1;		if(mid>=pos)				return Realnum(leftt,mid,root<<1,pos);		else if(mid+1<=pos)			return Realnum(mid+1,rightt,root<<1|1,pos);	}	void Modify(int leftt,int rightt,int root,int L,int R,int val,int tag){		Pushdown(leftt,rightt,root);		int mid=(leftt+rightt)>>1;		if(leftt>=L&&rightt<=R){			if(tag==1){				t[root].tag1=val;				t[root].level=Level(val);				t[root].Min=Dist(val);			}			else{				t[root].tag2=val;				t[root].Min-=val;			}			return;		}		t[root].tag1=-1;		if(L>=mid+1)	Modify(mid+1,rightt,root<<1|1,L,R,val,tag);		else if(R<=mid)	Modify(leftt,mid,root<<1,L,R,val,tag);		else{			Modify(leftt,mid,root<<1,L,R,val,tag);			Modify(mid+1,rightt,root<<1|1,L,R,val,tag);		}		reload(root);	}	void fix(int leftt,int rightt,int root){		Pushdown(leftt,rightt,root);		if(leftt==rightt||t[root].tag1==0){			Uplevel(root);			return;		}		int mid=(leftt+rightt)>>1;		if(t[root<<1].Min<0)	fix(leftt,mid,root<<1);		if(t[root<<1|1].Min<0)	fix(mid+1,rightt,root<<1|1);		reload(root);	}}using namespace SegmentTree;namespace solution{	void Prepare(){		pw[0]=1;		up(i,1,11)pw[i]=pw[i-1]*42LL;		N=read();M=read();		up(i,1,N)arr[i]=read();		Build(1,N,1);	}	void Solve(){		while(M--){			int opt=read();			if(opt==1){				int pos=read();				printf("%I64d\n",Realnum(1,N,1,pos));			}			if(opt==2){				int L=read(),R=read(),val=read();				Modify(1,N,1,L,R,val,1);			}			if(opt==3){				int L=read(),R=read(),val=read();				do{					Modify(1,N,1,L,R,val,2);					//printf("%d\n",Realnum(1,N,1,1));					if(t[1].Min<0)fix(1,N,1);				}while(t[1].Min==0);			}			//up(i,1,N)printf("%d ",Realnum(1,N,1,i));puts("");		}	}}int main(){	//freopen("input.in","r",stdin);	//freopen("out1.out","w",stdout);	//freopen(FILE".in","r",stdin);	//freopen(FILE".out","w",stdout);	using namespace solution;	Prepare();	Solve();	return 0;}

Codeforces679E. Bear and Bad Powers of 42