bzoj5003: 与链 5004: 开锁魔法II 5005:乒乓游戏

www.lydsy.com/JudgeOnline/upload/task.pdf

第一题题意可以转为选一个长度k的序列,每一项二进制的1的位置被下一项包含,且总和为1,考虑每个二进制位的出现位置,可以转化为一个多重背包求方案数的问题。

第二题构成一些环,可以每个环直接计算,然后合并答案。

第三题区间包含相当于单向边,区间相交不包含就是双向边,将区间相交不包含的情况缩点,剩余的单向边构成一棵树(几个被缩起来的区间可以用它们的并集表示),用lct维护树形态,查询即为询问两点是否是祖先关系,对于修改,由于区间长度递增,只有至多两种缩点情况:1.新加入的区间与某棵树的根缩点(另用平衡树维护所有根对应的区间,实际上需要再分几类);2.新加入的区间与树上非根的点缩点(另用线段树维护所有非根节点对应的区间)。

前两题代码实现比较简单,所以这里只给出第三题的代码。

#include<bits/stdc++.h>
int _(){
int x=,f=,c=getchar();
while(c<)c=='-'?f=-:,c=getchar();
while(c>)x=x*+c-,c=getchar();
return x*f;
}
#define lc ch][0
#define rc ch][1
#define fa ch][2
const int N=2e5+,inf=0x3f3f3f3f;
struct itv{
int l,r,id;
bool operator<(const itv&w)const{return l<w.l;}
};
struct cmpl{bool operator()(const itv&a,const itv&b){return a.l>b.l;}};
struct cmpr{bool operator()(const itv&a,const itv&b){return a.r<b.r;}};
std::set<itv>st;
int n,f[N],ch[N][],idp=;
int qs[N][],xs[N],xp=,mx=,tl[],tr[];
std::priority_queue<itv,std::vector<itv>,cmpl>ls[N];
std::priority_queue<itv,std::vector<itv>,cmpr>rs[N];
int gf(int x){
while(x!=x[f])x=x[f]=x[f][f];
return x;
}
bool nrt(int x){return x==x[fa][lc]||x==x[fa][rc];}
int wc(int x){return x==x[fa][rc];}
void rot(int x){
int f=x[fa],g=f[fa],d=wc(x);
if(nrt(f))g[ch][wc(f)]=x;
x[fa]=g;
(f[ch][d]=x[ch][d^])[fa]=f;
(x[ch][d^]=f)[fa]=x;
}
void sp(int x){
while(nrt(x)){
int f=x[fa];
if(nrt(f))rot(wc(x)==wc(f)?f:x);
rot(x);
}
}
int acs(int x){int y=;for(;x;sp(x),x[rc]=y,y=x,x=x[fa]);return y;}
void lk(int a,int b){acs(a)[fa]=b;}
void ctlk(int a,int b){acs(a),sp(a);a[lc][fa]=,a[lc]=,a[fa]=b;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void tl_up(int x){
tl[x+mx]=ls[x].size()?ls[x].top().l:inf;
for(x=x+mx>>;x;x>>=)tl[x]=min(tl[x<<],tl[(x<<)+]);
}
void tr_up(int x){
tr[x+mx]=rs[x].size()?rs[x].top().r:-inf;
for(x=x+mx>>;x;x>>=)tr[x]=max(tr[x<<],tr[(x<<)+]);
}
int $(int x){
return std::lower_bound(xs+,xs+xp+,x)-xs;
}
void tr_ins(itv w){
int _l=$(w.l),_r=$(w.r);
ls[_r].push(w),tl_up(_r);
rs[_l].push(w),tr_up(_l);
}
void chk(itv w,int z){
int p,u;
while(tl[z]<w.l){
for(p=z;p<mx;p<<=,p+=tl[p]>=w.l);
p-=mx;
u=ls[p].top().id;
if(u==f[u])ctlk(u,f[u]=w.id);
ls[p].pop();
tl_up(p);
}
while(tr[z]>w.r){
for(p=z;p<mx;p<<=,p+=tr[p]<=w.r);
p-=mx;
u=rs[p].top().id;
if(u==f[u])ctlk(u,f[u]=w.id);
rs[p].pop();
tr_up(p);
}
}
void tr_del(itv w){
for(int l=$(w.l)+mx,r=$(w.r)+mx;r-l>;l>>=,r>>=){
if(~l&)chk(w,l+);
if(r&)chk(w,r-);
}
}
void ins(itv w){
tr_del(w);
std::set<itv>::iterator it=st.lower_bound(w);
if(it!=st.end()&&it->l==w.l&&it->r>w.r)return lk(w.id,f[w.id]=it->id);
if(it!=st.begin()&&(--it)->r>w.l){
int u=it->id;
if(it->r>=w.r)return lk(w.id,f[w.id]=u);
w.l=it->l,f[u]=w.id;
lk(u,w.id);
st.erase(it);
}
while((it=st.lower_bound(w))!=st.end()&&it->l<w.r){
int u=it->id;
if(it->r>w.r)w.r=it->r,f[u]=w.id;
else tr_ins(*it);
lk(u,w.id);
st.erase(it);
}
st.insert(w);
}
bool query(int x,int y){
x=gf(x),y=gf(y);
if(x==y)return ;
x=acs(x);
int y0=y;
for(;nrt(y);y=y[fa]);
sp(y0);
return x==y;
}
int main(){
n=_();
for(int i=;i<=n;++i){
qs[i][]=_();
qs[i][]=_();
qs[i][]=_();
if(qs[i][]==)xs[++xp]=qs[i][],xs[++xp]=qs[i][];
}
std::sort(xs+,xs+xp+);
for(;mx<=xp+;mx<<=);
for(int i=mx*-;i;--i)tl[i]=inf,tr[i]=-inf;
for(int i=;i<=n;++i){
f[i]=i;
int o=qs[i][],x=qs[i][],y=qs[i][];
if(o==)ins((itv){x,y,++idp});
else puts(query(x,y)?"YES":"NO");
}
return ;
}
上一篇:HihoCoder 1075 开锁魔法III(概率DP+组合)


下一篇:【bzoj5004】开锁魔法II 组合数学+概率dp