首页 > 其他 > 详细

[BZOJ]4695: 最假女选手

时间：2019-01-29 22:57:47      阅读：164      评论：0      收藏：0      [点我收藏+]

题解:  看到这个题想的直接最大最小 次大次小 已经最大最小值出现的次数 和 求和   第一次做的时候 维护了最大值和最小值改变的下传标记 但是没有处理好与区间加标记的先后顺序  后来看了别人的题解 发现不用维护最值下传标记  因为可以通过判断其儿子的最值是否发生改变 然后用父亲的最值去更新即可 然后就只用维护区间加的标记  就行了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=5e5+10;
const double eps=1e-8;
#define ll long long
const int inf=1e9;
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}

typedef struct node{
    int mx,cmx,numx;
    int mn,cmn,numn;
    ll sum,flag;
}node;

node d[MAXN<<2];
int a[MAXN];

void up(int rt){
    d[rt].sum=d[rt<<1].sum+d[rt<<1|1].sum;
    d[rt].numx=d[rt].numn=0;
    d[rt].mx=max(d[rt<<1].mx,d[rt<<1|1].mx);
    if(d[rt].mx==d[rt<<1].mx)d[rt].numx+=d[rt<<1].numx;
    if(d[rt].mx==d[rt<<1|1].mx)d[rt].numx+=d[rt<<1|1].numx;
    d[rt].cmx=max(d[rt<<1].cmx,d[rt<<1|1].cmx);
    if(d[rt<<1].mx!=d[rt<<1|1].mx)d[rt].cmx=max(d[rt].cmx,min(d[rt<<1].mx,d[rt<<1|1].mx));
    d[rt].mn=min(d[rt<<1].mn,d[rt<<1|1].mn);
    if(d[rt].mn==d[rt<<1].mn)d[rt].numn+=d[rt<<1].numn;
    if(d[rt].mn==d[rt<<1|1].mn)d[rt].numn+=d[rt<<1|1].numn;
    d[rt].cmn=min(d[rt<<1].cmn,d[rt<<1|1].cmn);
    if(d[rt<<1].mn!=d[rt<<1|1].mn)d[rt].cmn=min(d[rt].cmn,max(d[rt<<1].mn,d[rt<<1|1].mn));
}

void push2(int x,int k){
    if(d[x].mn==d[x].cmx)d[x].cmx=k;
    if(d[x].cmx==-inf&&d[x].cmn==inf)d[x].mx=k;
    d[x].sum+=1ll*(k-d[x].mn)*d[x].numn,d[x].mn=k;
}

void push3(int x,int k){
    if(d[x].mx==d[x].cmn)d[x].cmn=k;
    if(d[x].cmx==-inf&&d[x].cmn==inf)d[x].mn=k;
    d[x].sum-=1ll*(d[x].mx-k)*d[x].numx,d[x].mx=k;
}

void push(int x,int l,int r){
    if(d[x].flag){
	int mid=(l+r)>>1;
	d[x<<1].flag+=d[x].flag;d[x<<1].mx+=d[x].flag;d[x<<1].mn+=d[x].flag;d[x<<1].sum+=1ll*(mid-l+1)*d[x].flag;
	if(d[x<<1].cmx!=-inf&&d[x<<1].cmn!=inf)d[x<<1].cmx+=d[x].flag,d[x<<1].cmn+=d[x].flag;
	d[x<<1|1].flag+=d[x].flag;d[x<<1|1].mx+=d[x].flag;d[x<<1|1].mn+=d[x].flag;d[x<<1|1].sum+=1ll*(r-mid)*d[x].flag;
	if(d[x<<1|1].cmx!=-inf&&d[x<<1|1].cmn!=inf)d[x<<1|1].cmx+=d[x].flag,d[x<<1|1].cmn+=d[x].flag;    
	d[x].flag=0;
    }
    //cout<<l<<"-----==="<<r<<" "<<d[x<<1|1].mn<<" "<<d[x<<1|1].cmn<<" "<<d[x].mn<<" "<<d[x<<1|1].flag<<endl;
    if(d[x<<1].cmx<d[x].mx&&d[x].mx<d[x<<1].mx)push3(x<<1,d[x].mx);
    if(d[x<<1|1].cmx<d[x].mx&&d[x].mx<d[x<<1|1].mx)push3(x<<1|1,d[x].mx);
    if(d[x<<1].mn<d[x].mn&&d[x].mn<d[x<<1].cmn)push2(x<<1,d[x].mn);
    if(d[x<<1|1].mn<d[x].mn&&d[x].mn<d[x<<1|1].cmn)push2(x<<1|1,d[x].mn);
}


