Educational Codeforces Round 72 (Rated for Div. 2)E（线段树，思维）

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
#define BUF_SIZE 100000
bool IOerror=0;//加了读入挂才1900ms+卡ddl过的，不加读入代码tleT_T
inline char nc(){
static char buf[BUF_SIZE], *p1=buf+BUF_SIZE, *pend=buf+BUF_SIZE;
if(p1==pend){
p1=buf;
pend=buf+fread(buf, 1, BUF_SIZE, stdin);
if(pend==p1){
IOerror=1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch){
return ch==‘ ‘||ch==‘\n‘||ch==‘\r‘||ch==‘\t‘;
}
inline void read(int &x){
char ch;
int sign=1;
while(blank(ch=nc()));
if(IOerror)return;
if(ch==‘-‘){
sign=-1;
ch=nc();
}
for(x=ch-‘0‘; (ch=nc())>=‘0‘&&ch<=‘9‘; x=x*10+ch-‘0‘);
x*=sign;
}
int a[200007];
typedef struct lst{
int l,r,mid;
int mn,mn2;
};
lst tree[15][800007];//建立十颗线段树，保存十进制上每一位每个位置的数字是多少，这个位置的数字在这一位为0就保存2e9
int tamp[7];
void up(int flag,int rt){
tamp[1]=tree[flag][rt<<1].mn;
tamp[2]=tree[flag][rt<<1].mn2;
tamp[3]=tree[flag][rt<<1|1].mn;
tamp[4]=tree[flag][rt<<1|1].mn2;
sort(tamp+1,tamp+5);//这里可能是运行速度慢的重要原因，sort比扫一遍大概慢一倍，即使如此还是比别人代码慢一倍T_T
tree[flag][rt].mn=tamp[1];
tree[flag][rt].mn2=tamp[2];
return ;
}
void build(int flag,int rt,int l,int r){
tree[flag][rt].l=l;
tree[flag][rt].r=r;
if(l==r){
int tmp=a[l]/pow(10,flag-1);
if(tmp%10==0)
tree[flag][rt].mn=tree[flag][rt].mn2=2e9;
else{
tree[flag][rt].mn=a[l];
tree[flag][rt].mn2=2e9;
}
return ;
}
int mid=tree[flag][rt].mid=l+r>>1;
build(flag,rt<<1,l,mid);
build(flag,rt<<1|1,mid+1,r);
up(flag,rt);
return ;
}
void update(int flag,int rt,int pos,int val){
if(tree[flag][rt].l==tree[flag][rt].r){
tree[flag][rt].mn=val;
tree[flag][rt].mn2=2e9;
return ;
}
if(pos<=tree[flag][rt].mid)
update(flag,rt<<1,pos,val);
else
update(flag,rt<<1|1,pos,val);
up(flag,rt);
}
pair<int,int>query(int flag,int rt,int l,int r){
if(tree[flag][rt].l>r&&tree[flag][rt].r<l)
return pair<int,int>(2e9,2e9);
if(tree[flag][rt].l>=l&&tree[flag][rt].r<=r)
return pair<int,int>(tree[flag][rt].mn,tree[flag][rt].mn2);
pair<int,int>tmp(2e9,2e9);
if(tree[flag][rt].mid>=l)
tmp=query(flag,rt<<1,l,r);
if(tree[flag][rt].mid<r){
pair<int,int>tp=query(flag,rt<<1|1,l,r);
tamp[1]=tp.first;
tamp[2]=tp.second;
tamp[3]=tmp.first;
tamp[4]=tmp.second;
sort(tamp+1,tamp+5);//又比扫一遍慢。。。
tmp={tamp[1],tamp[2]};
}
return tmp;
}
int main(){
int n,m;
read(n),read(m);
for(int i=1;i<=n;++i)
read(a[i]);
for(int i=1;i<=10;++i)
build(i,1,1,n);
for(int i=1;i<=m;++i){
int x,y,z;
read(x),read(y),read(z);
if(x==1)
for(int j=1;j<=10;++j){
int tmp=z/pow(10,j-1);
if(tmp%10)
update(j,1,y,z);//这一位上数字不为零就更新，将这一位变成z
else
update(j,1,y,2e9);//这一位上数字为零就更新，将这一位变成2e9
}
else{
long long mx=2e18;
for(int j=1;j<=10;++j){
pair<int,int>pr=query(j,1,y,z);
if(pr.second==2e9)
continue;//y~z区间内j这一位上没有两个数都不为0的
else
mx=min(mx,1ll*pr.first+1ll*pr.second);//y~z区间内j这一位上有两个数都不为0的，更新答案是否变成最小的两个数的和
}
if(mx==2e18)
cout<<-1<<"\n";
else
cout<<mx<<"\n";
}
}
return 0;
}