当前位置: 首页 > news >正文

\(m\) 个数,\(n\) 次操作,每次操作求 \([l,r]\) 内最大最小原始编号。将 \([l,r]\) 内下标与 \(l\) 奇偶性相同的元素删去,剩下元素补到前面。

唐氏症题。想了半天直接维护。

线段树维护区间剩余元素个数,以及操作标记 0/1 表示从开头/开头+1 位置开始删的操作。发现标记无法合并,但是注意到每次操作元素个数减小一倍,一个区间有效操作次数 \(log\) 量级的,故维护操作队列。

#include<bits/stdc++.h>
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define intz(x,y) memset((x),(y),sizeof((x)))
inline int lowbit(int x){return x&-x;}
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
#define int ll
const int N=1e5+5;
struct sgt{int rt,tot;struct node{int ls,rs;ll x;vector<bool>laz;}t[N*60];void pushup(int u){t[u].x=t[t[u].ls].x+t[t[u].rs].x;}void add(int u,bool f){if(t[u].x)t[u].laz.pb(f);t[u].x=(f?t[u].x+1:t[u].x)/2;}void pd(int u,ll l,ll r){ll mid=l+r>>1;if(!t[u].ls)t[t[u].ls=++tot].x=mid-l+1;if(!t[u].rs)t[t[u].rs=++tot].x=r-mid;for(int i=0,laz;i<t[u].laz.size();i++){laz=(t[t[u].ls].x&1)?!t[u].laz[i]:t[u].laz[i];add(t[u].ls,t[u].laz[i]),add(t[u].rs,laz);}t[u].laz.clear();}ll upd(int &u,ll l,ll r,ll lf,ll rt,ll X){if(!u)t[u=++tot].x=r-l+1;if(l>=lf&&r<=rt){ll q=t[u].x;return add(u,X&1),q;}ll mid=l+r>>1,res=0;pd(u,l,r);if(lf<=mid)res+=upd(t[u].ls,l,mid,lf,rt,X);if(rt>mid)res+=upd(t[u].rs,mid+1,r,lf,rt,X+res);pushup(u);return res;}ll get(int u,ll l,ll r,ll x){if(l==r)return l;ll mid=l+r>>1;pd(u,l,r);if(t[t[u].ls].x>=x)return get(t[u].ls,l,mid,x);else return get(t[u].rs,mid+1,r,x-t[t[u].ls].x);}
}t;
inline void UesugiErii(){ll n,m;cin>>n>>m;while(n--){ll l,r,L,R;cin>>l>>r;L=t.get(t.rt,1,m,l),R=t.get(t.rt,1,m,r);cout<<L<<' '<<R<<'\n';t.upd(t.rt,1,m,L,R,0);}
}
signed main(){cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}
http://www.hskmm.com/?act=detail&tid=35012

相关文章:

  • Microsoft 代理框架简介(预览版):让每个开发人员都能轻松使用 AI 代理
  • 2025 年破碎机厂家最新推荐榜,聚焦企业技术实力与市场口碑深度解析圆锥/辊式/对辊/煤矸石/砂石破碎机厂家推荐
  • 站位3
  • AI 的能源危机:训练一个模型究竟要耗掉多少电?
  • 2025 年制砂机厂家最新推荐榜,聚焦企业技术实力与市场口碑深度解析高效/冲击式/砂石/新疆制砂机厂家推荐
  • 拆解3D Gaussian Splatting:原理框架、实战 demo 与自驾仿真落地探索!
  • WebSocket Turbo Intruder:挖掘WebSocket安全漏洞的利器
  • Gitee:本土化技术平台如何重塑中国开发者生态
  • Hyper-V 与 root的Android7模拟器共存
  • 视频监控界的“万能翻译器”:视频汇聚平台EasyCVR视频接入功能全解读
  • 基于Ubuntu22.04 部署Dify详细教程
  • Java 8 - Optional类
  • 使用 Github Pages 和 Hexo 搭建博客
  • linux 移动硬盘加载失败
  • 得帆AI aPaaS(AI低代码)1.0产品特性(5)-智能搭建(二)
  • 吱吱企业即时通讯不止通讯,还是数字化协作的安全与效率标杆
  • callout样式
  • 得帆AI aPaaS(AI低代码)1.0产品特性(4)-智能搭建(一)
  • 日记11
  • 代码随想录Day11
  • 腾讯企业邮箱管理
  • C# 使用NPOI生成Word文件
  • 随机生成动态头像
  • element 表单校验失败定位到指定元素
  • 2025年湖北武汉实验室设计哪家口碑好/哪家信誉好/哪家售后好?
  • 国产化Word处理控件Spire.Doc教程:用Java实现TXT文本与Word互转的完整教程
  • C# Avalonia 16- Animation- BombDropper
  • 2025年太阳能板定制厂家可靠推荐与排行榜
  • 实验室改造推荐厂家/实验室设计供应商推荐/实验室装修找哪个?
  • 2025年太阳能板定制厂家口碑排行榜单:权威推荐与选择指南