bzoj : 4504: K个串区间修改主席树

4504: K个串

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 268 Solved: 110
[Submit][Status][Discuss]

Description

兔子们在玩k个串的游戏。首先，它们拿出了一个长度为n的数字序列，选出其中的一

个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。

兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第

k大的和是多少。

Input

第一行，两个整数n和k，分别表示长度为n的数字序列和想要统计的第k大的和

接下里一行n个数a_i，表示这个数字序列

Output

一行一个整数，表示第k大的和

Sample Input

7 5
3 -2 1 2 2 1 3 -2

Sample Output

HINT

1 <= n <= 100000, 1 <= k <= 200000, 0 <= |a_i| <= 10^9数据保证存在第 k 大的和

看到这道题感觉一脸不可做，直到有人告我主席树是可以区间修改的，靠我以前一直以为不行的。。。

思路还是很简单的，和超级钢琴一样，用堆存一个五元组，表示一个右端点往左某个区间的局部最大值，每次分裂成两个，暴力找出前k大的就好了。

所以要用主席树维护一个区间min和支持区间打标记，这道题的标记可以永久化。

据yousiki说也可以支持push_down，只是查询的时候需要新建节点。

因为第一次写所以出现了很多神奇的错误。

最开始修改我是这么写的：

if(ll<=l&&rr>=r)

{

	a[x].id=a[y].id;

	a[x].lazy=a[y].lazy+z;

	a[x].mn=a[x].lazy;

	return ;

}

果断过不了样例，查着查着意识到好像区间修改和单点修改不太一样，x应该有左右儿子的！于是:

if(ll<=l&&rr>=r)

{

　　a[x].id=a[y].id;

　　a[x].lazy=a[y].lazy+z;

　　a[x].mn=a[x].lazy;

　　a[x].l=a[y].l;

　　a[x].r=a[y].r;

　　return ;

}

过样例后交上去wa，拍拍拍，拍出来后发现不对，x又不是叶子，它的min和lazy怎么可能相等！！！

if(lll<=l&&rr>=r)

{

	a[x].id=a[y].id;

	a[x].lazy=a[y].lazy+z;

	a[x].mn=a[x].lazy+a[y].mn;

	a[x].l=a[y].l;

	a[x].r=a[y].r

	return ;

}

小数据都拍过了，很高兴试了组大数据，不给面子的wa了，直觉告诉我还是这错了，我靠我在写什么，这顺序不对啊，我给x的mn加了两倍的y.lazy.

if(lll<=l&&rr>=r)

{

	a[x].id=a[y].id;

	a[x].lazy=a[y].lazy+z;

	a[x].mn=z+a[y].mn;

	a[x].l=a[y].l;

	a[x].r=a[y].r

	return ;

}

普天同庆，终于对了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#define N 100005

#define ll long long

#define inf 1LL<<61

using namespace std;

int n,k;

struct node

{

    int l,r,pos,rr;

    ll zhi;

    node(){;}

    node(int _l,int _r,int _pos,int _rr,ll _zhi)

    {

        l=_l;r=_r;pos=_pos;rr=_rr;zhi=_zhi;

    }

    friend bool operator < (const node &aa,const node &bb)

    {

        return aa.zhi<bb.zhi;

    }

};

priority_queue<node>q;

struct tree

{

    int l,r,id;

    ll lazy,mn;

    tree()

    {

        lazy=mn=0;

    }

}a[N*30]; int cnt;

int root[N];

int b[N];

vector<int>v[N];

void push_up(int x)

{

    if(a[a[x].l].mn<a[a[x].r].mn)

    {

        a[x].mn=a[a[x].l].mn;

        a[x].id=a[a[x].l].id;

    }

    else

    {

        a[x].mn=a[a[x].r].mn;

        a[x].id=a[a[x].r].id;

    }

    a[x].mn+=a[x].lazy;

}

void build(int x,int l,int r)

