大家好,又见面了,我是你们的朋友全栈君。
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.cn/195422.html原文链接:https://javaforall.cn