前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ODT_ODT2是什么意思

ODT_ODT2是什么意思

作者头像
全栈程序员站长
发布2022-09-30 18:59:50
2050
发布2022-09-30 18:59:50
举报
文章被收录于专栏:全栈程序员必看

大家好,又见面了,我是你们的朋友全栈君。

ODT练手

CF915E 题意:Q次区间(1~n)操作,k=2区间(l,r)变为1, k=1区间(l,r)变为0 ,一开始全是1问每次操作后1的数目

n<=1e9 Q<=1e5

代码语言:javascript
复制
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll qmod(ll a,ll b,ll mod){
	ll res=1;
	while(b){
		res=res*a%mod;
		if(a&1)a=a*a%mod;
		b=b>>1;
	}return res%mod;
}
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

ll ans=0;
namespace ODT{//珂朵莉树 
	#define Poi set<node>::iterator 
	#define ll long long
	struct node{
		int l,r;mutable ll v;
		node(int l,int r,ll v):l(l),r(r),v(v){}
		bool operator <(const node &V)const{
			return l<V.l;
		}
	};
	set<node>S;
	inline Poi spilt(int pos){//核心 根据区间操作 维护新的区间到set 
		Poi poi=S.lower_bound(node(pos,-1,0));
		if(poi!=S.end()&&poi->l==pos)return poi;
		poi--;
		int nl=poi->l;
		int nr=poi->r;
		ll nv=poi->v;
		S.erase(poi);
		S.insert(node(nl,pos-1,nv));
		return S.insert(node(pos,nr,nv)).first;
	}
	inline void fuck(int l,int r,ll v){//核心 区间赋值,减少node 
		Poi por=spilt(r+1);
		Poi pol=spilt(l);
		S.erase(pol,por);
		S.insert(node(l,r,v));
	}
	void add(int l,int r,ll val){//区间加 
		Poi por=spilt(r+1);
		Poi pol=spilt(l);
		for(;pol!=por;pol->v+=val,++pol);
	}
	
	void op3(int l,int r,int v){//区间操作自定义 
		Poi por=spilt(r+1);//先右后左防止RE 
		Poi pol=spilt(l);Poi pok=pol;
		for(;pok!=por;++pok){
			int col=pok->v;
			if(col==0)ans-=(pok->r-pok->l+1);
		}
		S.erase(pol,por);
		S.insert(node(l,r,v));
		if(v==0)ans+=r-l+1;
	}
	
	
	ll op4(int l,int r,ll x,ll mod){
		Poi por=spilt(r+1);
		Poi pol=spilt(l);
		for(;pol!=por;++pol){
			ans=ans+qmod(pol->v,x,mod);
			ans%=mod;
		}
		return ans;
	}
}

int main(){
	using namespace ODT;
	int n,q;n=read();q=read();
	
	S.insert(node(1,n,0));ans=n;
	while(q--){
		int l,r,v;l=read();r=read();v=read();
		op3(l,r,v%2);
		printf("%d\n",ans); 
	}
	
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/195422.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年9月10日 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档