「LibreOJ β Round」ZQC 的手办

时间：2022-12-16 07:48:19

https://loj.ac/problem/504

一类套路题.

首先这个玩意可以两个logn树套树做。。。。

naive地，把区间内的所有数拿出来放进堆里。不断取出。

太多了。

所以开始只保留那初始logn区间最小值，弹出之后再找出左右区间下一个

线段树维护最小值和最小值位置。

和超级钢琴，异或粽子，K个串都一样。

或者说k短路。

只不过这个是线段树载体。

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

#define pb push_back

#define solid const auto &

#define enter cout<<endl

#define pii pair<int,int>

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);(fl==true)&&(x=-x);}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Modulo{

const int mod=;

il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}

il int sub(int x,int y){return ad(x,mod-y);}

il int mul(int x,int y){return (ll)x*y%mod;}

il void inc(int &x,int y){x=ad(x,y);}

il void inc2(int &x,int y){x=mul(x,y);}

il int qm(int x,int y=mod-){int ret=;while(y){if(y&) ret=mul(x,ret);x=mul(x,x);y>>=;}return ret;}

template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);}

template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);}

}

// using namespace Modulo;

namespace Miracle{

const int N=5e5+;

const int inf=0x3f3f3f3f;

int n,m;

struct tr{

    int mi,p;

    int tag;

}t[*N];

#define ls (x<<1)

#define rs (x<<1|1)

#define mid ((l+r)>>1)

void pushup(int x){

    t[x].mi=min(t[ls].mi,t[rs].mi);

    if(t[ls].mi==t[x].mi) t[x].p=t[ls].p;

    else t[x].p=t[rs].p;

}

void Max(int x,int c){

    t[x].mi=max(t[x].mi,c);

    t[x].tag=max(t[x].tag,c);

}

void pushdown(int x){

    if(t[x].tag){

        Max(ls,t[x].tag);

        Max(rs,t[x].tag);

        t[x].tag=;

    }

}

int a[N];

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

    if(l==r){

        t[x].mi=a[l];

        t[x].p=l;

        return;

    }

    build(ls,l,mid);

    build(rs,mid+,r);

    pushup(x);

}

void chan(int x,int l,int r,int L,int R,int c){

    if(L<=l&&r<=R){

        Max(x,c);

        return;

    }

    pushdown(x);

    if(L<=mid) chan(ls,l,mid,L,R,c);

    if(mid<R) chan(rs,mid+,r,L,R,c);

    pushup(x);

}

pii query(int x,int l,int r,int L,int R){

    if(L<=l&&r<=R){

        return mk(t[x].p,t[x].mi);

    }

    pushdown(x);

    if(L>mid) return query(rs,mid+,r,L,R);

    if(R<=mid) return query(ls,l,mid,L,R);

    pii le=query(ls,l,mid,L,R);

    pii ri=query(rs,mid+,r,L,R);

    le.se=min(le.se,ri.se);

    if(ri.se==le.se) le.fi=ri.fi;

    return le;

}

struct po{

    int v,p,l,r;

    po(){}

    po(int vv,int pp,int le,int ri){

        v=vv;p=pp;l=le;r=ri;

    }

    bool friend operator <(po a,po b){

        return a.v>b.v;

    }

    void op(){

        cout<<" po "<<v<<" "<<p<<" "<<l<<" "<<r<<endl;

    }

};

priority_queue<po>q;

void push(int x,int l,int r,int L,int R,int k){

    if(L<=l&&r<=R){

        if(t[x].mi<k) q.push(po(t[x].mi,t[x].p,l,r));

        return;

    }

    pushdown(x);

    if(L<=mid) push(ls,l,mid,L,R,k);

    if(mid<R) push(rs,mid+,r,L,R,k);

}

void clear(priority_queue<po>&q){

    priority_queue<po>tmp;

    q.swap(tmp);

}

int mem[+],num;

