HDU - 6521 Party (SYSU校赛K题)(线段树)

题意：n个人排成一列，一开始他们互不认识，每次选[l,r]上的人开party，使他们互相认识，求出每次party之后新互相认识的人的对数。

思路：把“互相认识”变成单向连边，只考虑左边的人对右边的贡献。对于每个人，他认识的人的区间必然是连续的，可以维护他认识的最右边的人R，这样更新操作相当于把[l,r]所有人的R值变成max(R,r)，可以构造线段树维护每个区间中R的最小值mi，如果最小值大于等于R的话就不用更新了，直接退出，否则暴力修改每个点的值。

先上个假算法：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=5e5+,inf=0x3f3f3f3f;

 #define ls (u<<1)

 #define rs (u<<1|1)

 #define mid ((l+r)>>1)

 int mi[N<<],n,m;

 ll ans;

 void pu(int u) {mi[u]=min(mi[ls],mi[rs]);}

 void build(int u=,int l=,int r=n) {

     if(l==r) {mi[u]=l; return;}

     build(ls,l,mid),build(rs,mid+,r),pu(u);

 }

 void upd(int L,int R,int u=,int l=,int r=n) {

     if(l>R||r<L||mi[u]>=R)return;

     if(l==r) {ans+=R-mi[u],mi[u]=R; return;}

     upd(L,R,ls,l,mid),upd(L,R,rs,mid+,r),pu(u);

 }

 int main() {

     while(scanf("%d%d",&n,&m)==) {

         build();

         while(m--) {

             ans=;

             int l,r;

             scanf("%d%d",&l,&r);

             upd(l,r);

             printf("%lld\n",ans);

         }

     }

     return ;

 }

这个算法本身是没有问题的，交上去也能AC，但会被一些极端的数据卡死，比如[1,1],[1,2],...,[1,n]这样的，会被卡成n^2，因此可以加一些优化。

由于每个人认识的最右边的人R的值是非递减的，即任意i>j，R[i]>=R[j]，因此每次发生变化的区间必然是连续的，可以把单点修改换成区间修改，这样就不会被卡了。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=5e5+,inf=0x3f3f3f3f;

 #define ls (u<<1)

 #define rs (u<<1|1)

 #define mid ((l+r)>>1)

 int mx[N<<],mi[N<<],lz[N<<],n,m;

 ll sum[N<<],ans;

 void pu(int u) {

     mi[u]=min(mi[ls],mi[rs]);

     mx[u]=max(mx[ls],mx[rs]);

     sum[u]=sum[ls]+sum[rs];

 }

 void pd(int u,int l,int r) {

     if(lz[u]) {

         sum[ls]=(ll)lz[u]*(mid-l+),sum[rs]=(ll)lz[u]*(r-mid);

         mi[ls]=mi[rs]=mx[ls]=mx[rs]=lz[ls]=lz[rs]=lz[u],lz[u]=;

     }

 }

 void build(int u=,int l=,int r=n) {

     lz[u]=;

     if(l==r) {sum[u]=mi[u]=mx[u]=l; return;}

     build(ls,l,mid),build(rs,mid+,r),pu(u);

 }

 void upd(int L,int R,int u=,int l=,int r=n) {

     if(l>R||r<L||mi[u]>=R)return;

     if(l>=L&&r<=R&&mx[u]<=R) {sum[u]=(ll)R*(r-l+),mi[u]=mx[u]=lz[u]=R; return;}

     pd(u,l,r);

     upd(L,R,ls,l,mid),upd(L,R,rs,mid+,r),pu(u);

 }

 int main() {

     while(scanf("%d%d",&n,&m)==) {

         build(),ans=sum[];

         while(m--) {

             int l,r;

             scanf("%d%d",&l,&r);

             upd(l,r);

             printf("%lld\n",sum[]-ans);

             ans=sum[];

         }

     }

     return ;

 }

然后据说还有一种叫“吉司机线段树”的东西也能做？赶紧学了学(便乘)，感觉对于区间取max/min这类问题的处理强大的，普适性也比较高。

对于区间取max操作，其基本思想是维护区间和sum,区间最小值mi,区间次小值se以及区间最小值个数nmi。如果要对[l,r]上的所有数与x取max，那么分三种情况讨论即可：

1)若x<=mi，则修改操作无效，退出

2)若mi<x<se，则将mi改成x，(sum+=x-mi)*ni，其余不变，同时下放标记

3)若x>=se，则在左右区间递归进行下去

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=5e5+,inf=0x3f3f3f3f;

 #define ls (u<<1)

 #define rs (u<<1|1)

 #define mid ((l+r)>>1)

 int mi[N<<],nmi[N<<],se[N<<],lz[N<<],n,m;

 ll sum[N<<],ans;

 void pu(int u) {

     sum[u]=sum[ls]+sum[rs];

     mi[u]=min(mi[ls],mi[rs]),se[u]=max(mi[ls],mi[rs]);

     se[u]=se[u]==mi[u]?min(se[ls],se[rs]):min(se[u],min(se[ls],se[rs]));

     nmi[u]=(mi[ls]==mi[u]?nmi[ls]:)+(mi[rs]==mi[u]?nmi[rs]:);

 }

 void change(int u,int x) {sum[u]+=(ll)nmi[u]*(x-mi[u]),mi[u]=lz[u]=x;}

 void pd(int u) {

     if(~lz[u]) {

         if(mi[ls]<lz[u])change(ls,lz[u]);

         if(mi[rs]<lz[u])change(rs,lz[u]);

         lz[u]=-;

     }

 }

 void build(int u=,int l=,int r=n) {

     lz[u]=-;

     if(l==r) {sum[u]=mi[u]=l,nmi[u]=,se[u]=inf; return;}

     build(ls,l,mid),build(rs,mid+,r),pu(u);

 }

 void upd(int L,int R,int x,int u=,int l=,int r=n) {

     if(l>R||r<L||x<=mi[u])return;

     if(l>=L&&r<=R&&x<se[u]) {change(u,x); return;}

     pd(u),upd(L,R,x,ls,l,mid),upd(L,R,x,rs,mid+,r),pu(u);

 }

 int main() {

     while(scanf("%d%d",&n,&m)==) {

         build(),ans=sum[];

         while(m--) {

             int l,r;

             scanf("%d%d",&l,&r);

             upd(l,r,r);

             printf("%lld\n",sum[]-ans);

             ans=sum[];

         }

     }

     return ;

 }

巴特西

HDU - 6521 Party (SYSU校赛K题)(线段树)

最新文章

热门文章