Gym 102419 I Another Query Problem —— 线段树

本文主要是介绍Gym 102419 I Another Query Problem —— 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有n个操作，有两种操作：
1 l r 查看l-r区间所有数是否相同
2 l r a b 区间l-r第i个位置加上a+(i-l)*b

题解：

这种题目遇到好几次了，估计下次就懒得写题解。首先区间问题考虑线段树，但是无法直接更新，因为值会随位置变化而变化，怎么解决这个问题，可以在第i个位置上维护$a_i-a_{i-1}$，那么相当于l+1到r的区间+b即可。然后查询就查l+1到r的区间最大最小值是否都为0.注意一点，2操作需要在r+1的位置上-(a+(r-l)*b)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pa pair<ll,ll>
const int N=4e5+5;
ll mx[N*4],mi[N*4],f[N*4];
void push_down(int root){if(!f[root])return ;mx[root<<1]+=f[root];mx[root<<1|1]+=f[root];mi[root<<1]+=f[root];mi[root<<1|1]+=f[root];f[root<<1]+=f[root];f[root<<1|1]+=f[root];f[root]=0;
}
void update(int l,int r,int root,int ql,int qr,ll v){if(l>=ql&&r<=qr){mi[root]+=v;mx[root]+=v;f[root]+=v;return ;}int mid=l+r>>1;push_down(root);if(mid>=ql)update(l,mid,root<<1,ql,qr,v);if(mid<qr)update(mid+1,r,root<<1|1,ql,qr,v);mx[root]=max(mx[root<<1],mx[root<<1|1]);mi[root]=min(mi[root<<1],mi[root<<1|1]);
}
pa query(int l,int r,int root,int ql,int qr){if(l>=ql&&r<=qr)return {mx[root],mi[root]};int mid=l+r>>1;push_down(root);pa ans={0,0};if(mid>=ql)ans=query(l,mid,root<<1,ql,qr);if(mid<qr){pa aa=query(mid+1,r,root<<1|1,ql,qr);ans.first=max(ans.first,aa.first);ans.second=min(ans.second,aa.second);}return ans;
}
int main()
{int n,m;scanf("%d%d",&n,&m);while(m--){int op,l,r;ll a,b;scanf("%d%d%d",&op,&l,&r);if(op==1){if(l==r)printf("1\n");else{pa ans=query(1,n,1,l+1,r);printf("%d\n",ans.first==0&&ans.second==0);}}else{scanf("%lld%lld",&a,&b);update(1,n,1,l,l,a);if(l<r)update(1,n,1,l+1,r,b);if(r<n)update(1,n,1,r+1,r+1,-(a+(r-l)*b));}}return 0;
}
//

这篇关于Gym 102419 I Another Query Problem —— 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---