int main(){

    rd(n);

    for(reg i=;i<=n;++i){

        rd(a[i]);

    }

    build(,,n);

//    return 0;

    rd(m);

//    cout<<" 22223 "<<endl;

    int op,l,r,k,x;

    while(m--){

        rd(op);rd(l);rd(r);rd(k);

        if(op==){

//            continue;

//            cout<<" op==1 "<<endl;

            chan(,,n,l,r,k);

        }else{

//            cout<<" op==2 "<<endl;

            rd(x);

            clear(q);

            push(,,n,l,r,k);

//            cout<<" size "<<q.size()<<endl;

            num=;

            while(x&&!q.empty()){

                po now=q.top();q.pop();

//                now.op();

                if(now.v>=k) break;

                mem[++num]=now.v;

                if(now.l<=now.p-){

//                    cout<<" findl "<<endl;

                    pii lp=query(,,n,now.l,now.p-);

//                    cout<<" endq "<<endl;

                    q.push(po(lp.se,lp.fi,now.l,now.p-));

//                    cout<<" enl "<<endl;

                }

                if(now.p+<=now.r){

//                    cout<<" findr "<<endl;

                    pii lp=query(,,n,now.p+,now.r);

                    q.push(po(lp.se,lp.fi,now.p+,now.r));

//                    cout<<" enr "<<endl;

                }

                --x;

            }

            if(x){

                puts("-1");

            }else{

                prt(mem,,num);

            }

        }

    }

    return ;

}

}

signed main(){

//    freopen("data.in","r",stdin);

//    freopen("my.out","w",stdout);

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

*/
#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

#define pb push_back

#define solid const auto &

#define enter cout<<endl

#define pii pair<int,int>

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);(fl==true)&&(x=-x);}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Modulo{

const int mod=;

il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}

il int sub(int x,int y){return ad(x,mod-y);}

il int mul(int x,int y){return (ll)x*y%mod;}

il void inc(int &x,int y){x=ad(x,y);}

il void inc2(int &x,int y){x=mul(x,y);}

il int qm(int x,int y=mod-){int ret=;while(y){if(y&) ret=mul(x,ret);x=mul(x,x);y>>=;}return ret;}

template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);}

template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);}

}

// using namespace Modulo;

namespace Miracle{

const int N=5e5+;

const int inf=0x3f3f3f3f;

int n,m;

struct tr{

    int mi,p;

    int tag;

}t[*N];

#define ls (x<<1)

#define rs (x<<1|1)

#define mid ((l+r)>>1)

void pushup(int x){

    t[x].mi=min(t[ls].mi,t[rs].mi);

    if(t[ls].mi==t[x].mi) t[x].p=t[ls].p;

    else t[x].p=t[rs].p;

}

void Max(int x,int c){

    t[x].mi=max(t[x].mi,c);

    t[x].tag=max(t[x].tag,c);

}

void pushdown(int x){

    if(t[x].tag){

        Max(ls,t[x].tag);

        Max(rs,t[x].tag);

        t[x].tag=;

    }

}

int a[N];

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

    if(l==r){

        t[x].mi=a[l];

        t[x].p=l;

        return;

    }

    build(ls,l,mid);

    build(rs,mid+,r);

    pushup(x);

}

void chan(int x,int l,int r,int L,int R,int c){

    if(L<=l&&r<=R){

        Max(x,c);

        return;

    }

    pushdown(x);

    if(L<=mid) chan(ls,l,mid,L,R,c);

    if(mid<R) chan(rs,mid+,r,L,R,c);

    pushup(x);

}

pii query(int x,int l,int r,int L,int R){

    if(L<=l&&r<=R){

        return mk(t[x].p,t[x].mi);

    }

    pushdown(x);

    if(L>mid) return query(rs,mid+,r,L,R);

    if(R<=mid) return query(ls,l,mid,L,R);

    pii le=query(ls,l,mid,L,R);

    pii ri=query(rs,mid+,r,L,R);

    le.se=min(le.se,ri.se);

    if(ri.se==le.se) le.fi=ri.fi;

    return le;

}

struct po{

    int v,p,l,r;

    po(){}

    po(int vv,int pp,int le,int ri){

        v=vv;p=pp;l=le;r=ri;

    }

