A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2006 [NOI2010] 超级钢琴 堆 主席树
发表于: | 分类: Oi | 评论:0 | 阅读:59

论前缀的前缀数组下标算不明白的危害系列

这题……比较裸吧,学弟问的我就说一下,首先化成前缀和的形式,然后对于一个位置,我们考虑他作为一个右端点的时候对于答案的贡献。

显然最开始的时候一定是选择一个前面最小的,然后如果选出最小的就选次小的……

支持区间查询第k大,主席树就行了;支持动态维护最大值,堆就行了。然后就简单了嘛。没看懂的再看看代码就行了

注意你是对前缀和维护一个有前缀性质的线段树,所以好好算算数组下标,注意 $sum_0$ 的存在

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5+5;
const int Maxm = 20*N;
#define mp make_pair 
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<<1)+(x<<3)+ch-'0';ch = getchar();} 
    return x*f;
}

priority_queue <pair<int,int> > q;
int sum[N],now[N],tt,root[N],T[N];
int tr[Maxm],ls[Maxm],rs[Maxm],sz;

void change(int x,int &y,int L,int R,int val){
    y = ++sz; ls[y] = ls[x], rs[y] = rs[x], tr[y] = tr[x] + 1;
    if(L == R) return;
    int mid = (L+R) >> 1;
    if(val <= mid) change(ls[x],ls[y],L,mid,val);
    else change(rs[x],rs[y],mid+1,R,val);
}

int ask(int x,int y,int L,int R,int k){
    if(L == R) return T[L];
    int mid = (L+R) >> 1,
        tmp = tr[ls[y]] - tr[ls[x]];
    if(k <= tmp) return ask(ls[x],ls[y],L,mid,k);
    else return ask(rs[x],rs[y],mid+1,R,k-tmp);
}

inline int find(int x){
    int l = 1, r = tt;
    while(l <= r){
        int mid = (l+r) >> 1;
        if(T[mid] == x) return mid;
        if(T[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int main(){
    int n = read(), k = read(), l = read(), r = read(), L,R,tmp,pos;
    for(int i=2;i<=n+1;++i) sum[i] = read()+sum[i-1];
    for(int i=1;i<=n+1;++i) T[++::tt] = sum[i];
    sort(T+1,T+::tt+1); T[::tt=1] = T[1];
    for(int i=2;i<=n+1;++i) if(T[i] != T[i-1]) T[++::tt] = T[i];
    for(int i=1;i<=n+1;++i) sum[i] = find(sum[i]);
    for(int i=1;i<=n+1;++i) change(root[i-1],root[i],1,::tt,sum[i]);
    for(int i=l+1;i<=n+1;++i) {
        L = i - r + 1;
        R = i - l + 1;
        L = max(L,2);
        tmp = ask(root[L-2],root[R-1],1,::tt,++now[i]);
        q.push(mp(T[sum[i]]-tmp,i));
//      cout << i << " " << T[sum[i]] - tmp << endl;
    }
    pair <int,int> tt;
    long long ans = 0;
    for(int i=1;i<=k;++i) {
        tt = q.top(); q.pop(); pos = tt.second, ans += tt.first;
//      cout << tt.first << " " << pos << endl;
        L = pos - r + 1;
        R = pos - l + 1;
        L = max(L,2);
        if(R-L+1!=now[pos]) {
            tmp = ask(root[L-2],root[R-1],1,::tt,++now[pos]);
            q.push(mp(T[sum[pos]]-tmp,pos));
        }
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP