[BZOJ2006 [NOI2010]超级钢琴]【RMQ】【二叉堆】【区间裂解】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2006
【算法分析】
就是搞成前缀和数组以后写一个rmq。然后在外面套一个二叉堆每次取最大值。然后把取出的区间裂解成两半，去掉中间那个最小值元素，继续放进二叉堆里，这样就可以AC。
T_T时间排在第3名。前面两个都是JZP神牛。
【时间复杂度】O((n+m) lg (n+m))
【空间复杂度】O(n lg n + n+m)
【吐槽】
NOI的时候写得二分答案+平衡树被卡得只剩30分T_T。。。
现在高3一个月只能回一次家。。。本次是因为配眼镜为由请假回家，就找些题练练手= =，准备我巨重要的NOIP。
【CODE】
#include #include #include #include using namespace std;
typedef __int64 lld;
const int N=500005;
int n,m,low,high;
int a[N];
int lg[N];
int zz[19][N];
lld ST[19][N];

int Get(int l,int r){
int k=lg[r-l+1];
if (ST[k][l] else return zz[k][r-(1<}

struct Heap_t{
struct Node{int l,r,i;lld key;}Q[N+N];
int tot;

void up(int k){
while (k>1 && Q[k>>1].key swap(Q[k>>1],Q[k]);
k>>=1;
}
}

void down(int k){
int p;
while (k<<1<=tot){
p=k<<1;
if (p if (Q[p].key>Q[k].key){
swap(Q[p],Q[k]);
k=p;
}
else break;
}
}

void Insert(int l,int r,int i){
if (l>r) return;
tot++;
Q[tot].l=l; Q[tot].r=r; Q[tot].i=i; Q[tot].key=ST[0][i]-ST[0][Get(l,r)];
up(tot);
}

void Del(){
Node tmp=Q[1];
Q[1]=Q[tot–];
down(1);
int pos=Get(tmp.l,tmp.r);
Insert(tmp.l,pos-1,tmp.i);
Insert(pos+1,tmp.r,tmp.i);
}

void init(){
int i;
for (tot=0,i=1;i<=n;i++)
Insert(max(0,i-high),i-low,i);
}

void solve(){
lld ans=0;
while (m){
ans+=Q[1].key;
Del();
m–;
}
printf("%I64dn",ans);
}
}Heap;

void init(){
scanf("%d%d%d%d",&n,&m,&low,&high);
int k,s,i;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) {ST[0][i]=ST[0][i-1]+a[i]; zz[0][i]=i;}
for (k=1;1< s=1< for (i=0;i+s+s-1<=n;i++)
if (ST[k-1][i] ST[k][i]=ST[k-1][i];
zz[k][i]=zz[k-1][i];
}
else{
ST[k][i]=ST[k-1][i+s];
zz[k][i]=zz[k-1][i+s];
}
}
for (i=1,k=0;i<=n;i++)
lg[i]=k+=(i==(1<}

int main(){
init();
Heap.init();
Heap.solve();
}