【洛谷5251】[LnOI2019] 第二代图灵机（线段树+ODT）
2024-08-29 05:02:44
大致题意： 有单点修改数字和区间着色两种修改操作，询问你某段区间内包含所有颜色且数字和最小的子区间的数字和，或某段区间内没有重复颜色且数字和最大的子区间的数字和。数据随机。
\(ODT\)维护颜色
看到区间着色且题目中强调数据随机，容易想到使用\(ODT\)去求解。
于是，我们就可以考虑用\(ODT\)来对颜色进行维护。
线段树维护数字和
但是考虑到要求区间数字和，\(ODT\)就很难搞了。
考虑到我们其实可以对于每个询问，每次找到一个合法区间再询问数字和更新答案。
也就是说，可以把维护颜色和维护数字和分开。
那维护数字和自然可以用线段树喽。
其实本来用树状数组似乎更优，但这题由于写法问题可能还会需要求区间\(Min\)或\(Max\)，树状数组搞起来就很吃力了。
处理询问
以上大致介绍了，可以用线段树维护数字和，\(ODT\)维护颜色。
接下来，再具体介绍一下如何去处理询问。
考虑到这两种询问实际上都具有单调性，因此可以直接用双指针搞。
我们枚举右端点，然后移动左端点。
对于第一种询问，我们需要在保证颜色数量等于\(c\)的情况下才能移动左端点，然后在移动的同时更新答案（不然统计答案的过程会略显麻烦）。
而\(c=1\)的情况可能要特判，直接输出这段区间的最小值。
对于第二种询问，我们只需在出现不合法情况，即出现重复颜色时移动左端点。考虑我们此时刚把右端点的颜色加入，若出现重复颜色，必然是由右端点导致的，因此不断移动左端点直至右端点所属颜色出现次数为\(1\)即可。
但注意，在处理第二种询问时，一旦出现右端点\(Size>1\)的情况，我们在统计完其答案后，需将左端点移动到右端点的位置上，不然就会出现重复颜色。
同理，在统计第二种询问的答案时，要求左端点的右边界与右端点的左边界之间的区间和，不然同样会出现重复颜色。
而且，在第二种情况时容易漏考虑单个颜色的贡献，因此要初始化\(res\)为整段区间的\(Max\)。
大致就是这些吧。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define INF 1e9
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define Gmin(x,y) (x>(y)&&(x=(y)))
using namespace std;
int n,c,a[N+5];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C^FS?FO[C++]=c:(fwrite(FO,1,C,stdout),FO[(C=0)++]=c))
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
int T,C;char c,*A,*B,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Con Ty& x) {write(x),pc('\n');}
I void clear() {fwrite(FO,1,C,stdout),C=0;}
}F;
class SegmentTree//线段树
{
private:
#define STO l,hl,rt<<1
#define ORZ hl+1,r,rt<<1|1
#define PU(x) (O[x]=O[x<<1]+O[x<<1|1])
int n,v[N+5];
struct Interval//维护区间信息
{
int S,Mx,Mn;I Interval(CI s=0,CI mx=-INF,CI mn=INF):S(s),Mx(mx),Mn(mn){}
I Interval operator + (Con Interval& t) Con {return Interval(S+t.S,max(Mx,t.Mx),min(Mn,t.Mn));}
}O[N<<2];
I void Build(CI l,CI r,CI rt)//建树
{
if(!(l^r)) return (void)(O[rt]=Interval(v[l],v[l],v[l]));
RI hl=l+r>>1;Build(STO),Build(ORZ),PU(rt);
}
I int qsu(CI l,CI r,CI rt,CI ql,CI qr)//询问区间和
{
if(ql<=l&&r<=qr) return O[rt].S;RI hl=l+r>>1;
return (ql<=hl?qsu(STO,ql,qr):0)+(qr>hl?qsu(ORZ,ql,qr):0);
}
I int qmx(CI l,CI r,CI rt,CI ql,CI qr)//询问区间最大值
{
if(ql<=l&&r<=qr) return O[rt].Mx;RI hl=l+r>>1,t,res=-INF;
return ql<=hl&&(t=qmx(STO,ql,qr),Gmax(res,t)),qr>hl&&(t=qmx(ORZ,ql,qr),Gmax(res,t)),res;
}
I int qmn(CI l,CI r,CI rt,CI ql,CI qr)//询问区间最小值
{
if(ql<=l&&r<=qr) return O[rt].Mn;RI hl=l+r>>1,t,res=INF;
return ql<=hl&&(t=qmn(STO,ql,qr),Gmin(res,t)),qr>hl&&(t=qmn(ORZ,ql,qr),Gmin(res,t)),res;
}
public:
I void Init(CI x,int* s) {for(RI i=1;i<=x;++i) v[i]=s[i];Build(1,n=x,1);}
I void Update(CI x,CI y)//单点修改（这里使用非递归写法）
{
RI l=1,r=n,rt=1,hl;W(l^r) hl=l+r>>1,x<=hl?(r=hl,rt<<=1):(l=hl+1,(rt<<=1)|=1);
O[rt]=Interval(y,y,y);W(rt>>=1) PU(rt);
}
I int QSum(CI x,CI y) {return qsu(1,n,1,x,y);}
I int QMax(CI x,CI y) {return qmx(1,n,1,x,y);}
I int QMin(CI x,CI y) {return qmn(1,n,1,x,y);}
}T;
class ODT
{
private:
#define IT set<Il>::iterator
#define ins insert
#define era erase
#define fir first
#define LB lower_bound
#define add(x) (!cnt[x]++&&++tot)
#define del(x) (!--cnt[x]&&--tot)
int cnt[N+5];
struct Il//维护区间信息
{
int l,r,v;I Il(CI x=0,CI y=0,CI p=0):l(x),r(y),v(p){}
I bool operator < (Con Il& t) Con {return l<t.l;}
};set<Il> S;
I IT Sp(CI x)//分裂操作
{
IT t;if((t=S.LB(Il(x)))!=S.end()&&!(t->l^x)) return t;
RI l=(--t)->l,r=t->r,v=t->v;S.era(t),S.ins(Il(l,x-1,v));
return S.ins(Il(x,r,v)).fir;
}
public:
I void Init(CI x,int* s)//初始化节点信息
{
for(RI i=(s[0]=s[x+1]=-1,1),t=0;i<=x+2;++i)
s[i]^s[i-1]&&(S.insert(Il(t,i-1,s[i-1])),t=i);
}
I void Assign(CI x,CI y,CI v)//推平操作
{
IT tr=Sp(y+1),tl=Sp(x);S.era(tl,tr),S.ins(Il(x,y,v));
}
I int Q1(CI x,CI y)//处理第一种询问
{
if(!(c^1)) return T.QMin(x,y);//特判c=1
memset(cnt,0,sizeof(cnt));IT tr=Sp(y+1),tl=Sp(x),ti=tl;RI t,res=INF,tot=0;//初始化
W(ti!=tr) {add(ti->v);W(!(tot^c)) t=T.QSum(tl->r,ti->l),Gmin(res,t),del((tl++)->v);++ti;}//移动右端点，在保证颜色数量等于c的情况下才能移动左端点，然后在移动的同时更新答案
return res==INF?-1:res;//判断是否无解，无解返回-1
}
I int Q2(CI x,CI y)//处理第二种询问
{
memset(cnt,0,sizeof(cnt));IT tr=Sp(y+1),tl=Sp(x),ti=tl;RI t,res=T.QMax(x,y);//初始化
W(ti!=tr)
{
++cnt[ti->v];W(ti!=tl&&cnt[ti->v]>1) --cnt[(tl++)->v];//不断移动左端点直至右端点所属颜色出现次数为1
ti!=tl&&(t=T.QSum(tl->r,ti->l),Gmax(res,t));//更新答案
if(ti->l^ti->r) W(ti!=tl) --cnt[(tl++)->v];++ti;//当出现右端点Size>1的情况，将左端点移动到右端点的位置上
}return res;//返回答案
}
}O;
int main()
{
RI Qtot,i,op,x,y,z;for(F.read(n,Qtot,c),i=1;i<=n;++i) F.read(a[i]);T.Init(n,a);//读入数据
for(i=1;i<=n;++i) F.read(a[i]);O.Init(n,a);W(Qtot--)
{
switch(F.read(op,x,y),op)//处理操作
{
case 1:T.Update(x,y);break;case 2:F.read(z),O.Assign(x,y,z);break;
case 3:F.writeln(O.Q1(x,y));break;case 4:F.writeln(O.Q2(x,y));break;
}
}return F.clear(),0;
}
最新文章
- Apache配置中的ProxyPass 和 ProxyPassReverse
- shared_ptr 和 unique_ptr
- 论文笔记之：Deep Reinforcement Learning with Double Q-learning
- linux指令大全(完整篇)（转）
- java.lang.ClassCastException: java.math.BigDecimal cannot be cast to java.lang.String
- R - 一只小蜜蜂...（第二季水）
- Android中Broadcast Receiver组件具体解释
- HDU1163 Eddy&#39;s digital Roots【九剩余定理】
- Android两种为ViewPager+Fragment添加Tab的方式
- EXT 可选择图片列表的表单控件实现
- cmd提取时间格式（小时）问题以及Windows系统语言判断
- 阿里云RDS数据库改造迁移方案
- Tigase8.0 源代码分析：一、启动篇
- python——元组和字典类型简明理解
- linux每日命令(21)：find命令之exec
- How to add hyperlink in JLabel
- python学习：python的星号（*）和双星号（**）用法
- Java多线程之Future与FutureTask
- 配置ssh互信的一个小问题记录
- 选择排序(直接排序)java语言实现