- 10%:1<n,m<=10
- 30%:1<n,m<=10000
- 100%:1<n,m<=100000
保证中间结果在 long long(C/C++),int64(pascal) 范围内
思路;
有两个标记一个 add 一个 set, 我们肯定是优先处理 set 操作, 如果当前点被 set 标记了, 那么之前的 add 标记也会被清空, 所以当进行 set 操作是必须要清空 add 标记.
题目没给 c 的范围, 那么我们假定他为 -1e9 <c < 1e9 , 那么也就是有可能存在等于 0 和负数的情况, 所以 set 标记的初始化可以选定为 -1e16;
为社么感觉写过...
实现代码;
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define lson l,m,rt<<1
- #define rson m+1,r,rt<<1|1
- #define mid ll m = (l + r)>> 1
- const ll M = 1e5 + 10;
- const ll inf = 1e16+10;
- ll sum[M<<2],Set[M<<2],mx[M<<2],add[M<<2],mn[M<<2];
- ll a[M];
- void pushup(ll rt){
- sum[rt] = sum[rt<<1] + sum[rt<<1|1];
- mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
- mn[rt] = min(mn[rt<<1],mn[rt<<1|1]);
- }
- void pushdown(ll l,ll r,ll rt){
- if(Set[rt]!=-inf){
- mid;
- sum[rt<<1] = Set[rt]*(m-l+1);
- sum[rt<<1|1] = Set[rt]*(r-m);
- mx[rt<<1] = mx[rt<<1|1] = Set[rt];
- mn[rt<<1] = mn[rt<<1|1] = Set[rt];
- Set[rt<<1] = Set[rt<<1|1] = Set[rt];
- add[rt<<1] = add[rt<<1|1] = 0;
- Set[rt] = -inf;
- }
- if(add[rt]){
- mid;
- sum[rt<<1] += add[rt]*(m-l+1);
- sum[rt<<1|1] += add[rt]*(r-m);
- mx[rt<<1] += add[rt]; mx[rt<<1|1] += add[rt];
- mn[rt<<1] += add[rt]; mn[rt<<1|1] += add[rt];
- add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt];
- add[rt] = 0;
- }
- }
- void build(ll l,ll r,ll rt){
- Set[rt] = -inf; add[rt] = 0;
- if(l == r){
- sum[rt] = mx[rt] = mn[rt] = a[l];
- Set[rt] = -inf;add[rt] = 0;
- return ;
- }
- mid;
- build(lson); build(rson);
- pushup(rt);
- }
- void update(ll L,ll R,ll op,ll c,ll l,ll r,ll rt){
- if(L <= l&&R>= r){
- if(op == 1){
- sum[rt] = (r-l+1)*c;
- mx[rt] = mn[rt] = Set[rt] = c;
- add[rt] = 0;
- return ;
- }
- else{
- sum[rt] += (r-l+1)*c;
- mx[rt] += c; add[rt] += c;
- mn[rt] += c;
- return ;
- }
- }
- pushdown(l,r,rt);
- mid;
- if(L <= m) update(L,R,op,c,lson);
- if(R> m) update(L,R,op,c,rson);
- pushup(rt);
- }
- ll query_sum(ll L,ll R,ll l,ll r,ll rt){
- if(L <= l&&R>= r){
- return sum[rt];
- }
- pushdown(l,r,rt);
- mid; ll ret = 0;
- if(L <= m) ret += query_sum(L,R,lson);
- if(R> m) ret += query_sum(L,R,rson);
- return ret;
- }
- ll query_max(ll L,ll R,ll l,ll r,ll rt){
- if(L <= l&&R>= r){
- return mx[rt];
- }
- pushdown(l,r,rt);
- mid; ll ret = -inf;
- if(L <= m) ret = max(ret,query_max(L,R,lson));
- if(R> m) ret = max(ret,query_max(L,R,rson));
- return ret;
- }
- ll query_min(ll L,ll R,ll l,ll r,ll rt){
- if(L <= l&&R>= r){
- return mn[rt];
- }
- pushdown(l,r,rt);
- mid,ret = inf;
- if(L <= m) ret = min(ret,query_min(L,R,lson));
- if(R> m) ret = min(ret,query_min(L,R,rson));
- return ret;
- }
- char s[100];
- int main(){
- ll n,l,r,c,q;
- scanf("%lld%lld",&n,&q);
- for(ll i = 1;i <= n;i ++)
- scanf("%lld",&a[i]);
- build(1,n,1);
- while(q--){
- scanf("%s",s); scanf("%lld%lld",&l,&r);
- if(s[0] == 'a'){
- scanf("%lld",&c);
- update(l,r,0,c,1,n,1);
- }
- else if(s[0] == 's'&&s[1] == 'e'){
- scanf("%lld",&c);
- update(l,r,1,c,1,n,1);
- }
- else if(s[0] == 's'&&s[1] == 'u'){
- printf("%lld\n",query_sum(l,r,1,n,1));
- }
- else if(s[0] == 'm'&&s[1] == 'a'){
- printf("%lld\n",query_max(l,r,1,n,1));
- }
- else {
- printf("%lld\n",query_min(l,r,1,n,1));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2831830.html