概述
题意 ： 给定a数组和b数组，有两种操作。
第一种操作：每次查询【L,R】区间内有多少数满足a【i】>=b【i】
第二种操作：将a数组【L,R】区间内的数全部置为x
考虑到b数组始终不变，用归并树维护b数组，在建树时归并排序，每个节点维护区间内b的有序序列，全部保存在pool数组中。用st和en维护该节点最早和最后出现在pool中的位置。更新时由于a数组全部被置为x，二分查找该节点第一个大于x的位置pos，更新sum值为pos-st【rt】，下放lazy标记时也需要二分的更新。
#include <bits/stdc++.h>
#define MAXN 100010
#define LL long long
using namespace std ;
int a[MAXN],b[MAXN],tot;
int st[MAXN*4],en[MAXN*4];//st[rt]表示rt节点在pool数组中最早出现位置，en[rt]则表示最后出现位置
int sum[MAXN*4],add[MAXN*4],pool[MAXN*20];
int c,d;
LL res;
const int mod=1000000007;
void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r)
{
add[rt]=-1;
if(l==r)
{
st[rt]=++tot,en[rt]=tot;
pool[tot]=b[l];
sum[rt]=(a[l]>=b[l]);
return ;
}
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
pushup(rt);
int l1=st[rt<<1],r1=en[rt<<1],l2=st[rt<<1|1],r2=en[rt<<1|1];
st[rt]=tot+1;
while(l1<=r1&&l2<=r2)
{
if(pool[l1]<=pool[l2]) pool[++tot]=pool[l1++];
else pool[++tot]=pool[l2++];
}
while(l1<=r1) pool[++tot]=pool[l1++];
while(l2<=r2) pool[++tot]=pool[l2++];
en[rt]=tot;
}
void pushdown(int rt)
{
if(add[rt]!=-1)
{
add[rt<<1]=add[rt];
add[rt<<1|1]=add[rt];
int L,R,mid;
L=st[rt<<1],R=en[rt<<1];
while(L<=R)
{
mid=(L+R)>>1;
if(pool[mid]<=add[rt]) L=mid+1;
else R=mid-1;
}
sum[rt<<1]=L-st[rt<<1];
L=st[rt<<1|1],R=en[rt<<1|1];
while(L<=R)
{
mid=(L+R)>>1;
if(pool[mid]<=add[rt]) L=mid+1;
else R=mid-1;
}
sum[rt<<1|1]=L-st[rt<<1|1];
add[rt]=-1;
}
}
void update(int rt,int l,int r,int x)
{
if(c<=l&&d>=r)
{
int L=st[rt],R=en[rt],mid;
while(L<=R)
{
mid=(L+R)>>1;
if(pool[mid]<=x) L=mid+1;
else R=mid-1;
}
sum[rt]=L-st[rt];
add[rt]=x;
return ;
}
int m=(l+r)>>1;
pushdown(rt);
if(c<=m) update(rt<<1,l,m,x);
if(d>m) update(rt<<1|1,m+1,r,x);
pushup(rt);
}
int query(int rt,int l,int r)
{
if(c<=l&&d>=r)
{
return sum[rt];
}
int m=(l+r)>>1;
pushdown(rt);
int ans=0;
if(c<=m) ans+=query(rt<<1,l,m);
if(d>m) ans+=query(rt<<1|1,m+1,r);
return ans;
}
int A,B,C=~(1<<31),M=(1<<16)-1;
int rnd()
{
A=(36969+(res>>3))*(A&M)+(A>>16);
B=(18000+(res>>3))*(B&M)+(B>>16);
return (C&((A<<16)+B))%1000000000;
}
int main()
{
freopen("x.txt","r",stdin);
int t,n,m,x;
scanf("%d",&t);
while(t--)
{
tot=0,res=0;
scanf("%d%d%d%d",&n,&m,&A,&B);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
build(1,1,n);
int ans=0;
for(int i=1;i<=m;i++)
{
c=rnd()%n+1,d=rnd()%n+1,x=rnd()+1;
if(c>d) swap(c,d);
if((c+d+x)&1)update(1,1,n,x);
else
{
res=0;
res+=1LL*query(1,1,n);
ans=(1LL*i*res%mod+ans)%mod;
}
}
printf("%dn",ans);
}
return 0;
}
这种算法的时间复杂度为O(mlog2n),运行结果TLE，被出题者很不厚道的卡掉了。
我们思考需要每次查询的时候都二分的查询第一个不大于x的位置吗。
其实可以在每次更新之前先二分查找根节点最后一个不大于x的位置，用两个数组pl和pr分别存pool【i】所在节点左右儿子中最后一个不大于pool【i】的位置，在建树的时候顺便预处理好，在更新的时候记录x在当前结点中的排名pos，这样更新时候的复杂度就是O（1）了，总的复杂度为O（mlogn）
//O(nlogn)算法实现
//Time：5272ms
#include <bits/stdc++.h>
#define MAXN 100010
#define LL long long
using namespace std ;
int a[MAXN],b[MAXN],tot;
int st[MAXN*4],en[MAXN*4];//st[rt]表示rt节点在pool数组中最早出现位置，en[rt]则表示最后出现位置
int sum[MAXN*4],add[MAXN*4],pool[MAXN*20];
int pl[MAXN*20],pr[MAXN*20];//pl[i]表示pool[i]所在节点左儿子最后一个小于pool[i]的位置，pr[i]则表示右儿子
int c,d;
LL res;
const LL mod=1000000007;
inline void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r)
{
add[rt]=-1;
if(l==r)
{
st[rt]=++tot,en[rt]=tot;
pool[tot]=b[l];
sum[rt]=(a[l]>=b[l]);
return ;
}
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
pushup(rt);
int l1=st[rt<<1],r1=en[rt<<1],l2=st[rt<<1|1],r2=en[rt<<1|1];
st[rt]=tot+1;
while(l1<=r1&&l2<=r2)
{
if(pool[l1]<=pool[l2]) pool[++tot]=pool[l1++];
else pool[++tot]=pool[l2++];
}
while(l1<=r1) pool[++tot]=pool[l1++];
while(l2<=r2) pool[++tot]=pool[l2++];
en[rt]=tot;
l1=st[rt<<1],l2=st[rt<<1|1];
for(int i=st[rt];i<=en[rt];i++)
{
while(pool[l1]<=pool[i]&&l1<=r1) l1++;
while(pool[l2]<=pool[i]&&l2<=r2) l2++;
pl[i]=l1-1,pr[i]=l2-1;
if(pl[i]<st[rt<<1]) pl[i]=0;
if(pr[i]<st[rt<<1|1]) pr[i]=0;
}
}
inline void pushdown(int rt)
{
if(add[rt]!=-1)
{
int pos=add[rt];
add[rt<<1]=pl[pos];
add[rt<<1|1]=pr[pos];
sum[rt<<1]=pl[pos]?pl[pos]-st[rt<<1]+1:0;
sum[rt<<1|1]=pr[pos]?pr[pos]-st[rt<<1|1]+1:0;
add[rt]=-1;
}
}
inline void update(int rt,int l,int r,int pos)
{
if(c<=l&&d>=r)
{
sum[rt]=pos?pos-st[rt]+1:0;
add[rt]=pos;
return ;
}
int m=(l+r)>>1;
pushdown(rt);
if(c<=m) update(rt<<1,l,m,pl[pos]);
if(d>m) update(rt<<1|1,m+1,r,pr[pos]);
pushup(rt);
}
inline int query(int rt,int l,int r)
{
if(c<=l&&d>=r)
{
return sum[rt];
}
int m=(l+r)>>1;
pushdown(rt);
int ans=0;
if(c<=m) ans+=query(rt<<1,l,m);
if(d>m) ans+=query(rt<<1|1,m+1,r);
return ans;
}
inline int solve(int x)
{
int L=st[1],R=en[1],mid,ans=0;
while(L<=R)
{
mid=(L+R)>>1;
if(x>=pool[mid]) ans=mid,L=mid+1;
else R=mid-1;
}
return ans;
}
int A,B,C=~(1<<31),M=(1<<16)-1;
inline int rnd()
{
A=(36969+(res>>3))*(A&M)+(A>>16);
B=(18000+(res>>3))*(B&M)+(B>>16);
return (C&((A<<16)+B))%1000000000;
}
int main()
{
//freopen("x.txt","r",stdin);
int t,n,m,x;
scanf("%d",&t);
while(t--)
{
tot=0,res=0;
scanf("%d%d%d%d",&n,&m,&A,&B);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
build(1,1,n);
LL ans=0;
for(int i=1;i<=m;i++)
{
c=rnd()%n+1,d=rnd()%n+1,x=rnd()+1;
if(c>d) swap(c,d);
if((c+d+x)&1)update(1,1,n,solve(x));
else
{
res=0;
res+=1LL*query(1,1,n);
ans=(1LL*i*res+ans)%mod;
}
}
printf("%lldn",ans);
}
return 0;
}
最后
以上就是清爽斑马为你收集整理的HDU -5737 归并树+二分的全部内容，希望文章能够帮你解决HDU -5737 归并树+二分所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复