{

    a[x].id=l;

    if(l==r)return ;

    int mid=(l+r)>>1;

    a[x].l=++cnt;a[x].r=++cnt;

    build(a[x].l,l,mid);build(a[x].r,mid+1,r);

}

void insert(int x,int y,int l,int r,int lll,int rr,int z)

{

    if(lll<=l&&rr>=r)

    {

        a[x].id=a[y].id;

        a[x].lazy=a[y].lazy+z;

        a[x].mn=z+a[y].mn;

        a[x].l=a[y].l;

        a[x].r=a[y].r;

        return ;

    }

    a[x].lazy=a[y].lazy;

    int mid=(l+r)>>1;

    if(lll<=mid)

    {

        a[x].l=++cnt;

        insert(a[x].l,a[y].l,l,mid,lll,rr,z);

    }

    else a[x].l=a[y].l;

    if(rr>mid)

    {

        a[x].r=++cnt;

        insert(a[x].r,a[y].r,mid+1,r,lll,rr,z);

    }

    else a[x].r=a[y].r;

    push_up(x);

    return ;

}

int ans1;ll ans2;

void qur(int x,int l,int r,int lll,int rr,ll now)

{

    if(lll<=l&&rr>=r)

    {

        ll tmp=now+a[x].mn;

        if(tmp<ans2)

        {

            ans1=a[x].id;ans2=tmp;

        }

        return ;

    }

    int mid=(l+r)>>1;

    if(lll<=mid)qur(a[x].l,l,mid,lll,rr,now+a[x].lazy);

    if(rr>mid)qur(a[x].r,mid+1,r,lll,rr,now+a[x].lazy);

    return ;

}

ll sum[N];

int li[N],ct,nxt[N],now[N];

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)scanf("%d",&b[i]),li[++ct]=b[i];

    sort(li+1,li+ct+1);

    ct=unique(li+1,li+ct+1)-li-1;

    for(int i=1;i<=n;i++)b[i]=lower_bound(li+1,li+ct+1,b[i])-li;

    for(int i=1;i<=ct;i++)now[i]=n+1;

    for(int i=n;i>=1;i--)

    {

        nxt[i]=now[b[i]];

        v[nxt[i]].push_back(i);

        now[b[i]]=i;

    }

    memset(now,0,sizeof(now));

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

    {

        sum[i]=sum[i-1];

        if(!now[b[i]])

        {

            now[b[i]]=1;

            sum[i]+=li[b[i]];

        }

    }

    cnt=0;

    root[n+2]=++cnt;

    build(1,0,n-1);

    for(int i=n+1;i>=1;i--)

    {

        root[i]=root[i+1];

        for(int j=0;j<v[i].size();j++)

        {

            if(v[i][j]==n)continue;

            int tmp=root[i];root[i]=++cnt;

            insert(root[i],tmp,0,n-1,v[i][j],n-1,li[b[v[i][j]]]);

        }

    }

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

    {

        ans2=inf;qur(root[i+1],0,n-1,0,i-1,0);

        q.push(node(0,i-1,ans1,i,sum[i]-ans2));

    }

    for(int i=1;i<=k;i++)

    {

        node tmp=q.top();q.pop();

        if(tmp.l!=tmp.pos)

        {

            ans2=inf;qur(root[tmp.rr+1],0,n-1,tmp.l,tmp.pos-1,0);

            q.push(node(tmp.l,tmp.pos-1,ans1,tmp.rr,sum[tmp.rr]-ans2));

        }

        if(tmp.r!=tmp.pos)

        {

            ans2=inf;qur(root[tmp.rr+1],0,n-1,tmp.pos+1,tmp.r,0);

            q.push(node(tmp.pos+1,tmp.r,ans1,tmp.rr,sum[tmp.rr]-ans2));

        }

        if(i==k)

        {

            printf("%lld\n",tmp.zhi);

        }

    }

    return 0;

}

巴特西

bzoj : 4504: K个串区间修改主席树

4504: K个串

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

bzoj : 4504: K个串 区间修改主席树

4504: K个串

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

bzoj : 4504: K个串区间修改主席树