    bool friend operator <(po a,po b){

        return a.v>b.v;

    }

    void op(){

        cout<<" po "<<v<<" "<<p<<" "<<l<<" "<<r<<endl;

    }

};

priority_queue<po>q;

void push(int x,int l,int r,int L,int R,int k){

    if(L<=l&&r<=R){

        if(t[x].mi<k) q.push(po(t[x].mi,t[x].p,l,r));

        return;

    }

    pushdown(x);

    if(L<=mid) push(ls,l,mid,L,R,k);

    if(mid<R) push(rs,mid+,r,L,R,k);

}

void clear(priority_queue<po>&q){

    priority_queue<po>tmp;

    q.swap(tmp);

}

int mem[+],num;

int main(){

    rd(n);

    for(reg i=;i<=n;++i){

        rd(a[i]);

    }

    build(,,n);

//    return 0;

    rd(m);

//    cout<<" 22223 "<<endl;

    int op,l,r,k,x;

    while(m--){

        rd(op);rd(l);rd(r);rd(k);

        if(op==){

//            continue;

//            cout<<" op==1 "<<endl;

            chan(,,n,l,r,k);

        }else{

//            cout<<" op==2 "<<endl;

            rd(x);

            clear(q);

            push(,,n,l,r,k);

//            cout<<" size "<<q.size()<<endl;

            num=;

            while(x&&!q.empty()){

                po now=q.top();q.pop();

//                now.op();

                if(now.v>=k) break;

                mem[++num]=now.v;

                if(now.l<=now.p-){

//                    cout<<" findl "<<endl;

                    pii lp=query(,,n,now.l,now.p-);

//                    cout<<" endq "<<endl;

                    q.push(po(lp.se,lp.fi,now.l,now.p-));

//                    cout<<" enl "<<endl;

                }

                if(now.p+<=now.r){

//                    cout<<" findr "<<endl;

                    pii lp=query(,,n,now.p+,now.r);

                    q.push(po(lp.se,lp.fi,now.p+,now.r));

//                    cout<<" enr "<<endl;

                }

                --x;

            }

            if(x){

                puts("-1");

            }else{

                prt(mem,,num);

            }

        }

    }

    return ;

}

}