void built(int rt,int l,int r){
    d[rt].flag=0;
    if(l==r){
	d[rt].mn=d[rt].mx=d[rt].sum=a[l];
	d[rt].numn=d[rt].numx=1;
	d[rt].cmx=-inf;d[rt].cmn=inf;
	return ;
    }
    int mid=(l+r)>>1;
    built(rt<<1,l,mid);
    built(rt<<1|1,mid+1,r);
    up(rt);
}

void operator1(int rt,int l,int r,int ql,int qr,ll x){
    if(ql<=l&&r<=qr){
	d[rt].mn+=x;d[rt].mx+=x;d[rt].sum+=1ll*(r-l+1)*x;
	if(d[rt].cmx!=-inf&&d[rt].cmn!=inf)d[rt].cmx+=x,d[rt].cmn+=x;
	d[rt].flag+=x;
	return ;
    }
    int mid=(l+r)>>1;
    push(rt,l,r);
    if(ql<=mid)operator1(rt<<1,l,mid,ql,qr,x);
    if(qr>mid)operator1(rt<<1|1,mid+1,r,ql,qr,x);
    up(rt);
   // cout<<l<<"====="<<r<<" "<<d[rt].mx<<" "<<d[rt].cmx<<" "<<d[rt].mn<<" "<<d[rt].cmn<<" "<<d[rt].sum<<endl;
    //cout<<l<<":::::"<<mid<<endl;
    //cout<<l<<"====="<<mid<<" "<<d[rt<<1].mx<<" "<<d[rt<<1].cmx<<" "<<d[rt<<1].mn<<" "<<d[rt<<1].cmn<<" "<<d[rt<<1].sum<<" "<<d[rt<<1].flag<<endl;
}

void operator2(int rt,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){
	if(d[rt].mn>=x)return ;
	else if(d[rt].cmn>x){
	    if(d[rt].mn==d[rt].cmx)d[rt].cmx=x;
	    if(d[rt].cmx==-inf&&d[rt].cmn==inf)d[rt].mx=x;
	    d[rt].sum+=1ll*(x-d[rt].mn)*d[rt].numn,d[rt].mn=x;
	    return ;
	}
    }
    int mid=(l+r)>>1;
    push(rt,l,r);
    if(ql<=mid)operator2(rt<<1,l,mid,ql,qr,x);
    if(qr>mid)operator2(rt<<1|1,mid+1,r,ql,qr,x);
    up(rt);
   // cout<<l<<":::"<<r<<" "<<d[rt].mx<<" "<<d[rt].cmx<<" "<<d[rt].mn<<" "<<d[rt].cmn<<" "<<d[rt].sum<<endl;
     // cout<<l<<":::"<<mid<<" "<<d[rt<<1].mx<<" "<<d[rt<<1].cmx<<" "<<d[rt<<1].mn<<" "<<d[rt<<1].cmn<<" "<<d[rt<<1].sum<<endl;
     // cout<<mid+1<<":::"<<r<<" "<<d[rt<<1|1].mx<<" "<<d[rt<<1|1].cmx<<" "<<d[rt<<1|1].mn<<" "<<d[rt<<1|1].cmn<<" "<<d[rt<<1|1].sum<<endl;
}

void operator3(int rt,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){
	if(d[rt].mx<=x)return ;
	else if(d[rt].cmx<x){
	    if(d[rt].mx==d[rt].cmn)d[rt].cmn=x;
	    if(d[rt].cmx==-inf&&d[rt].cmn==inf)d[rt].mn=x;
	    d[rt].sum-=1ll*(d[rt].mx-x)*d[rt].numx,d[rt].mx=x;
	    return ;
	}
    }
    int mid=(l+r)>>1;
    push(rt,l,r);
    if(ql<=mid)operator3(rt<<1,l,mid,ql,qr,x);
    if(qr>mid)operator3(rt<<1|1,mid+1,r,ql,qr,x);
    up(rt);
   // cout<<"sb:::"<<endl;
    //cout<<l<<":::"<<r<<" "<<d[rt].mx<<" "<<d[rt].cmx<<" "<<d[rt].mn<<" "<<d[rt].cmn<<" "<<d[rt<<1].sum<<" "<<d[rt<<1|1].sum<<endl;
}

