EduCational CodeForces Round 72 (Rated for Div. 2) E (Line Segment Tree, Thinking)

#define HAVE_STRUCT_TIMESPEC
#include
using namespace std;
#define BUF_SIZE 100000
bool IOerror=0; “font-family:’Microsoft YaHei’; font-size: 18px;”>inline char nc(){
static char buf[BUF_SIZE], *p1=buf+BUF_SIZE, *pend=buf+BUF_SIZE;
if(p1==pend){
p1=buf;
pend=buf+fread(bu f, 1, BUF_SIZE, stdin);
if(pend==p1){
IOerror=1;
return -1;
}
< span style="font-family:'Microsoft YaHei'; font-size: 18px;"> }
return *p1++;
}
inline bool blank(char ch){
return ch==”||ch==’
‘||ch==’
‘||ch==’ ‘;
}
inline void read(int &x ){ char ch;
int sign=1;
while(blank(ch=nc()) );
if(IOerror)return;
if(ch==’-‘){
sign=-1;
ch=nc();< br> }
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];//Create ten line segment trees ，Save the number of each position in the decimal system. If the number in this position is 0, it will save 2e9
int tamp[7];
void up(int flag,int rt ){
tamp[1]=tree[flag][rt<<1].mn;< /span>
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);//This may be an important reason for the slow running speed. Sort is about twice as slow as scanning, and even so it is twice as slow as other code 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 ;
< span style="font-family:'Microsoft YaHei'; font-size: 18px;">}
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 ;
}< /span>
if(pos<=tree[flag][rt].mid)
update(flag,rt<<1,pos,val);
else
update(flag,rt <<1|1,pos,val);
up(flag,rt);
}
pairquery(int flag,int rt,int l,int r){
if(tree[flag][rt].l>r&&tree[flag][rt].r
return pair(2e9,2e9);
if(tree[flag][rt].l>=l&&tree[flag ][rt].r<=r)
return pair(tree[flag ][rt].mn,tree[flag][rt].mn2);
pairtmp(2e9,2e9);
if(tree[flag][rt].mid >=l)
tmp=query(flag,rt<<1,l,r);< /span>
if(tree[flag][rt].mid
pairtp=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);//It is slower than scanning again. . .
tmp={tamp[1],tamp[2]};
}
return tmp;
}
int main(){
int n ,m;
read(n),read(m);
< span style="font-family:'Microsoft YaHei'; font-size: 18px;"> 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)< br> for(int j=1;j<=10;++j){
int tmp=z/pow(10,j-1);
if(tmp%10)
update( j,1,y,z);//Update this digit if it is not zero, and change this digit to z
else
update(j,1,y,2e9);/ /If the number on this digit is zero, update it and change this digit to 2e9
}
else{
long long mx=2e18;
for(int j=1;j<=10 ;++j){
pairpr=query(j,1,y ,z);
if(pr.second==2e9)
< span style="font-family:'Microsoft YaHei'; font-size: 18px;"> continue;//In the range of y~z, there are no two numbers in j that are not 0
else
mx=min(mx,1ll*pr.first+1ll*pr.second);//In the interval of y~z, there are two numbers in j that are not 0, update the answer whether it becomes the smallest The sum of the two numbers
}
if(mx==2e18)
cout<<-1<<" ";
else
cout<
}
}
return 0;
}