signed main(){

//    freopen("data.in","r",stdin);

//    freopen("my.out","w",stdout);

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

*/

「LibreOJ β Round」ZQC 的手办的更多相关文章

  1. LOJ504「LibreOJ β Round」ZQC 的手办

    https://loj.ac/problem/504 题解 对于区间取\(\max\),这个比较好办,直接在线段树上打标记就行了. 如果让我们弹出前\(n\)个数,我们可以用类似超级钢琴的思想,队列中 ...

  2. LOJ&num;505&period; 「LibreOJ β Round」ZQC 的游戏&lpar;最大流&rpar;

    题意 题目链接 Sol 首先把第一个人能吃掉的食物删掉 然后对每个人预处理出能吃到的食物,直接限流跑最大流就行了 判断一下最后的最大流是否等于重量和 注意一个非常恶心的地方是需要把除1外所有人都吃不到 ...

  3. &num;505&period; 「LibreOJ β Round」ZQC 的游戏

    题目描述 首先一定是让ZQC吃掉他能吃到的所有的球,这样才能尽可能的满足ZQC的质量是所有玩家中最大的. 在满足某一个玩家的质量不会超过ZQC的情况下,让这个玩家吃掉尽可能多的球,让其他玩家吃掉的尽可 ...

  4. &num;503&period; 「LibreOJ β Round」ZQC 的课堂 容斥原理&plus;Treap

    题目: 题解: 比较容易发现 : \(x,y\) 的贡献是独立的. 所以可以分开考虑. 假设我们考虑 \(x\).向量在 \(x\) 方向的投影依次是 : \(\{a_1,a_2, ... ,a_n\ ...

  5. LOJ&num;503&period; 「LibreOJ β Round」ZQC 的课堂（容斥&plus;FHQTreap）

    题面 传送门 题解 首先\(x\)和\(y\)两维互相独立,可以分开考虑,我们以\(x\)为例 我们把\(x\)做个前缀和,那么就是问有多少\(i\)满足\(s_is_{i-1}<0\),其中\ ...

  6. loj&num;501 「LibreOJ β Round」ZQC 的树列

    分析 代码(我的代码是瞎jb水过去的) #include<bits/stdc++.h> using namespace std; #define li long long li a[]; ...

  7. loj&num;500 「LibreOJ β Round」ZQC 的拼图

    分析 二分倍数 然后考虑dp[i][j]表示选到第i个x轴覆盖到j的情况y轴最多覆盖多少 贡献柿子可以画图然后相似三角形得到 代码 #include<bits/stdc++.h> usin ...

  8. &lbrack;LOJ&num;500&rsqb;「LibreOJ β Round」ZQC的拼图

    题目   点这里看题目. 分析   首先不难发现答案具有单调性,因此可以二分答案.答案上限为\(V=2m\times \max\{a_i, b_i\}\).   考虑如何去判断当前的答案.设这个答案为 ...

  9. loj &num;547&period; 「LibreOJ β Round &num;7」匹配字符串

    #547. 「LibreOJ β Round #7」匹配字符串   题目描述 对于一个 01 串(即由字符 0 和 1 组成的字符串)sss,我们称 sss 合法,当且仅当串 sss 的任意一个长度为 ...

随机推荐

  1. AD 域账号登录

    域服务数据读写,有俩种模式 1.轻量级的数据读取 _domain是服务器的域名 获取连接PrincipalContext pc = new PrincipalContext(ContextType.D ...

  2. Word2Vec 使用总结

    word2vec 是google 推出的做词嵌入(word embedding)的开源工具. 简单的说,它在给定的语料库上训练一个模型,然后会输出所有出现在语料库上的单词的向量表示,这个向量称为&qu ...

  3. 关于myeclipse中maven项目转换相关设置

    关于myeclipse中maven项目转换相关设置 在myeclipse菜单中,Configure->Convert to Maven Project 这个菜单 如果没有的话,需要做如下设置: ...

  4. poj1265Area（pick定理）

    链接  Pick定理是说,在一个平面直角坐标系内,如果一个多边形的顶点全都在格点上,那么这个图形的面积恰好就等于边界上经过的格点数的一半加上内部所含格点数再减一. pick定理的一些应用 题意不好懂, ...

  5. 车牌识别LPR（七）-- 字符特征

    第七篇:字符特征 选择的字符特征应该满足以下条件: (1)选取的字符特征具有较强的鲁棒性,不受字符变形.弯曲等影响. (2)两个字符的字符特征不能完全相同,但部分相同是允许的,即选择的字符特征是唯一的 ...

  6. jquery 事件委托绑定click的使用方法

    直接绑定ul的click事件  代码如下 复制代码 $("ul").click(function(e) 例子  代码如下 复制代码 $(function(){ //$(" ...

  7. react-native之站在巨人的肩膀上

    react-native之站在巨人的肩膀上 前方高能,大量图片,不过你一定会很爽.如果爽到了,请告诉我

  8. Haproxy&plus;Keepalived搭建Weblogic高可用负载均衡集群

    配置环境说明: KVM虚拟机配置 用途 数量 IP地址 机器名 虚拟IP地址 硬件 内存3G  系统盘20G cpu 4核 Haproxy keepalived 2台 192.168.1.10 192 ...

  9. Windows下Discuz搭建论坛过程

    搭建环境:Win7 + XAMPP5.5 + Discuz3.2 GBK 官方论坛下载安装包,解压,把upload文件夹拷贝到网站文档根目录(例如我的为:D:\IT\XAMPP5.5\htdocs\) ...

  10. FMS4中的P2P功能

    在fms4以前Adobe只允许在stratus中才能使用p2p功能.令人高兴的是,在最新发布的fms4中,p2p功能已经集成进来了,这将给实时视频类的应用带来更高的效率,adobe这次很给力! 为了使 ...

相关文章