花了一個星期，總算把這一道該死的毒瘤題做完了。 這道題有很多種解法，我是用優先隊列+主席樹。 首先每一個區間的和，可以表示為兩個首碼和之差。 我們顯然可以知道，每一次找到的那個最大值必然在以一個點為最後一個點的區間之內。 所以我們可以把每一個點為最後一個點的最大值的區間求出來，先打入隊列。 然後每一 ...
花了一個星期，總算把這一道該死的毒瘤題做完了。
這道題有很多種解法，我是用優先隊列+主席樹。
首先每一個區間的和，可以表示為兩個首碼和之差。
我們顯然可以知道，每一次找到的那個最大值必然在以一個點為最後一個點的區間之內。
所以我們可以把每一個點為最後一個點的最大值的區間求出來，先打入隊列。
然後每一次打出來一個值，我們就把這個區間的最後一個值的位置的排名前一名的那一個區間打入隊列。
這樣重覆計算即可。
至於實現，我們可以將每一個首碼和建一個主席樹，然後我們維護一個三元組(add,cnt,end)
add維護區間和。
cnt維護當前在以這個最後一個位置最後的區間的排名。
end維護結尾的點。
具體實現有點迷，註意在建主席樹的時候記得把0給建進去，會少不少麻煩。
剩下的就是主席樹區間第k大了。
貼上代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#define maxn 500100
using namespace std;
typedef long long ll;
ll a[maxn];
ll b[maxn];
int lx,rx,n,k;
int root[maxn];
int tot;
struct P{
int l,r,sum;
}tree[maxn*20];
struct X{
ll add;
int cnt,end;
};
map<ll,int>ma;
struct cmp{
bool operator () (const X a,const X b) const
{
return a.add<b.add;
}
};
priority_queue<X,vector<X>,cmp > q;
void update(int k1,int k2,int l,int r,int x)//k1-build,k2-find
{
if(l==r)
{
tree[k1].sum=tree[k2].sum+1;
return;
}
else
{
int mid=(l+r)/2;
if(x>=l&&x<=mid)
{
tot++;
tree[k1].l=tot;
tree[k1].r=tree[k2].r;
update(tree[k1].l,tree[k2].l,l,mid,x);
}
else
{
tot++;
tree[k1].r=tot;
tree[k1].l=tree[k2].l;
update(tree[k1].r,tree[k2].r,mid+1,r,x);
}
}
tree[k1].sum=tree[tree[k1].l].sum+tree[tree[k1].r].sum;
}
int query(int i,int j,int k,int l,int r)
{
if(l==r) return l;
int t=tree[tree[j].l].sum-tree[tree[i].l].sum;
int mid=(l+r)/2;
if(k<=t) return query(tree[i].l,tree[j].l,k,l,mid);
else return query(tree[i].r,tree[j].r,k-t,mid+1,r);
}
void work(int a,int b,int c)
{
X y;
y.add=a;
y.end=b;
y.cnt=c;
q.push(y);
}
ll ans;
int main()
{
scanf("%d%d%d%d",&n,&k,&lx,&rx);
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld",&x);
a[i+1]=a[i]+x;
}
for(int i=1;i<=n+1;i++) b[i]=a[i];
sort(b+1,b+n+2);
int o=unique(b+1,b+n+2)-b-1;
for(int i=1;i<=o;i++) ma[b[i]]=i;
for(int i=1;i<=n+1;i++) root[i]=i;
tot=n+1;
for(int i=1;i<=n+1;i++) update(root[i],root[i-1],1,o,ma[a[i]]);
for(int i=lx;i<=n;i++)
{
int p1=i-lx+1;
int p2=max(1,i-rx+1);
ll t=b[query(root[p2-1],root[p1],1,1,o)];
work(a[i+1]-t,i,1);
}
int sumx=0;
while(true)
{
X now=q.top();
q.pop();
ans+=now.add;
sumx++;
if(sumx==k) break;
int p1=now.end;
int p2=now.cnt;
int k1=p1-lx+1;
int k2=max(p1-rx+1,1);
if(p2==k1-k2+1) continue;
else{
ll u=b[query(root[k2-1],root[k1],p2+1,1,o)];
work(a[p1+1]-u,p1,p2+1);
}
}
cout<<ans<<endl;
return 0;
}
/*
4 3 2 3
3 2 -6 8
*/
有什麼寫的不好的地方大家儘管提出。
謝謝！！
