2．第k大区间
(kth.cpp/c/pas)
时间限制：1s
内存限制：256MB
【问题描述】
定义一个长度为奇数的区间的值为其所包含的的元素的中位数。
现给出n个数，求将所有长度为奇数的区间的值排序后，第K大的值为多少。
【输入】
输入文件名为kth.in。
第一行两个数n和k
第二行，n个数。（0<=每个数<231）
【输出】
输出文件名为kth.out。
一个数表示答案。
【输入输出样例】
kth.in kth.out
4 3
3 1 2 4 2

【样例解释】
[l,r]表示区间l~r的值
[1,1]：3
[2,2]：1
[3,3]：2
[4,4]：4
[1,3]：2
[2,4]：2
【数据说明】
对于30%的数据，1<=n<=100；
对于60%的数据，1<=n<=300
对于80%的数据，1<=n<=1000
对于100%的数据，1<=n<=100000, k<=奇数区间的数

考试的时候除了暴力啥也没有想到

下面时考试代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 100005
#define M 10005
using namespace std;
int n,k;
int a[100016];
int ans[6016];
int tem[6015];
int b[100016];
int f[100016][5]; 
int maxn=0;
int l,r;
inline 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;
}
inline bool cmp(int a,int b){
    return a>b;
}
inline int lowbit(int x){
    return x&(-x);
}
inline int gsum(int x,int p){
    int s=0;
    for(register int i=x;i>0;i-=lowbit(i)) s+=f[i][p];
    return s;
}
inline void update(int x,int p){
    if(!x) return ;
    for(register int i=x;i<N;i+=lowbit(i)) f[i][p]+=1;
}
inline int cha(int val){
    memset(f,0,sizeof(f));
    b[0]=0;
    for(register int i=1;i<=n;i++){
       if(a[i]>=val) b[i]=1;
        else b[i]=0;
        b[i]+=b[i-1];
    }
    for(register int i=1;i<=n;i++) b[i]=b[i]*2-i+M;
    int s=0;
    update(M,0);
    for(register int i=1;i<=n;i++){
        s+=gsum(b[i],(i&1)^1);
        update(b[i],(i&1));
    }
    return s;
}
int main(){ 
    freopen("kth.in","r",stdin);
    freopen("kth.out","w",stdout);
    n=read();
    k=read();
    for(register int i=1;i<=n;++i){
        a[i]=read();
        if(maxn<a[i]) maxn=a[i];
    }
    if(n<=1000){
  //60分 ~80分 
        int lm;
        if(n&1) lm=n-1;
        else lm=n;
        int tot=0;
        for(register int i=1;i<=n;++i){
            ans[++tot]=a[i];
        }
        for(register int i=3;i<=lm;i+=2){
  //枚举区间长度 
            for(register int j=1;j<=n-i+1;++j){
  //枚举起点嘿嘿嘿
                int zhong=j+i-1;
                for(register int k=1;k<=n;++k){
                    tem[k]=a[k];
                }
                sort(tem+j,tem+zhong+1);
                ans[++tot]=tem[(j+zhong)/2];
            } 
        } 
        sort(ans+1,ans+tot+1,cmp);
        printf("%d",ans[k]);
        return 0;
    }
    int l=0,r=maxn,ans=0;
    while(l<=r){
  //乱写二分 
        int mid=(l+r)>>1;
        if(cha(mid)>=k) l=mid+1,ans=mid;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

这是标程

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#define N 200005
#define ll long long
using namespace std;
int a[100010];
int b[100010];
int c[2][400010];
int n;
ll k;
void add(int x,int y,int f){
    for(;x<=400000;x+=(x&(-x))){
        c[f][x]+=y;
    }
}
int query(int x,int f){
    int ret=0;
    for(;x>0;x-=(x&(-x))){
        ret+=c[f][x];
    }
    return ret;
}
bool check(int mid){
    ll ret=0;
    int tmp=0;
    memset(c,0,sizeof(c));
    add(N,1,0);
    for(int i=1;i<=n;i++){
        if(a[i]>=mid) tmp++;
        if(i&1){
            ret+=query(tmp*2-i+N,0);
            add(tmp*2-i+N,1,1);
        }
        else{
            ret+=query(tmp*2-i+N,1);
            add(tmp*2-i+N,1,0);
        }
    }
    return ret>=k;
}
int main(){
    freopen("kth.in","r",stdin);
    freopen("kth.out","w",stdout);
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int tmp=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+tmp+1,a[i])-b;
    }
    int l=1;
    int r=tmp;
    while(l+1<r){
        int mid=l+r>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    if(check(r)) cout<<b[r];
    else cout<<b[l];
    return 0;
}

主要呢，这题学会了离散化

    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int tmp=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+tmp+1,a[i])-b;
    }

unique(b+1,b+n+1)去重，并返回去重后的最后一个元素的后一位的指针，减去b(首指针)，然后再减1就是去重后的个数
a[i]=lower_bound(b+1,b+tmp+1,a[i])-b;
lower_bound(b+1,b+tmp+1,a[i])返回的是a[i]在b中的位置，减b,就没了

总结
①离散化真好写
②duan2 太强了