ODT_ODT2是什么意思

全栈程序员-站长 • 2022年9月10日上午11:36 • 未分类 • 阅读 0

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

ODT练手

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

n<=1e9 Q<=1e5

#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.net/195422.html原文链接：https://javaforall.net