算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
   给长度为20000的序列。求左端点在[a,b]和右端点在[c,d]中所有的子序列,最大的中位数。
吐槽:
    1. 照着CLJ的标程和题解一点点看,终于弄懂了主席树。。。。(即可持久化线段树)
    2. 函数式编程V5。。。。。
    3. 划分树已经成为时代的眼泪了。。。。
算法分析:
    大家自己去看CLJ的论文吧。。。。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 20005;
struct info{
    int sum, mxl, mxr;
    info(){}
    info(int val){
        sum = mxl = mxr = val;
    }
};
info operator + (const info l, const info r){
    info mid ;
    mid .sum = l.sum + r.sum;
    mid .mxl = max(l.mxl , l.sum + max(r.mxl, 0 ));
    mid .mxr = max(r.mxr , r.sum + max(l.mxr, 0 ));
    return mid;
}
struct tree{
    int l,r;
    tree *pl, *pr;
    info v;
    tree (int _l, int _r, tree *_pl, tree *_pr)
    : l(_l), r(_r), pl (_pl), pr(_pr){
        v = pl->v + pr->v;
    }
    tree (int _l, int _r, int val): l(_l), r(_r){
        if(_l == _r) {
            v = info(val);
            return ;
        }
        int mid = l + r >>1;
        pl = new tree(l, mid, val);
        pr = new tree(mid+1, r, val);
        v = pl->v + pr->v;
    }
    info ask(int L,int R){
//        cout<<L<<" "<<R<<" "<<l<<" "<<r<<endl;
        if(L <= l && R >= r){
//            cout<<l<<" "<<r<<" "<<v.mxl<<" "<<v.sum<<" "<<v.mxr<<endl;
            return v;
        }
        int mid = l + r >> 1;
        if(mid < L) return pr->ask(L,R);
        else if(mid >= R) return pl->ask(L,R);
        else return pl ->ask(L,R) + pr ->ask(L,R);
    }
    tree* change(int pos, int val){
        if(l == r){
            return new tree(l,r,val);
        }
        int mid = l+r >>1;
        if(pos <= mid) return new tree(l,r,pl->change(pos,val),pr);
        return new tree(l,r,pl,pr->change(pos,val));
    }
    void OP(){
        cout<<l<<" "<<r<<" "<<v.mxl<<" "<<v.sum<<" "<<v.mxr<<endl;
        if(l==r) return;
        pl->OP();
        pr->OP();
    }
};
tree *root[N];
pair<int,int> num[N];
int a[N],n;
bool chk(int m,int a,int b,int c,int d){
    tree *rt = root[m];
    int val =  rt->ask(a, b).mxr + (b+1<c ? rt->ask(b+1,c-1).sum : 0) + rt -> ask(c,d).mxl ;
    //cout<<val<<endl;
    return val >= 0;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        num[i] = make_pair(a[i],i);
    }
    sort(num,num+n);
    root[0] = new tree(0,n-1,1);
    //for(int i=0;i<n;i++) cout<<num[i].first <<" "<<num[i].second <<" "; cout<<endl;
    for(int i=1;i<n;i++){
//        cout<<"i: "<<i<<" "<<num[i-1].second<<endl;
        root[i] = root[i-1] -> change(num[i-1].second, -1);
//        root[i]->OP();
    }
    int Q, last = 0;
    cin >>Q;
    while(Q--){
        int q[4];
        for(int i=0;i<4;i++){
            scanf("%d",&q[i]);
            q[i] = (q[i] + last) % n;
        }
        sort(q,q+4);
        int l = 0, r = n;
        while(l < r){
            int m = l+ r>>1;
    //        cout<<m<<" "<<q[0]<<" "<<q[1]<<" "<<q[2]<<" "<<q[3]<<endl;
            if(chk(m,q[0],q[1],q[2],q[3])) l = m+1;
            else r = m;
        }
        printf("%d\n",num[l-1].first);
        last = num[l-1].first;
    }
    return 0;
}
posted on 2012-06-20 16:44 西月弦 阅读(1225) 评论(5)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: bzoj 2653 二分枚举 + 可持久化线段树
2012-07-14 21:36 | 蒟蒻
CLJ的标程?请问大神在哪找的...  回复  更多评论
  
# re: bzoj 2653 二分枚举 + 可持久化线段树
2012-07-14 21:40 | 蒟蒻
还有大神,我是P转C
这是什么语法啊
tree (int _l, int _r, tree *_pl, tree *_pr)
: l(_l), r(_r), pl (_pl), pr(_pr){
v = pl->v + pr->v;
}
tree (int _l, int _r, int val): l(_l), r(_r){
提一下名称...我去百度一下...  回复  更多评论
  
# re: bzoj 2653 二分枚举 + 可持久化线段树
2012-07-14 22:44 | 西月弦
@蒟蒻
这个语法是C++构造函数
CLJ的题解我的文章里不是有超链接么...  回复  更多评论
  
# re: bzoj 2653 二分枚举 + 可持久化线段树
2012-07-15 19:07 | 蒟蒻
@西月弦
只有PDF...没有标程...  回复  更多评论
  
# re: bzoj 2653 二分枚举 + 可持久化线段树
2012-07-15 19:12 | 蒟蒻
找到了...在homework2里...但还是谢谢了...  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理