加法线段树 + 思维-白红宇的个人博客

加法线段树 + 思维

发布日期：2021-09-25 23:57:49 浏览次数：10 分类：技术文章

本文共 3029 字，大约阅读时间需要 10 分钟。

加法

时间限制: 8 Sec 内存限制: 128 MB

[提交] [状态]

题目描述

菜鸡Resee在学加法竖式

具体的，她可能会对{A1,A2,…,Ak}k个数做加法，得到一个和s

如果一次计算中s的每一位都在相加的那些数中对应的位置出现过，那么她认为这次计算是快乐的，不然就是不快乐的。例子如下图：

左边的计算是快乐的。右边的是不快乐的，因为s的十位是3，而没有一个数的十位是3

现在Resee的练习本上写了一排n个数。每次她会被要求在第L到第R个数中选一些数相加

她想知道存不存在方案使这一次计算是不快乐的。如果有，s最小是多少

因为Resee还可能涂涂改改，这些数还有可能改变。具体见读入格式

输入

第一行给出 n,Q 分别表示数字个数、操作个数

第二行给出 n 个数表示练习本上的数

接下来 Q 行，每行有两种情况：

1 x y 表示把第 x 个数改成 y

2 L R 表示题目描述中的询问

输出

对于每次询问输出一行，如果有答案就输出最小的 s，否则输出-1

样例输入 Copy

4 4

300 10001 20 20

2 1 3

1 1 310

2 1 3

2 3 3

样例输出 Copy

-1

330

-1

提示

第一次询问{20,300,10001}，无论怎么加都快乐

第二次询问{20,310,10001}，将{20,310}相加是不快乐的，不存在 s 更小的方案

第三次询问{20}，无论怎么加都快乐

本子上的数非负且在任意时刻小于 1000000

保证 1<=L<=R<=n

一天的补题计划被这个题给毁了，不过弄懂了强行不亏。

首先明确题目要求的是不快乐的数，根据题意，不快乐的数只需要一个数位不满足要求即可，一开始看成了快乐的数，结果卡了半天。

那么就不难想到，如果两个数的某一位都不为0，那么相加之后这个位置在结果中对应位置一定是找不到对应值的。由此得知，答案一定是两个数相加，因为求的是最小值，三个数相加的时候一定可以去掉一个数也满足要求，使答案变得更小。

既然是两个尽可能小的数相加，而且只需要一个数位不快乐就行，那么可以考虑维护每个数位的最小值和次小值，当数位为0的时候不进行更新，设为不存在，因为我们要的是都不为0的数。让后枚举每个数位，此时每个数位存的都是能使其不快乐的两个数 (如果存在的话) ，更新答案即可。

因为还有修改操作，那么可以用线段树来维护。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=200010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;int a[N],ans;PII w[6];struct Node{ int l,r; PII p[6];//first是最小值，second位次小值}tr[N<<2];void pushup(int u)//把最小值和次小值向上传递{ for(int i=0;i<6;i++) { int x1=tr[L].p[i].X,y1=tr[L].p[i].Y; int x2=tr[R].p[i].X,y2=tr[R].p[i].Y; if(x1<=x2) { tr[u].p[i].X=x1; tr[u].p[i].Y=min(x2,y1); } else { tr[u].p[i].X=x2; tr[u].p[i].Y=min(x1,y2); } }}void build(int u,int l,int r){ tr[u]={ l,r}; if(l==r) { int t=a[l],c=0; for(int i=0;i<6;i++)//这里终止条件要写 i < 6 ，写 t 的话可能没到6位就终止了，后面的 p 都是0，但应该设为 INF { c=t%10; if(c!=0) tr[u].p[i].X=a[l]; else tr[u].p[i].X=INF; tr[u].p[i].Y=INF; t/=10; } return; } build(L,l,Mid),build(R,Mid+1,r); pushup(u);}void modify(int u,int l,int r,int t){ if(tr[u].l>=l&&tr[u].r<=r) { int c=0,tt=t; for(int i=0;i<6;i++) { c=tt%10; if(c!=0) tr[u].p[i].X=t; else tr[u].p[i].X=INF; tt/=10; } return; } if(l<=Mid) modify(L,l,r,t); if(r>Mid) modify(R,l,r,t); pushup(u);}void query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) { for(int i=0;i<6;i++) { int x1=w[i].X,y1=w[i].Y; int x2=tr[u].p[i].X,y2=tr[u].p[i].Y; if(x1<=x2) { w[i].X=x1; w[i].Y=min(x2,y1); } else { w[i].X=x2; w[i].Y=min(x1,y2); } } return; } if(l<=Mid) query(L,l,r); if(r>Mid) query(R,l,r); pushup(u);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); while(m--) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1) modify(1,x,x,y); else { ans=INF; for(int i=0;i<6;i++) w[i].X=w[i].Y=INF; query(1,x,y); for(int i=0;i<6;i++) { int x=w[i].X,y=w[i].Y; if(x==INF&&y==INF) continue; ans=min(ans,x+y); } if(ans==INF) puts("-1"); else printf("%d\n",ans); } } return 0;}

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106110385 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：HDU 1325 Is It A Tree? 并查集

下一篇：upc 最⼤⼦段和线段树 + 懒标

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章