F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4695 >> 本机拍不WA交上去就WA求助
FlashHu @ 2018-09-21 21:04:26
[ Quote ] [ Edit ] [ Delete ] 1#
RT
#include<bits/stdc++.h>
#define RG register
#define R RG int
#define G if(++ip==ie)fread(ip=buf,1,N,stdin)
#define pushup \
s=lc->s+rc->s; \
mn=min(lc->mn,rc->mn); \
mx=max(lc->mx,rc->mx)
#define pushdn \
if(ls!=INF)lc->lset(ls),rc->lset(ls),ls=INF;\
if(la)lc->ladd(la),rc->ladd(la),la=0
using namespace std;
const int N=1<<20,INF=1e9;
char buf[N],*ie=buf+N,*ip=ie-1;
int op,x;
inline int in(){
G;while(*ip<'-')G;
RG bool f=*ip=='-';if(f)G;
R x=*ip&15;
G;while(*ip>'-'){x*=10;x+=*ip&15;G;}
return f?-x:x;
}
struct Node{
Node*lc,*rc;
int l,r,m,s,mn,mx,ls,la;
void build(R b,R e){//printf("[%d,%d]\n",b,e);
m=((l=b)+(r=e))>>1;ls=INF;la=0;
if(b==e){
s=mn=mx=in();return;
}
(lc=new Node)->build(l,m);
(rc=new Node)->build(m+1,r);
pushup;//this->out();
}
inline void lset(R x){
s=x*(r-l+1);mn=mx=ls=x;la=0;
}
inline void ladd(R x){
s+=x*(r-l+1);mn+=x;mx+=x;la+=x;
}
void add(R b,R e){
if(l==b&&r==e)return this->ladd(x);
pushdn;
if(e<=m)lc->add(b,e);
else if(b>m)rc->add(b,e);
else lc->add(b,m),rc->add(m+1,e);
pushup;
}
void upd(R b,R e){//printf("[%d,%d]b%d e%d\n",l,r,b,e);
if(op&1?mx<=x:mn>=x)return;
if(l==b&&r==e&&(op&1?mn>=x:mx<=x))return this->lset(x);
pushdn;
if(e<=m)lc->upd(b,e);
else if(b>m)rc->upd(b,e);
else lc->upd(b,m),rc->upd(m+1,e);
pushup;//this->out();
}
int qrys(R b,R e){
if(l==b&&r==e)return s;
pushdn;
if(e<=m)return lc->qrys(b,e);
if(b> m)return rc->qrys(b,e);
return lc->qrys(b,m)+rc->qrys(m+1,e);
}
int qrym(R b,R e){
if(l==b&&r==e)return op&1?mx:mn;
pushdn;
if(e<=m)return lc->qrym(b,e);
if(b> m)return rc->qrym(b,e);
if(op&1)return max(lc->qrym(b,m),rc->qrym(m+1,e));
return min(lc->qrym(b,m),rc->qrym(m+1,e));
}
void out(){
printf("l%d r%d m%d s%d mn%d mx%d ls%d la%d\n",l,r,m,s,mn,mx,ls,la);
}
};
int main(){
RG Node rt;rt.build(1,in());
for(R m=in(),l,r;m;--m){
op=in();l=in();r=in();
if(op<=3)x=in(),op==1?rt.add(l,r):rt.upd(l,r);
else printf("%d\n",op==4?rt.qrys(l,r):rt.qrym(l,r));
}
return 0;
}
FlashHu @ 2018-09-21 21:12:35
[ Quote ] [ Edit ] [ Delete ] 2#
傻逼了忘开longlong
iot @ 2018-09-21 22:44:16
[ Quote ] [ Edit ] [ Delete ] 3#
先orz为敬
FlashHu @ 2018-09-22 15:06:53
[ Quote ] [ Edit ] [ Delete ] 4#
这是个假的复杂度却拿了rank1的线段树
star_magic_young @ 2018-09-25 15:08:38
[ Quote ] [ Edit ] [ Delete ] 5#
orz rk1 fakehu
[Top] [Previous Page] [Next Page]

HOME Back