F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 5042 >> tmd这题数据范围有问题???
Rose_max @ 2017-09-21 12:43:09
[ Quote ] [ Edit ] [ Delete ] 1#
st表开标准范围直接爆空间
线段树爆时间
逗我???删了吧这题
czqqqaq @ 2017-09-21 14:08:37
[ Quote ] [ Edit ] [ Delete ] 2#
这个题你为什么不写O(n)RMQ呢
dcy11011 @ 2017-09-21 14:09:32
[ Quote ] [ Edit ] [ Delete ] 3#
GCD活摘智商又添新的铁证
hhhwsqhhh @ 2017-09-21 14:16:58
[ Quote ] [ Edit ] [ Delete ] 4#
有问题的话之前的人是怎么过的...
nzhtl1477 @ 2017-09-21 14:17:08
[ Quote ] [ Edit ] [ Delete ] 5#
你们啊,Naive!
zhonghaoxi @ 2017-09-21 14:17:31
[ Quote ] [ Edit ] [ Delete ] 6#
你们啊,Naive!
lyzy @ 2017-09-21 14:18:03
[ Quote ] [ Edit ] [ Delete ] 7#
你们啊,Naive!
wxh0109010 @ 2017-09-21 14:18:09
[ Quote ] [ Edit ] [ Delete ] 8#
你们啊,Naive!
cx_riaive @ 2017-09-21 14:18:17
[ Quote ] [ Edit ] [ Delete ] 9#
你们啊,Naive!
wxh0I0910 @ 2017-09-21 14:18:40
[ Quote ] [ Edit ] [ Delete ] 10#
你们啊,Naive!
dalao @ 2017-09-21 14:18:48
[ Quote ] [ Edit ] [ Delete ] 11#
你们啊,Naive!
yjqqqqaq @ 2017-09-21 14:18:56
[ Quote ] [ Edit ] [ Delete ] 12#
你们啊,Naive!
Nikolai @ 2017-09-21 14:19:07
[ Quote ] [ Edit ] [ Delete ] 13#
哎,那是lxl的活儿。
hhhhhhh @ 2017-09-21 14:19:22
[ Quote ] [ Edit ] [ Delete ] 14#
你们啊,Naive!
czqqqwq @ 2017-09-21 14:20:18
[ Quote ] [ Edit ] [ Delete ] 15#
你们啊,Naive!
Leokery @ 2017-09-21 14:39:55
[ Quote ] [ Edit ] [ Delete ] 16#
破!
Zcysky @ 2017-09-21 14:58:04
[ Quote ] [ Edit ] [ Delete ] 17#
你们啊,Naive!
Simpson @ 2017-09-21 17:39:36
[ Quote ] [ Edit ] [ Delete ] 18#
你们啊,Naive!
Rose_max @ 2017-09-21 18:57:33
[ Quote ] [ Edit ] [ Delete ] 19#
怎么写O(n)的RMQ???
分块??
不懂
99999999999999999999 @ 2017-09-21 19:19:44
[ Quote ] [ Edit ] [ Delete ] 20#
@zkw
czqqqaq @ 2017-09-21 19:22:30
[ Quote ] [ Edit ] [ Delete ] 21#
离线RMQ的近似线性算法
hhhwsqhhh @ 2017-09-21 19:22:55
[ Quote ] [ Edit ] [ Delete ] 22#
自己上网百度啊...
Star_Feel @ 2017-09-21 19:47:50
[ Quote ] [ Edit ] [ Delete ] 23#
你们啊,Naive!
Rose_max @ 2017-09-21 19:50:07
[ Quote ] [ Edit ] [ Delete ] 24#
%%%%大佬大佬。。受教了
Rose_max @ 2017-09-23 16:26:00
[ Quote ] [ Edit ] [ Delete ] 25#
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int mn[15][3000001],s[3000001],Log[3000001];
int ans[1500001];
int x[1500001],y[1500001],k[1500001];
int n,m;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void premn()
{
//mn[i][j]=min(mn[i-1][j],mn[i-1][j+1<<i])
Log[0]=-1;
for(int i=1;i<=n;i++)Log[i]=Log[i/2]+1;
for(int i=1;(1<<i)<=n && i<=14;i++)
for(int j=1;j+(1<<i)-1<=n && j<=n;j++)
{
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
}
}
void premx()
{
for(int i=1;i<=n;i++)mn[0][i]=s[i];
for(int i=1;(1<<i)<=n && i<=14;i++)
for(int j=1;j+(1<<i)-1<=n && j<=n;j++)
{
mn[i][j]=max(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
}
}
int main()
{
freopen("naive.in","r",stdin);
freopen("naive.out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;i++){mn[0][i]=s[i]=read();}

premn();int tmp=0;
for(int i=1;i<=m;i++)
{
int op=read(),xx=read(),yy=read();
if(op==1)
{
int kk=Log[yy-xx+1];
ans[i]=min(mn[kk][xx],mn[kk][yy-(1<<kk)+1]);
}
else
{
tmp++;
x[tmp]=xx;y[tmp]=yy;k[tmp]=i;
}
}
premx();
for(int i=1;i<=tmp;i++)
{
int kk=Log[y[i]-x[i]+1];
ans[k[i]]=max(mn[kk][x[i]],mn[kk][y[i]-(1<<kk)+1]);
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}

一脸懵我觉得O(2nlogn)应该过得了吧。。
OwenOwl @ 2017-10-24 19:23:05
[ Quote ] [ Edit ] [ Delete ] 26#
你们啊,Naive!
[Top] [Previous Page] [Next Page]

HOME Back