2021 中庸之道

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 查看运行结果

 

 

题目描述 

Description

给定一个长度为N的序列，有Q次询问，每次询问区间[L,R]的中位数。

数据保证序列中任意两个数不相同，且询问的所有区间长度为奇数。

输入描述 

Input Description

第一行为N，Q。

第二行N个数表示序列。

接下来Q行，每行为L，R，表示一次询问。

输出描述 

Output Description

输出Q行，对应每次询问的中位数。

样例输入 

Sample Input

5 3

1 4 8 16 2

1 5

3 5

3 3

样例输出 

Sample Output

4

8

8

数据范围及提示 

Data Size & Hint

40%的数据，N，Q≤100；

70%的数据，N≤100；

100%的数据，N≤1000，Q≤100000，序列中的元素为1到10^9之间的整数。

分类标签 Tags 

傻逼了，自己手写快排，忘了c++自带sort，哎~~

/*c++sort最后一个点TLE，不知道为什么*/#include
         
          #include
          
           using namespace std;const int maxn=10010;int a[maxn],d[maxn];int n,m,b,c;int main(){     scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++) scanf("%d",a+i);     for(int i=1;i<=n;i++) d[i]=a[i];     for(int i=1;i<=m;i++){         scanf("%d%d",&b,&c);        sort(a+b,a+c+1);         printf("%d\n",a[b+c>>1]);         for(int i=1;i<=n;i++) a[i]=d[i];     }     return 0;}
          
         

 由此可见 STL sort 也就这样 1000*10000*log₂(1000)=TLE

不能AC的原因 看《紫书》STL篇章

 

AC代码

手写快排+分治

#include
         
          #include
          
           #include
           
            #define s first#define e secondusing namespace std;const int N=1e6+10;const int M=1e3+10;int n,m,b,c,smid,a[M],d[M];pair
            
             q[N];inline int read(){    register int x=0,f=1;    register 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 swap(int &x,int &y){    int t=x;x=y;y=t;}void kp(int l,int r){    int i=l,j=r,mid=a[i+j>>1];    while(i<=j){        while(a[i]
             
              mid) j--;        if(i<=j){            swap(a[i],a[j]);            i++;j--;        }    }    if(i
              
               <=smid) kp(i,r); if(l
               
                =smid) kp(l,j);}int main(){ n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); memcpy(d,a,sizeof a); for(int i=1;i<=m;i++) q[i].s=read(),q[i].e=read(); for(int i=1;i<=m;i++){ b=q[i].s;c=q[i].e;smid=(b+c>>1); kp(b,c); printf("%d\n",a[smid]); memcpy(a,d,sizeof d); } return 0;}
               
              
             
            
           
          
         

stl:nth_element

#include
         
          #include
          
           #include
           
            #define s first#define e secondusing namespace std;const int N=1e6+10;const int M=1e3+10;int n,m,a[M],d[M];pair
            
             q[N];inline int read(){    register int x=0,f=1;    register 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;}int main(){    n=read();m=read();    for(int i=1;i<=n;i++) a[i]=read();    memcpy(d,a,sizeof a);    for(int i=1;i<=m;i++) q[i].s=read(),q[i].e=read();    for(int i=1,l,r,mid;i<=m;i++){        l=q[i].s;r=q[i].e;mid=(l+r>>1);        nth_element(a+l,a+mid,a+r+1);        printf("%d\n",a[mid]);        memcpy(a,d,sizeof d);    }    return 0;}
            
           
          
         

 主席树

 

#include
         
          #include
          
           using namespace std;inline const int read(){    register int x=0,f=1;    register char ch=getchar();    while(ch>'9'||ch<'0'){
       if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}const int M=1e3+10;const int N=M*20;int tot,sum[N],ls[N],rs[N],san[M],num[M],T[M];void build(int &rt,int l,int r){    rt=++tot;    if(l==r) return ;    int mid=l+r>>1;    build(ls[rt],l,mid);    build(rs[rt],mid+1,r);}void updata(int &rt,int last,int l,int r,int p){    rt=++tot;    ls[rt]=ls[last];    rs[rt]=rs[last];    sum[rt]=sum[last]+1;    if(l==r) return ;    int mid=l+r>>1;    p<=mid?updata(ls[rt],ls[last],l,mid,p):updata(rs[rt],rs[last],mid+1,r,p);}int query(int l,int r,int x,int y,int k){    if(l==r) return l;    int mid=l+r>>1;    int cnt=sum[ls[y]]-sum[ls[x]];    return k<=cnt?query(l,mid,ls[x],ls[y],k):query(mid+1,r,rs[x],rs[y],k-cnt);}int main(){    int n=read(),m=read();    for(int i=1;i<=n;i++) san[i]=num[i]=read();    stable_sort(san+1,san+n+1);    int cnt=unique(san+1,san+n+1)-(san+1);    for(int i=1;i<=n;i++) num[i]=lower_bound(san+1,san+cnt+1,num[i])-san;    build(T[0],1,cnt);    for(int i=1;i<=n;i++) updata(T[i],T[i-1],1,cnt,num[i]);    for(int i=1;i<=m;i++){        int x=read(),y=read();        int k=(y-x>>1)+1;        int id=query(1,cnt,T[x-1],T[y],k);        printf("%d\n",san[id]);    }    return 0;}