博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDOJ 5306 Gorgeous Sequence 线段树
阅读量:6581 次
发布时间:2019-06-24

本文共 4226 字,大约阅读时间需要 14 分钟。

Gorgeous Sequence

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 440    Accepted Submission(s): 87


Problem Description
There is a sequence 
a of length 
n. We use 
ai to denote the 
i-th element in this sequence. You should do the following three types of operations to this sequence.
0 x y t: For every 
xiy, we use 
min(ai,t) to replace the original 
ai's value.
1 x y: Print the maximum value of 
ai that 
xiy.
2 x y: Print the sum of 
ai that 
xiy.
 

Input
The first line of the input is a single integer 
T, indicating the number of testcases. 
The first line contains two integers 
n and 
m denoting the length of the sequence and the number of operations.
The second line contains 
n separated integers 
a1,,an (
1in,0ai<231).
Each of the following 
m lines represents one operation (
1xyn,0t<231).
It is guaranteed that 
T=100
n1000000, m1000000.
 

Output
For every operation of type 
1 or 
2, print one line containing the answer to the corresponding query.
 

Sample Input
 
1 5 5 1 2 3 4 5 1 1 5 2 1 5 0 3 5 3 1 1 5 2 1 5
 

Sample Output
 
5 15 3 12
Hint
Please use efficient IO method
 

Source
 

/* ***********************************************Author        :CKbossCreated Time  :2015年07月27日 星期一 08时13分39秒File Name     :HDOJ5306.cpp************************************************ */#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long int LL;const int maxn=1000030;int n,m;int a[maxn];struct Node{ LL ss; int mx,tag,cv; void toString() { printf("ss: %lld mx: %d tag: %d cv: %d\n",ss,mx,tag,cv); }}T[maxn<<2];#define lrt (rt<<1)#define rrt (rt<<1|1)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1void push_up(int rt){ T[rt].ss=T[lrt].ss+T[rrt].ss; T[rt].mx=max(T[lrt].mx,T[rrt].mx); T[rt].cv=T[lrt].cv+T[rrt].cv;}void pnc(int t,int l,int r,int rt){ if(T[rt].tag!=0&&T[rt].tag<=t) return ; int all=r-l+1; if(T[rt].cv!=all) { T[rt].ss+=(LL)t*(all-T[rt].cv); T[rt].tag=T[rt].mx=t; T[rt].cv=all; }}void push_down(int l,int r,int rt){ if(T[rt].tag) { int m=(l+r)/2; pnc(T[rt].tag,lson); pnc(T[rt].tag,rson); }}/// 清除掉全部大于t的标记void fix(int t,int l,int r,int rt){ if(T[rt].mx
=t) T[rt].tag=0; if(l==r) { T[rt].ss=T[rt].mx=T[rt].tag; T[rt].cv=T[rt].tag!=0; } else { push_down(l,r,rt); int m=(l+r)/2; fix(t,lson); fix(t,rson); push_up(rt); }}void build(int l,int r,int rt){ if(l==r) { T[rt].ss=T[rt].mx=T[rt].tag=a[l]; T[rt].cv=1; return ; } T[rt].tag=0; int m=(l+r)/2; build(lson); build(rson); push_up(rt);}/// 0void update(int L,int R,int t,int l,int r,int rt){ if(T[rt].mx<=t) return ; if(L<=l&&r<=R) { fix(t,l,r,rt); if(l==r) { T[rt].ss=T[rt].mx=T[rt].tag=t; T[rt].cv=1; } else push_up(rt); pnc(t,l,r,rt); } else { push_down(l,r,rt); int m=(l+r)/2; if(L<=m) update(L,R,t,lson); if(R>m) update(L,R,t,rson); push_up(rt); }}/// 1int query_max(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return T[rt].mx; push_down(l,r,rt); int m=(l+r)/2; int ret=0; if(L<=m) ret=max(ret,query_max(L,R,lson)); if(R>m) ret=max(ret,query_max(L,R,rson)); return ret;}/// 2LL query_sum(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return T[rt].ss; push_down(l,r,rt); int m=(l+r)/2; LL ret=0; if(L<=m) ret+=query_sum(L,R,lson); if(R>m) ret+=query_sum(L,R,rson); return ret;}void show(int l,int r,int rt){ printf("rt: %d %d <---> %d\n ",rt,l,r); T[rt].toString(); if(l==r) return ; int m=(l+r)/2; show(lson); show(rson);}/********** fast read **************/char *ch,buf[40*1024000+5];void nextInt(int& x){ x=0; for(++ch;*ch<=32;++ch); for(x=0;'0'<=*ch;ch++) x=x*10+*ch-'0';}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ch=buf-1; fread(buf,1,1000*35*1024,stdin); int T_T; nextInt(T_T); while(T_T--) { nextInt(n); nextInt(m); for(int i=1;i<=n;i++) nextInt(a[i]); build(1,n,1); int k,l,r,t; while(m--) { nextInt(k); if(k==0) { nextInt(l); nextInt(r); nextInt(t); update(l,r,t,1,n,1); } else if(k==1) { nextInt(l); nextInt(r); printf("%d\n",query_max(l,r,1,n,1)); } else if(k==2) { nextInt(l); nextInt(r); //printf("%lld\n",query_sum(l,r,1,n,1)); printf("%I64d\n",query_sum(l,r,1,n,1)); } } } return 0;}

转载地址:http://fonno.baihongyu.com/

你可能感兴趣的文章
c# WebBrowser获取cookie
查看>>
【流媒体】UPnP的工作过程
查看>>
JAVA的堆于栈
查看>>
每日英语:South India's Streetside Coffee Culture
查看>>
你可能不知道UED和UCD
查看>>
利用IFormattable接口自动参数化Sql语句
查看>>
webdriver(python)学习笔记一
查看>>
导出DC列表
查看>>
AndroidInject项目使用动态代理增加对网络请求的支持
查看>>
读<jQuery 权威指南>[5]-插件
查看>>
eclipse缺省的Server没有weblogic
查看>>
The Java serialization algorithm revealed---reference
查看>>
使用WMI来连接远端计算机
查看>>
Linux下的线程
查看>>
Fat-jar 打包,并使用 proguard 混淆代码
查看>>
[转]jquery.pagination.js分页
查看>>
C#泛类型链表的实现
查看>>
升级到WP8必需知道的13个特性
查看>>
Ext.getCmp()的简单使用
查看>>
前端样板资源概览及总评
查看>>