首页 > 其他分享 >2023NOIP A层联测9 风信子+P2048 【NOI2010】 超级钢琴 2023

2023NOIP A层联测9 风信子+P2048 【NOI2010】 超级钢琴 2023

时间：2024-01-22 11:14:36浏览次数：34  
标签：val int tree 三元组 风信子 NOI2010 联测 区间 now

P2048 【NOI2010】 超级钢琴

2023NOIP A层联测9 风信子

一年 OI 一场空，一道原题见祖宗……

Ps：超级钢琴是风信子的前置题。

超级钢琴

题意

在一段序列上，选择长度为 \(x\) 的区间且 \(x\in [L,R]\)，求选择 \(k\) 个区间求和的最大值。

思路

来自洛谷第一篇 Nekroz 的题解。

将区间和变为前缀和，考虑将所有的合法方案的和拉出来排序，时间复杂度不现实，考虑贪心的解决这个问题。

设 \(S(o,l,r)=max(sum[t]-sum[o-1])|l\leq t \leq r\)，即以 \(o\) 为左端点，以 \(t\) 为右端点的区间的和。\(sum\) 是前缀和，\(l,r\) 使得 \(t\) 满足题目限制。

维护 \(sum[t]\) 可以使用 \(ST\) 表 \(O(1)\) 维护。

然后考虑贪心。

我们将每次可以选择最优的 \(S(o,l,r)\)，选择 \(k\) 次就是我们的结果。

初始时，是 \(n\) 个 \(i\ (i\in [1,n])\) 为起点，终点范围最大的区间，这里可以用优先队列维护（用结构体存 \(S(o,l,r)\)，写构造函数比较大小）。

三元组 \(S(o,l,r)\) 选择后，会增加 \(S(o,l,t-1)\) 和 \(S(o,t+1,r)\) 两个答案区间，同时 \(S(o,l,r)\) 这个区间不能再被选中，先弹出不能选的区间，再把这两个玩意丢进堆里。对于 \(l=t\) 或 \(r=t\) 的情况需要特判。

那么这个分裂的正确性在哪里呢？

约定：下文称 \(S(o,l,r)\) 选中后分裂出的三元组为子三元组，\(S(o,l,r)\) 为父三元组。

Q：子三元组有没有可能大于父三元组，导致答案变劣。

A：不难发现，我们分裂出这个三元组的父三元组肯定大于这个三元组（因为起点相同，结束端点父三元组肯定选最大的）。所以只有父三元组被选，子三元组才会被选。

Q：父三元组选择的结束端点影响子三元组的取值，是否存在结束端点使父三元组变略，而使子三元组和父三元组共同的贡献更优。

A：每次三元组本质是一段区间，如果父三元组不选择最大段区间，肯定存在子三元组会选择最大区间，其实分到最后，每一个区间都会出现一次。其实上文的父子三元组单调性也证明了不会出现这种情况。

CODE

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=5e5+5;


int n,k,l,r;
int sum[maxn];

struct Tree
{
    int l,r;
    pair<int,int>mx={-1e9,-1e9};
}tree[maxn*10];

void build(int p,int l,int r)
{
    tree[p].l=l;
    tree[p].r=r;
    if(l==r)
    {
        tree[p].mx=make_pair(sum[l],l);
        return ;
    }
    build(p*2,l,(l+r)>>1);
    build(p*2+1,((l+r)>>1)+1,r);
    tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);
}
pair<int,int> query(int p,int l,int r)
{
    if(tree[p].l>r||tree[p].r<l) return make_pair(-1e9,-1e9);
    if(l<=tree[p].l&&tree[p].r<=r) return tree[p].mx;
    return max(query(p*2,l,r),query(p*2+1,l,r));
}

struct element
{
    int o,l,r,t;
    friend bool operator<(element a,element b){return (sum[a.t]-sum[a.o-1])<(sum[b.t]-sum[b.o-1]);}
};
element gt(int o,int l,int r)
{
    return {o,l,r,query(1,l,r).second};
}

priority_queue<element>que;

signed main()
{
    scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%lld",&x);
        sum[i]=sum[i-1]+x;
    }

    build(1,1,n);
    for(int i=1;i+l-1<=n;i++) que.push(gt(i,i+l-1,min(i+r-1,n)));

    int ans=0;
    while(k--)
    {
        int o=que.top().o,l=que.top().l,r=que.top().r,t=que.top().t;
        que.pop();
        ans+=sum[t]-sum[o-1];
        if(t!=l) que.push(gt(o,l,t-1));
        if(t!=r) que.push(gt(o,t+1,r));
    }

    printf("%lld",ans);
}

