【BZOJ2006】超级钢琴（RMQ，priority_queue）

题意：

思路：

用三元组(i, l, r)表示右端点为i，左端点在[l, r]之间和最大的区间（[l, r]保证是对于i可行右端点区间的一个子区间），我们用堆维护一些这样的三元组。

堆中初始的元素为每个i，并且[l, r]为这个i可行左端点的区间。

假如某次最大值为(i, l, r)，并且j为那个和最大区间的左端点，那么需要往堆中加入两个三元组(i, l, j-1)和(i, j+1, r)。

对于一个三元组，计算对应最大和的问题实际就是一个RMQ问题，可以通过Sparse Table在O(NlogN) – O(1)的时间内解决。

实际上固定左端点的方法也类似，程序中使用这种方法

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 #include<iostream>

 #include<algorithm>

 #include<set>

 #include<map>

 #define mp(a,b,c,d) (data){a,b,c,d}

 #define inf 1000000000

 #define ll long long

 #define MAXN 510000

 using namespace std;

 struct data{int i,l,r,t;};

 int f[MAXN][];

 int a[MAXN];

 int query(int x,int y)

 {

     if(x>y) return ;

     int len=y-x+; int l=log(len)/log();

     int s1=f[x][l];

     int s2=f[y-(<<l)+][l];

     if(a[s1]>a[s2]) return s1;

      else return s2;

 }

 bool operator<(data x,data y)

 {

     return a[x.t]-a[x.i-]<a[y.t]-a[y.i-];

 }

 int main()

 {

     freopen("bzoj2006.in","r",stdin);

     freopen("bzoj2006.out","w",stdout);

     priority_queue<data,vector<data> >q;

     int n,K,L,R;

     scanf("%d%d%d%d",&n,&K,&L,&R);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

         a[i]+=a[i-];

         f[i][]=i;

     }

     int l=log(n)/log();

     for(int i=;i<=l;i++)

      for(int j=;j+(<<i)-<=n;j++)

      {

          int x=f[j][i-]; int y=f[j+(<<(i-))][i-];

          if(a[x]>a[y]) f[j][i]=x;

           else f[j][i]=y;

      }

     for(int i=;i<=n;i++)

      if(i+L-<=n)

      {

          int t=min(n,i+R-);

          q.push(mp(i,i+L-,t,query(i+L-,t)));

      }

     ll ans=;

     for(int i=;i<=K;i++)

     {

         data t=q.top();q.pop();

         ans+=a[t.t]-a[t.i-];

         //printf("%lld\n",ans);

         if(t.t->=t.l) q.push(mp(t.i,t.l,t.t-,query(t.l,t.t-)));

         if(t.t+<=t.r) q.push(mp(t.i,t.t+,t.r,query(t.t+,t.r)));

     }

     printf("%lld\n",ans);

     return ;

 }