ll ans;
void operator4(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){ans+=d[rt].sum;return ;}
    int mid=(l+r)>>1;
    push(rt,l,r);
    if(ql<=mid)operator4(rt<<1,l,mid,ql,qr);
    if(qr>mid)operator4(rt<<1|1,mid+1,r,ql,qr);
    up(rt);
}

void operator5(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){ans=max(1ll*d[rt].mx,ans);return ;}
    int mid=(l+r)>>1;
    //cout<<l<<"::::"<<r<<" "<<d[rt<<1].mx<<" "<<d[rt<<1|1].mx<<endl;
    push(rt,l,r);
   // cout<<l<<"===="<<r<<" "<<d[rt<<1].mx<<" "<<d[rt<<1|1].mx<<endl;
    if(ql<=mid)operator5(rt<<1,l,mid,ql,qr);
    if(qr>mid)operator5(rt<<1|1,mid+1,r,ql,qr);
    up(rt);
}

void operator6(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){ans=min(ans,1ll*d[rt].mn);return ;}
    int mid=(l+r)>>1;
   // cout<<l<<"-----"<<r<<" "<<d[rt<<1].mn<<" "<<d[rt<<1|1].mn<<endl;
    push(rt,l,r);
   // cout<<l<<"====="<<r<<" "<<d[rt<<1].mn<<" "<<d[rt<<1|1].mn<<endl;
    if(ql<=mid)operator6(rt<<1,l,mid,ql,qr);
    if(qr>mid)operator6(rt<<1|1,mid+1,r,ql,qr);
    up(rt);
}

int main(){
    int n=read();
    inc(i,1,n)a[i]=read();
    built(1,1,n);
    int m=read();
    int op,l,r;ll x;
    while(m--){
	op=read();l=read();r=read();
	if(op==1)x=read(),operator1(1,1,n,l,r,x);
	else if(op==2)x=read(),operator2(1,1,n,l,r,x);
	else if(op==3)x=read(),operator3(1,1,n,l,r,x);
	else if(op==4)ans=0,operator4(1,1,n,l,r),printf("%lld\n",ans);
	else if(op==5)ans=-inf,operator5(1,1,n,l,r),printf("%lld\n",ans);
	else ans=inf,operator6(1,1,n,l,r),printf("%lld\n",ans);
    }
    return 0;
}

　

4695: 最假女选手

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 932  Solved: 250
[Submit][Status][Discuss]

Description

在刚刚结束的水题嘉年华的压轴节目放水大赛中，wyywyy如愿以偿的得到了最假女选手的奖项。但是作为主办人的
C_SUNSHINE为了证明wyywyy确实在放水，决定出一道基础题考察wyywyy的姿势水平。给定一个长度为 N序列，编号
从1 到 N。要求支持下面几种操作：
1.给一个区间[L,R] 加上一个数x 
2.把一个区间[L,R] 里小于x 的数变成x 
3.把一个区间[L,R] 里大于x 的数变成x 
4.求区间[L,R] 的和
5.求区间[L,R] 的最大值
6.求区间[L,R] 的最小值

 

Input

第一行一个整数 N表示序列长度。
第二行N 个整数Ai 表示初始序列。
第三行一个整数M 表示操作个数。
接下来M 行，每行三或四个整数，第一个整数Tp 表示操作类型，接下来L,R,X 或L,R 表述操作数。
1<=tp<=6,N,M<=5*10^5,|Ai|<=10^8
Tp=1时,|x|<=1000
Tp=2或3时，|x|<=10^8

 

Output

对于每个4,5,6类型的操作输出一行一个整数表示答案。

 

Sample Input

2
1 2
2
2 1 2 2
4 1 2

Sample Output

4

 

[BZOJ]4695: 最假女选手

原文：https://www.cnblogs.com/wang9897/p/10336011.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！