风信子

题面

有两种操作

1.选择区间 \([l,r]\) 使 \(i\in [l,r]\) 中的 \(a_i\) 都加上 \(x\)。

2.在区间 \([l,r]\) 选择 \(k\) 个数对 \((i,j)\ (i<j)\)，求 \(a_i-a_j\) 的和的最大值。

思路

\(50pts\)：查询询问做一次超级钢琴，线段树区间加。

\(15pts(k=1)\)：线段树维护区间答案，对于一个节点，答案可以是左右儿子的答案，也可以是左边最大-右边最小。

\(100pts\)：

超级钢琴中，我们的”候补答案集合“思想是以每个点为起点做一次做三元组。

这显然不够带劲，在这里我们把起点也设成区间，那么也就是：\(S(l,r,l',r')\)，其中 \([l,r]\) 是起点，\([l',r']\) 是终点。

但这样子选择区间后不方便分裂，那么我们考虑，什么样的区间分裂比较方便？

1.起点终点区间没有交集。（起点取区间最大，终点去区间最小）

2.起点终点区间完全重合。（\(k=1\) 的做法）

利用超级钢琴的思想维护优先队列即可。

分裂后的区间情况：

维护很麻烦，但思路简单。

CODE

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ls(i) i*2
#define rs(i) i*2+1

const int maxn=1e5+5;
const int inf=1e9;

int n,m;
int a[maxn];

struct Ans
{
    int val,x,y;
    friend bool operator<(Ans a,Ans b){return a.val<b.val;}
    friend bool operator>(Ans a,Ans b){return a.val>b.val;}
};
struct Grid
{
    int val,id;
    friend bool operator<(Grid a,Grid b){return a.val<b.val;}
    friend bool operator>(Grid a,Grid b){return a.val>b.val;}
};
struct node1
{
    int l,r,mx=-inf,mi=inf,mxid,miid,lazy;
    Ans val;
}tree[maxn*10];

inline void updata(int p)
{
    tree[p].val=max(tree[ls(p)].val,tree[rs(p)].val);
    Ans tmp;
    tmp.val=tree[ls(p)].mx-tree[rs(p)].mi;
    tmp.x=tree[ls(p)].mxid,tmp.y=tree[rs(p)].miid;
    tree[p].val=max(tree[p].val,tmp);

    if(tree[ls(p)].mi>tree[rs(p)].mi) tree[p].mi=tree[rs(p)].mi,tree[p].miid=tree[rs(p)].miid;
    else tree[p].mi=tree[ls(p)].mi,tree[p].miid=tree[ls(p)].miid;
    if(tree[ls(p)].mx<tree[rs(p)].mx) tree[p].mx=tree[rs(p)].mx,tree[p].mxid=tree[rs(p)].mxid;
    else tree[p].mx=tree[ls(p)].mx,tree[p].mxid=tree[ls(p)].mxid;
}
inline void push_down(int p)
{
    if(tree[p].l==tree[p].r)
    {
        tree[p].lazy=0;
        return ;
    }
    tree[ls(p)].lazy+=tree[p].lazy;
    tree[ls(p)].mx+=tree[p].lazy;
    tree[ls(p)].mi+=tree[p].lazy;

    tree[rs(p)].lazy+=tree[p].lazy;
    tree[rs(p)].mx+=tree[p].lazy;
    tree[rs(p)].mi+=tree[p].lazy;
    tree[p].lazy=0;
}
inline void build(int p,int l,int r)
{
    tree[p].l=l;
    tree[p].r=r;
    if(l==r)
    {
        tree[p].mx=tree[p].mi=a[l];
        tree[p].mxid=tree[p].miid=l;
        tree[p].val.x=tree[p].val.y=l;
        return ;
    }
    build(ls(p),l,l+r>>1);
    build(rs(p),(l+r>>1)+1,r);
    updata(p);
}
inline Grid gtmi(int p,int l,int r)
{
    push_down(p);
    if(tree[p].l>r||tree[p].r<l) return {inf,inf};
    if(l<=tree[p].l&&tree[p].r<=r) return {tree[p].mi,tree[p].miid};
    return min(gtmi(ls(p),l,r),gtmi(rs(p),l,r));
}
inline Grid gtmx(int p,int l,int r)
{
    push_down(p);
    if(tree[p].l>r||tree[p].r<l) return {-inf,0};
    if(l<=tree[p].l&&tree[p].r<=r) return {tree[p].mx,tree[p].mxid};
    return max(gtmx(ls(p),l,r),gtmx(rs(p),l,r));
}
inline Ans gtans(int p,int l,int r)
{
    push_down(p);
    if(tree[p].l>r||tree[p].r<l) return {-inf,0,0};
    if(l<=tree[p].l&&tree[p].r<=r) return tree[p].val;

    int mid=l+r>>1;
    Ans t=max(gtans(ls(p),l,r),gtans(rs(p),l,r));
    Grid a=gtmx(ls(p),l,r),b=gtmi(rs(p),l,r);
    return max(t,(Ans){a.val-b.val,a.id,b.id});
}
inline void insert(int p,int l,int r,int val)
{
    push_down(p);
    if(tree[p].r<l||tree[p].l>r) return ;
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        tree[p].lazy+=val;
        tree[p].mx+=val;
        tree[p].mi+=val;
        return ;
    }
    insert(ls(p),l,r,val);
    insert(rs(p),l,r,val);
    updata(p);
}

