题目:
Description
Input
Output
Sample Input
Sample Output
HINT
题解:
首先我们发现,如果相同的字符的贡献可以重复计算的话,那就是超级钢琴了.
可以直接应用堆来求解
但是这道题中相同字符的贡献只统计一次,就需要我们瞎搞一下了。
对于这道题,我们可以通过可持久化线段树来处理去重的问题
怎么处理呢...
我们可以对每个点维护以这个点为右端点的所有子段和
这样我们考虑如何从i-1拓展到i
实际上我们拓展的时候只需要考虑第i位上的数字对前面做出的贡献
我们发现其实这个字符只对一部分左端点连续的字段做出贡献
具体一点,i位置上的数字只对左端点在\([last[a[i]]+1 ~ i]\)位置上的子段做出贡献
所以我们可以在可持久化线段树中通过区间修改实现\(nlogn\)处理出所有的子段
然后就是超级钢琴啦....
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const ll maxn = 210010;
struct Node{
Node *ch[2];
ll mx,id,lazy;
void update(){
mx = max(ch[0]->mx,ch[1]->mx);
if(mx == ch[0]->mx) id = ch[0]->id;
if(mx == ch[1]->mx) id = ch[1]->id;
mx += lazy;
}
}*null,*root[maxn],*it,mem[maxn*50];
inline void init(){
it = mem;null = it++;
null->ch[0] = null->ch[1] = null;
null->mx = null->id = 0;
root[0] = null;
}
Node* insert(Node *rt,ll l,ll r,ll L,ll R,ll val){
Node *p = it++;*p = *rt;
if(L == R && l == r){
p->id = l;
}
if(L <= l && r <= R){
p->lazy += val;
p->mx += val;
return p;
}
ll mid = l+r >> 1;
if(L <= mid) p->ch[0] = insert(p->ch[0],l,mid,L,R,val);
if(R > mid) p->ch[1] = insert(p->ch[1],mid+1,r,L,R,val);
p->update();return p;
}
typedef pair<ll,ll> pa;
inline pa query(Node *p,ll l,ll r,ll L,ll R){
if(L <= l && r <= R){
return make_pair(p->mx,p->id);
}
ll mid = l+r >> 1;pa x,y;
if(R <= mid){
x = query(p->ch[0],l,mid,L,R);
x.first += p->lazy;
return x;
}
if(L > mid){
y = query(p->ch[1],mid+1,r,L,R);
y.first += p->lazy;
return y;
}
x = query(p->ch[0],l,mid,L,R);
y = query(p->ch[1],mid+1,r,L,R);
x.first += p->lazy;y.first+=p->lazy;
if(x.first > y.first) return x;
else return y;
}
ll a[maxn],last[maxn],b[maxn],c[maxn];
struct num{
ll l,r;
ll val,le,ri;
bool friend operator < (const num &a,const num &b){
return a.val < b.val;
}
num(){}
num(const ll &a,const ll &b,const ll &c,const ll &d,const ll &e){
l = a;r = b;val = c;le = d;ri = e;
}
};
priority_queue<num>q;
int main(){
init();
ll n,k;read(n);read(k);
for(ll i=1;i<=n;++i){
read(a[i]);
b[i] = a[i];
}
sort(b+1,b+n+1);
for(ll i=1;i<=n;++i){
c[i] = lower_bound(b+1,b+n+1,a[i]) - b;
}
memset(last,-1,sizeof last);
for(ll i=1;i<=n;++i){
b[i] = last[c[i]];
last[c[i]] = i;
}
for(ll i=1;i<=n;++i){
root[i] = insert(root[i-1],1,n,i,i,a[i]);
if(b[i] != -1){
ll l = b[i] + 1,r = i-1;
if(l <= r){
root[i] = insert(root[i],1,n,l,r,a[i]);
}
}else{
ll l = 1,r = i-1;
if(l <= r) root[i] = insert(root[i],1,n,l,r,a[i]);
}
pa x = query(root[i],1,n,1,i);
q.push(num(x.second,i,x.first,1,i));
}
while(--k){
num x = q.top();q.pop();
ll l = x.l + 1,r = x.ri;
if(l <= r){
pa tmp = query(root[x.r],1,n,l,r);
q.push(num(tmp.second,x.r,tmp.first,l,r));
}
l = x.le;r = x.l - 1;
if(l <= r){
pa tmp = query(root[x.r],1,n,l,r);
q.push(num(tmp.second,x.r,tmp.first,l,r));
}
}
num ans = q.top();
printf("%lld\n",ans.val);
getchar();getchar();
return 0;
}
如果你不会超级钢琴...
这道题要求k大值,实际上我们可以考虑依次求出第一大、第二大、第三大、 ... 、第k大
那么问题就在于如何求解这个东西。
我们可以采用如下的策略: