首页 > 代码库 > CodeForces 444C 节点更新求变化值的和

CodeForces 444C 节点更新求变化值的和

2024-07-16 09:20:48   216人阅读

http://vjudge.net/problem/viewProblem.action?id=51622

题目大意：

给定一列n个数字，最初赋予值1到n

两个操作：
1.将区间[l,r]内的数改为x，则这区间中所有数的改变值进行求和，即ans=abs(a[l]-x)+abs[a[l+1]-x).....abs(a[r]-x)，但不要求输出

2.需要将刚才要求得到的区间改变值输出出来

 

这里我们利用一个color[]数组相当于给这堆数进行染色，当某个区间内的赋予的值相等时，我们可以看做有一个相同的color[]=val了，这样我们可以直接对这个区间

利用乘法求改变值。

这样的话，我们还需要一个数组del[]时刻记录每个量改变的差值

sum[]数组的话就是用来保存区间改变量的和

 

 1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define N 100005 5 #define LL long long 6 #define L ls,x,mid 7 #define R rs,mid+1,y 8 LL color[N<<2],sum[N<<2],del[N<<2]; 9 LL abs(LL a)10 {11     return a>0?a:-a;12 }13 void push_up(int cur)14 {15     if(color[cur<<1]==color[cur<<1|1]) color[cur]=color[cur<<1];16     else color[cur]=0;17     sum[cur]=sum[cur<<1]+sum[cur<<1|1];18 }19 void push_down(int cur,int x,int y)20 {21     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;22     if(color[cur]){23         color[ls]=color[rs]=color[cur];24         del[ls]+=del[cur],del[rs]+=del[cur];25         sum[ls]+=(mid-x+1)*del[cur];26         sum[rs]+=(y-mid)*del[cur];27         del[cur]=color[cur]=0;28     }29 }30 void build(int cur,int x,int y)31 {32     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;33     if(x==y){34         color[cur]=x;35         sum[cur]=0;36         return;37     }38     color[cur]=del[cur]=0;39     build(L);40     build(R);41     push_up(cur);42 }43 void update(int cur,int x,int y,int s,int t,int v)44 {45     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;46     if(x>=s&&y<=t&&color[cur]){47         sum[cur]+=abs(color[cur]-v)*(y-x+1);48         //printf("%I64d\n",abs(color[cur]-v));49         del[cur]+=abs(color[cur]-v);50         color[cur]=v;51         return;52     }53     push_down(cur,x,y);54     if(mid>=s) update(L,s,t,v);55     if(mid<t) update(R,s,t,v);56     push_up(cur);57 }58 void query(int cur,int x,int y,int s,int t,LL &ans)59 {60     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;61     if(x>=s&&y<=t){62         ans+=sum[cur];63         return;64     }65     push_down(cur,x,y);66     if(mid>=s) query(L,s,t,ans);67     if(mid<t) query(R,s,t,ans);68 }69 int main()70 {71     int n,m,type,l,r,x;72     scanf("%d%d",&n,&m);73     build(1,1,n);74     for(int i=0;i<m;i++)75     {76         scanf("%d",&type);77         if(type==1){78             scanf("%d%d%d",&l,&r,&x);79             update(1,1,n,l,r,x);80         }else{81             scanf("%d%d",&l,&r);82             LL ans=0;83             query(1,1,n,l,r,ans);84             printf("%I64d\n",ans);85         }86     }87     return 0;88 }

 


联系
我们