| 记录编号 |
338755 |
评测结果 |
AAAAAAAAAAT |
| 题目名称 |
快速红包变换 |
最终得分 |
90 |
| 用户昵称 |
 Hzoi_Go灬Fire |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
3.231 s |
| 提交时间 |
2016-11-05 15:12:29 |
内存使用 |
16.34 MiB |
显示代码纯文本
/*
Name: 快速红包变换
Copyright:
From：cogs
Author: Go灬Fire
Date: 05/11/16 15:10
Description: 如果说旅游是树剖大全，那么此题就是线段树大全，无与伦比宇宙无敌
精华在于两个Lazy标记，一个是修改一个是覆盖，两个lazy不能共存（Update要清空其中一个）
覆盖的优先级比修改的优先级要高，提高自信！！！！！
*/
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stdio.h>
using namespace std;
#define LL long long
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define Begin freopen("redbag.in","r",stdin);freopen("redbag.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
const int maxn=150000;
struct Node{
int date,maxnum,minnum,max,min;
int lazy1,lazy2;//lazy1是修改，lazy2是覆盖
}a[maxn<<2];
int n,m;
inline int Read(){
int x,f=1;char ch;
while(ch=getchar(), (ch<'0' || ch>'9') && ch!='-');
if(ch=='-')f=-1,ch=getchar();x=ch-48;
while(ch=getchar() ,ch>='0' && ch<='9')x=x*10+ch-48;
return x;
}
inline void Update(int rt,int l,int r){
if(a[rt].lazy2){
int z=a[rt].lazy2,mid=(l+r)>>1;a[rt].lazy1=a[rt].lazy2=0;
a[rt<<1].date=z*(mid-l+1);a[rt<<1|1].date=z*(r-mid);
a[rt<<1].minnum=a[rt<<1].maxnum=mid-l+1;a[rt<<1|1].minnum=a[rt<<1|1].maxnum=r-mid;
a[rt<<1].max=a[rt<<1].min=a[rt<<1|1].max=a[rt<<1|1].min=z;
a[rt<<1].lazy1=a[rt<<1|1].lazy1=0;a[rt<<1].lazy2=a[rt<<1|1].lazy2=z;
}
else {
int z=a[rt].lazy1,mid=(l+r)>>1;a[rt].lazy1=a[rt].lazy2=0;
a[rt<<1].date+=z*(mid-l+1);a[rt<<1|1].date+=z*(r-mid);
//----------------这个扯淡的UPDATE让我无语了------------------//
if(a[rt<<1].lazy2){a[rt<<1].lazy2+=z+a[rt<<1].lazy1;a[rt<<1].lazy1=0;}
else a[rt<<1].lazy1+=z;
if(a[rt<<1|1].lazy2){a[rt<<1|1].lazy2+=z+a[rt<<1|1].lazy1;a[rt<<1|1].lazy1=0;}
else a[rt<<1|1].lazy1+=z;
a[rt<<1].max+=z;a[rt<<1].min+=z;a[rt<<1|1].min+=z;a[rt<<1|1].max+=z;
}
}
inline void pushup(int rt){
a[rt].date=a[rt<<1].date+a[rt<<1|1].date;
if(a[rt<<1].max==a[rt<<1|1].max){a[rt].max=a[rt<<1].max;a[rt].maxnum=a[rt<<1].maxnum+a[rt<<1|1].maxnum;}
else {
if(a[rt<<1].max>a[rt<<1|1].max){a[rt].max=a[rt<<1].max;a[rt].maxnum=a[rt<<1].maxnum;}
else {a[rt].max=a[rt<<1|1].max;a[rt].maxnum=a[rt<<1|1].maxnum;}
}
if(a[rt<<1].min==a[rt<<1|1].min){a[rt].min=a[rt<<1].min;a[rt].minnum=a[rt<<1].minnum+a[rt<<1|1].minnum;}
else {
if(a[rt<<1].min<a[rt<<1|1].min){a[rt].min=a[rt<<1].min;a[rt].minnum=a[rt<<1].minnum;}
else {a[rt].min=a[rt<<1|1].min;a[rt].minnum=a[rt<<1|1].minnum;}
}
}
inline void Build(int rt,int l,int r){
if(l==r){
scanf("%d",&a[rt].date);
a[rt].max=a[rt].min=a[rt].date;
a[rt].maxnum=a[rt].minnum=1;
return;
}
int mid=(l+r)>>1;
Build(lson);Build(rson);
pushup(rt);
}
inline void Tree_change(int s,int t,int z,int rt,int l,int r){
if(s<=l && t>=r){
a[rt].date=(r-l+1)*z;a[rt].lazy2=z;a[rt].lazy1=0;
a[rt].max=a[rt].min=z;
a[rt].maxnum=a[rt].minnum=r-l+1;
return;
}
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
int mid=(l+r)>>1;
if(s<=mid)Tree_change(s,t,z,lson);
if(t>mid)Tree_change(s,t,z,rson);
pushup(rt);
}
inline void Tree_add(int s,int t,int z,int rt,int l,int r){
if(s<=l && t>=r){
a[rt].date+=z*(r-l+1);
a[rt].max+=z;a[rt].min+=z;
if(a[rt].lazy2)a[rt].lazy2+=z;else a[rt].lazy1+=z;
return;
}
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
int mid=(l+r)>>1;
if(s<=mid)Tree_add(s,t,z,lson);
if(t>mid)Tree_add(s,t,z,rson);
pushup(rt);
}
inline int Tree_sum(int s,int t,int rt,int l,int r){
if(s<=l && t>=r)return a[rt].date;
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
int mid=(l+r)>>1;
if(t<=mid)return Tree_sum(s,t,lson);
if(s>mid)return Tree_sum(s,t,rson);
return Tree_sum(s,t,lson)+Tree_sum(s,t,rson);
}
inline int Tree_max(int s,int t,int rt,int l,int r){
if(s<=l && t>=r)return a[rt].max;
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
int mid=(l+r)>>1;
if(t<=mid)return Tree_max(s,t,lson);
if(s>mid)return Tree_max(s,t,rson);
return max(Tree_max(s,t,lson),Tree_max(s,t,rson));
}
inline int Tree_min(int s,int t,int rt,int l,int r){
if(s<=l && t>=r)return a[rt].min;
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
int mid=(l+r)>>1;
if(t<=mid)return Tree_min(s,t,lson);
if(s>mid)return Tree_min(s,t,rson);
return min(Tree_min(s,t,lson),Tree_min(s,t,rson));
}
inline int Tree_maxnum(int s,int t,int rt,int l,int r){
if(s<=l && t>=r)return a[rt].maxnum;
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
int mid=(l+r)>>1;
if(t<=mid)return Tree_maxnum(s,t,lson);
if(s>mid)return Tree_maxnum(s,t,rson);
int maxlson=Tree_max(s,t,lson),maxrson=Tree_max(s,t,rson);
if(maxlson==maxrson)return Tree_maxnum(s,t,lson)+Tree_maxnum(s,t,rson);
if(maxlson>maxrson)return Tree_maxnum(s,t,lson);
if(maxlson<maxrson)return Tree_maxnum(s,t,rson);
}
inline int Tree_minnum(int s,int t,int rt,int l,int r){
if(s<=l && t>=r)return a[rt].minnum;
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
int mid=(l+r)>>1;
if(t<=mid)return Tree_minnum(s,t,lson);
if(s>mid)return Tree_minnum(s,t,rson);
int minlson=Tree_min(s,t,lson),minrson=Tree_min(s,t,rson);
if(minlson==minrson)return Tree_minnum(s,t,lson)+Tree_minnum(s,t,rson);
if(minlson<minrson)return Tree_minnum(s,t,lson);
if(minlson>minrson)return Tree_minnum(s,t,rson);
}
inline void Tree_bmax(int s,int t,int z,int rt,int l,int r){
if(l==r){
a[rt].date=max(a[rt].date,z);a[rt].max=a[rt].min=a[rt].date;
a[rt].maxnum=a[rt].minnum=1;
return;
}
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
if(s<=l && t>=r){
if(a[rt].min>=z)return;
if(a[rt].max<=z){Tree_change(l,r,z,1,1,n);return;}
}
int mid=(l+r)>>1;
if(s<=mid)Tree_bmax(s,t,z,lson);
if(t>mid)Tree_bmax(s,t,z,rson);
pushup(rt);
}
inline void Tree_bmin(int s,int t,int z,int rt,int l,int r){
if(l==r){
a[rt].date=min(a[rt].date,z);a[rt].max=a[rt].min=a[rt].date;
a[rt].maxnum=a[rt].minnum=1;
return;
}
if(a[rt].lazy1 || a[rt].lazy2)Update(rt,l,r);
if(s<=l && t>=r){
if(a[rt].max<=z)return;
if(a[rt].min>=z){Tree_change(l,r,z,1,1,n);return;}
}
int mid=(l+r)>>1;
if(s<=mid)Tree_bmin(s,t,z,lson);
if(t>mid)Tree_bmin(s,t,z,rson);
pushup(rt);
}
inline void Init(void);
int main(){
Begin;
Init();
getchar();getchar();
End;
return 0;
}
inline void Init(){
scanf("%d",&n);
Build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++){
char aaa[16];scanf("%s",aaa);string type=aaa;
int s,t;scanf("%d%d",&s,&t);int z;
if(type=="Qsum")printf("%d\n",Tree_sum(s,t,1,1,n));
if(type=="Qwmax")printf("%d\n",Tree_max(s,t,1,1,n));
if(type=="Qwmin")printf("%d\n",Tree_min(s,t,1,1,n));
if(type=="Qnmax")printf("%d\n",Tree_maxnum(s,t,1,1,n));
if(type=="Qnmin")printf("%d\n",Tree_minnum(s,t,1,1,n));
if(type=="Cchange"){
scanf("%d",&z);Tree_change(s,t,z,1,1,n);
}
if(type=="Cadd"){
scanf("%d",&z);Tree_add(s,t,z,1,1,n);
}
if(type=="Cbmax"){
scanf("%d",&z);Tree_bmax(s,t,z,1,1,n);
}
if(type=="Cbmin"){
scanf("%d",&z);Tree_bmin(s,t,z,1,1,n);
}
}
}
/*
6
3 4 5 7 1 3
4
Cadd 1 3 2
Cbmin 1 3 6
Qsum 1 3
Qwmin 1 3
*/