struct preAns
{
    int al,ar,bl,br,val;
    Ans Val()
    {
        if(ar<bl)
        {
            Grid a=gtmx(1,al,ar),b=gtmi(1,bl,br);
            return {a.val-b.val,a.id,b.id};
        }
        else return gtans(1,al,ar);
    }
    friend bool operator<(preAns a,preAns b){return a.val<b.val;}
    friend bool operator>(preAns a,preAns b){return a.val>b.val;}
};

priority_queue<preAns>que;

signed main()
{
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

    build(1,1,n);

    while(m--)
    {
        int op,l,r,k;
        scanf("%lld%lld%lld%lld",&op,&l,&r,&k);
        if(op==1) insert(1,l,r,k);
        else
        {
            preAns t;
            t.al=t.bl=l,t.ar=t.br=r;
            t.val=t.Val().val;
            que.push(t);
            int sum=0;
            while(k--)
            {
                preAns now=que.top();
                que.pop();
                Ans val=now.Val();
                int x=val.x,y=val.y;
                sum+=now.val;
                if(now.ar<now.bl)
                {
                    if (x > now.al)
                    {
                        t=now;
                        t.ar=x-1;
                        t.val = t.Val().val;
                        que.push(t);
                    }
                    if (now.bl < y)
                    {
                        t=now;
                        t.ar=t.al=x;
                        t.br=y-1;
                        t.val = t.Val().val;
                        que.push(t);
                    }
                    if (y < now.br)
                    {
                        t=now;
                        t.ar=t.al=x;
                        t.bl=y+1;
                        t.val = t.Val().val;
                        que.push(t);
                    }
                    if (x < now.ar)
                    {
                        t=now;
                        t.al=x+1;
                        t.val = t.Val().val;
                        que.push(t);
                    }
                }
                else
                {
                    if(x>now.al)
                    {
                        t=now;
                        t.ar=t.br=x-1;
                        t.val=t.Val().val;
                        que.push(t);

                        t=now;
                        t.ar=x-1,t.bl=x;
                        t.val=t.Val().val;
                        que.push(t);
                    }
                    if(x!=y)
                    {
                        t.al=t.ar=t.bl=t.br=x;
                        t.val=t.Val().val;
                        que.push(t);
                    }
                    if(x<y-1)
                    {
                        t.al=t.ar=x;
                        t.bl=x+1;
                        t.br=y-1;
                        t.val=t.Val().val;
                        que.push(t);
                    }
                    if(y<now.br)
                    {
                        t.al=t.ar=x;
                        t.br=now.br;
                        t.bl=y+1;
                        t.val=t.Val().val;
                        que.push(t);
                    }
                    if(x<now.ar)
                    {
                        t=now;
                        t.al=t.bl=x+1;
                        t.val=t.Val().val;
                        que.push(t);
                    }
                }
            }
            printf("%lld\n",sum);
            while(!que.empty()) que.pop();
        }
    }
}

标签：val,int,tree,三元组,风信子,NOI2010,联测,区间,now
From： https://www.cnblogs.com/binbinbjl/p/17979601

