| 记录编号 |
433366 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HZOI 2015]聪聪的世界 |
最终得分 |
100 |
| 用户昵称 |
 Hzoi_QTY |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
15.055 s |
| 提交时间 |
2017-08-05 11:03:55 |
内存使用 |
168.16 MiB |
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 1000000
using namespace std;
ll n,m,a[N+5],b[N+5];
struct node
{
ll l,r,h,k,lazy;
} t[4*N+5];
ll read()
{
ll sum=0,f=1;char x=getchar();
while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}
return sum*f;
}
inline void pushup(ll x)
{
t[x].h=max(t[x*2].h,t[x*2+1].h);
t[x].k=min(t[x*2].k,t[x*2+1].k);
}
inline void pushdown(ll x)
{
ll l=t[x].lazy;
t[x*2].h+=l;t[x*2].k+=l;t[x*2].lazy+=l;
t[x*2+1].h+=l;t[x*2+1].k+=l;t[x*2+1].lazy+=l;
t[x].lazy=0;
}
inline void build(ll l,ll r,ll x)
{
t[x].l=l;t[x].r=r;t[x].lazy=0;
if(l==r)
{
t[x].k=t[x].h=a[l];
b[l]=x;
return ;
}
ll mid=(l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
pushup(x);
}
inline void pllus(ll l,ll r,ll k,ll x)
{
if(t[x].l>=l&&t[x].r<=r)
{
t[x].h+=k;t[x].k+=k;
t[x].lazy+=k;
return;
}
if(t[x].lazy)pushdown(x);
ll mid=(t[x].l+t[x].r)/2;
if(l<=mid) pllus(l,r,k,x*2);
if(r>mid) pllus(l,r,k,x*2+1);
if(t[x].l!=t[x].r)
pushup(x);
}
void wohh(ll x)
{
if(x!=1)
wohh(x/2);
if(t[x].lazy&&t[x].l!=t[x].r)
pushdown(x);
}
inline void change(ll x,ll y)
{
ll f;
wohh(b[x]);
wohh(b[y]);
f=t[b[x]].h;
pllus(x,x,t[b[y]].h-t[b[x]].h,1);
pllus(y,y,f-t[b[y]].h,1);
}
inline ll min_ldown(ll k,ll x)
{
if(t[x].l==t[x].r)
return t[x].h;
if(t[x].lazy&&t[x].l!=t[x].r)pushdown(x);
if(t[x*2+1].k<k)
return min_ldown(k,x*2+1);
else
return min_ldown(k,x*2);
}
inline ll min_lup(ll k,ll x)
{
if(x==1)return -1;
if(x&1)
{
if(t[x^1].k<k)
return min_ldown(k,x^1);
else
return min_lup(k,x/2);
}
else
return min_lup(k,x/2);
}
inline ll min_rdown(ll k,ll x)
{
if(t[x].l==t[x].r)
return t[x].h;
if(t[x].lazy&&t[x].l!=t[x].r)pushdown(x);
if(t[x*2].k<k)
return min_rdown(k,x*2);
else
return min_rdown(k,x*2+1);
}
inline ll min_rup(ll k,ll x)
{
if(x==1)return -1;
if(!(x&1))
{
if(t[x^1].k<k)
return min_rdown(k,x^1);
else
return min_rup(k,x/2);
}
else
return min_rup(k,x/2);
}
inline ll max_rdown(ll k,ll x)
{
if(t[x].l==t[x].r)
return t[x].h;
if(t[x].lazy&&t[x].l!=t[x].r)pushdown(x);
if(t[x*2].h>k)
return max_rdown(k,x*2);
else
return max_rdown(k,x*2+1);
}
inline ll max_rup(ll k,ll x)
{
if(x==1)return -1;
if(!(x&1))
{
if(t[x^1].h>k)
return max_rdown(k,x^1);
else
return max_rup(k,x/2);
}
else
return max_rup(k,x/2);
}
inline ll max_ldown(ll k,ll x)
{
if(t[x].l==t[x].r)
return t[x].h;
if(t[x].lazy&&t[x].l!=t[x].r)pushdown(x);
if(t[x*2+1].h>k)
return max_ldown(k,x*2+1);
else
return max_ldown(k,x*2);
}
inline ll max_lup(ll k,ll x)
{
if(x==1)return -1;
if((x&1))
{
if(t[x^1].h>k)
return max_ldown(k,x^1);
else
return max_lup(k,x/2);
}
else
return max_lup(k,x/2);
}
int yjn()
{
freopen("ccsworld.in","r",stdin);
freopen("ccsworld.out","w",stdout);
/*int __size__=128<<20;
char *__p__=(char*)malloc(__size__)+__size__;
__asm__("movl %0, %%esp\n"::"r"(__p__));*/
n=read();m=read();
ll op,x,y,z;
for(ll i=1;i<=n;i++)a[i]=read();
build(1,n,1);
while(m--)
{
op=read();x=read();
switch(op)
{
case 1 :wohh(b[x]);printf("%lld\n",min_lup(t[b[x]].h,b[x]));break;
case 2 :wohh(b[x]);printf("%lld\n",max_lup(t[b[x]].h,b[x]));break;
case 3 :wohh(b[x]);printf("%lld\n",min_rup(t[b[x]].h,b[x]));break;
case 4 :wohh(b[x]);printf("%lld\n",max_rup(t[b[x]].h,b[x]));break;
case 5 :y=read();change(x,y);break;
case 6 :y=read();z=read();pllus(x,y,z,1);break;
case 7 :y=read();z=read();pllus(x,y,-z,1);break;
}
}
}
int qty=yjn();
int main(){;}