F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 3196 >> 本机AC,提交0msTLE???
Super_Nick @ 2018-01-24 22:46:42
[ Quote ] [ Edit ] [ Delete ] 1#
没有忘删freopen啊?为什么会这样???很绝望啊




#include<bits/stdc++.h>
#define N 50010
#define RG register
#define md ((l+r)>>1)
#define inf 0x3f3f3f3f
using namespace std;
int m,n,t,ct,lc,tt,va,p[N],rt[N],fan[N<<1];
struct node{int w,ma,mi,ls,rs;}tr[N*400];
struct ques{int k,l,r,opt,pos;}q[N];
struct numb{
int w,id;
bool operator < (const numb &x) const {
return w<x.w;
}
}nb[N<<1];
inline int gi(){
RG int x=0;RG char y=getchar();RG int z=0;
while((y<'0'||y>'9')&&y!='-') y=getchar();
if(y=='-') z=1,y=getchar();
while(y>='0'&&y<='9') x=x*10+y-'0',y=getchar();
return z?-x:x;
}
inline void modify(RG int &x,RG int l,RG int r){
if(!x) tr[x=++t]=tr[0];
tr[x].w+=va;
if(l==r){
if(tr[x].w) tr[x].ma=tr[x].mi=md;
else tr[x].ma=tr[x].mi=0;
return;
}
if(lc<=md) modify(tr[x].ls,l,md);
else modify(tr[x].rs,md+1,r);
tr[x].ma=tr[tr[x].rs].w?tr[tr[x].rs].ma:tr[tr[x].ls].ma;
tr[x].mi=tr[tr[x].ls].w?tr[tr[x].ls].mi:tr[tr[x].rs].mi;
}
inline void add(RG int x){
while(x<=n){
modify(rt[x],1,ct);
x+=x&-x;
}
}
inline int check(RG int x,RG int l,RG int r,RG int ll,RG int rr){
if(!x) return 0;
if(l==ll&&r==rr) return tr[x].w;
if(rr<=md) return check(tr[x].ls,l,md,ll,rr);
if(ll>md) return check(tr[x].rs,md+1,r,ll,rr);
return check(tr[x].ls,l,md,ll,md)+check(tr[x].rs,md+1,r,md+1,rr);
}
inline int query(RG int x,RG int l,RG int r){
if(l>r) return 0;
RG int rs=0;
while(x){
rs+=check(rt[x],1,ct,l,r);
x-=x&-x;
}
return rs;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("psh.in","r",stdin);
freopen("psh.out","w",stdout);
#endif
n=gi();m=gi();
for (RG int i=1;i<=n;++i)
nb[++tt]=(numb){gi(),i};
for (RG int i=1;i<=m;++i){
q[i].opt=gi();
if(q[i].opt!=3){q[i].l=gi();q[i].r=gi();}
else q[i].pos=gi();
if(q[i].opt!=2) nb[++tt]=(numb){gi(),i+n};
else q[i].k=gi();
}
sort(nb+1,nb+tt+1);
for (RG int i=1;i<=tt;++i){
if(i<2||nb[i].w>nb[i-1].w) fan[++ct]=nb[i].w;
if(nb[i].id>n) q[nb[i].id-n].k=ct;
else p[nb[i].id]=ct;
}
va=1;
for (RG int i=1;i<=n;++i){lc=p[i];add(i);}
for (RG int i=1;i<=m;++i)
if(q[i].opt<2)
printf("%d\n",query(q[i].r,1,q[i].k-1)-query(q[i].l-1,1,q[i].k-1)+1);
else if(q[i].opt<3){
RG int l=1,r=ct,rs;
while(l<=r){
if(query(q[i].r,1,md)-query(q[i].l-1,1,md)>=q[i].k) rs=md,r=md-1;
else l=md+1;
}
printf("%d\n",fan[rs]);
}
else if(q[i].opt<4){
lc=p[q[i].pos];va=-1;
add(q[i].pos);
lc=p[q[i].pos]=q[i].k;va=1;
add(q[i].pos);
}
else if(q[i].opt<5){
RG int l=1,r=q[i].k-1,rs;
while(l<=r)
if(query(q[i].r,md,q[i].k-1)-query(q[i].l-1,md,q[i].k-1)) rs=md,l=md+1;
else r=md-1;
printf("%d\n",fan[rs]);
}
else{
RG int l=q[i].k+1,r=ct,rs;
while(l<=r)
if(query(q[i].r,q[i].k+1,md)-query(q[i].l-1,q[i].k+1,md)) rs=md,r=md-1;
else l=md+1;
printf("%d\n",fan[rs]);
}
return 0;
}
Super_Nick @ 2018-01-24 22:49:49
[ Quote ] [ Edit ] [ Delete ] 2#
虽说nlog^3有点卡但也不至于0msTLE吧……
stl @ 2018-01-25 00:34:27
[ Quote ] [ Edit ] [ Delete ] 3#
MLE
GXZlegend @ 2018-01-25 08:04:31
[ Quote ] [ Edit ] [ Delete ] 4#
你MLE了
nzhtl1477 @ 2018-01-25 12:33:29
[ Quote ] [ Edit ] [ Delete ] 5#
orz Zer0 MS!
iloi @ 2018-01-25 18:53:30
[ Quote ] [ Edit ] [ Delete ] 6#
orz Zer0 MS!
[Top] [Previous Page] [Next Page]

HOME Back