相关文章

  • P6105 [Ynoi2010] y-fast trie
    更好的阅读体验P6105[Ynoi2010]y-fasttrie首先把所有数对\(C\)取模，分类讨论：\(x+y\geqC\)因为只会取模一次，这时显然取最大值和次大值。\(x+y<C\)一开始的想法是对于每一个数\(a\)找到另一个数满足\(a+b<C\)的最大的\(b\)，这样是一棵外向树（环长一定\(=2\)），修改......
  • 2024省选联测12
    A.硬币给定\(n\)，在满足\(x\timesy=n^2+1\)且\(x,y\ge2\)的前提下，最大化\(x+y\)。从后向前扫描序列，第\(i\)个数被扫到时为\(p\)，\(p\)为质数或者为\(1\)。第\(i+kp,k\in\mathbb{Z}\)个数仍然是\(p\)的倍数。因为\[i^2+1\equiv0\modp\]所以\[(i+kp)^2+......
  • 2024省选联测11
    A.Giao徽的烤鸭给定一棵树，边权为\(1\)。在第\(i\)家店办卡花费\(w_i\)元。对于任意一家店，如果Giao徽在到\(i\)的距离小于等于\(p\)的所有店办了卡，可得到\(v_p\)元的代金券。求最大利润。\(f_{u,i}\)表示在以\(u\)为根的子树中，到\(u\)距离小于等于\(i\)......
  • 2024省选联测10
    A.小幸运题目描述给出平面上\(n\)个点的坐标，以及整数\(W，H\)。以每个点为底边中点构造底边长度相等且底边与一坐标轴平行的等腰直角三角形，满足三角形在\((0,0),(W,0),(W,H),(0,H)\)四点构成的矩形内部且三角形内部区域互不重叠。求每个三角形底边长度的最大值。把所有坐......
  • P3205 [HNOI2010] 合唱队
    原题链接导入1.对于一个给定的序列，最后一个加进来的元素不是最左端就是最右端，如果是最左端，那么代表去掉最左端的序列中最后一个加进来的元素比最左端小，最右端同理。2.对于一个给定的序列，可能的排序结果无非两类，一类是以最左端的元素结尾的，一类是以最右端的元素结尾的。因此设\(......
  • 2023NOIP A层联测32 T4 红楼 ~ Eastern Dream
    2023NOIPA层联测32T4红楼~EasternDream根号分治加分块。Ps：分块后面真的用的多。思路考虑根号分治，将\(x\)分为\(x\leq\sqrtn\)的情况和\(x>\sqrtn\)的情况。\(x\leq\sqrtn\)由于这一部分较小，如果在线段上暴力添加肯定会超时。先设\(f_{x,i}\)表示模\(......
  • 2023NOIP A层联测32
    2023NOIPA层联测32目录2023NOIPA层联测32AflandreB.meirinC.sakuyaD.红楼~EasternDream总结Aflandre有\(n\)种烟花，每种烟花有两个参数\(a，b\)，你要构造一种燃放顺序，使得\(b\)的和最大，\(b\)会改变，具体来说：设\(i\)在\(j\)前燃放，那么。\(a_i<a_j\)，则\(b_......
  • 2023NOIP A层联测31 T4 民主投票
    2023NOIPA层联测31T4民主投票思维好题。思路首先可以设\(s\)每个人最多获得的票数，一开始所有点都把自己的票投给自己父亲。如果一个点的票数超过\(s\)了，那么这个点肯定要把票分给他的父亲。设\(f_{u,s}\)为\(u\)点在最多获得\(s\)票的情况下要向父亲分的票数（不......
  • 2023NOIP A层联测30 总结
    2023NOIPA层联测30总结题目T1草莓列车\(n\leq10^5,m\leq10^7\)赛时思路一开始看错\(m\)数据范围，以为\(O(m\logm)\)可以过，后来发现问题以后，集中在考虑线段树之类的\(\log\)级别的算法维护序列，或者线段区间，一直没有想过ST表相关数据结构，于是最后只有60。赛后......
  • 2023NOIP A层联测31总结
    2023NOIPA层联测31总结\(T1\)暴力操作：给你一个长度为\(n\)的序列\(a\)，你可以花费\(c_x\)使得\(a_i\)变为\([a_i/x]\)，你总共有\(k\)元。为最终序列的中位数最小是多少。保证\(n\)为奇数。\(n,m\le5*10^5\)首先想到了二分一个答案，因为只要使得前\((n+1......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99