2019-8-10 考试总结-白红宇

2019-8-10 考试总结

阅读量：4455 次

发布时间：2019-06-07

本文共 3906 字，大约阅读时间需要 13 分钟。

贪心，是个水题。

考试的时候打的代码时间复杂度有点高，得了$80$分。

正解：

维护一个优先队列，队首为编号最小的。

每次贪心，队首能走就走，然后替换队首为当前节点编号。

队首掉队后直接$pop$。

丑陋的代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define Maxn 1000050#define Reg register#define int long long#define _max(x,y) ((x)>(y)?(x):(y))using namespace std;int T,n,m,d,l,las,ans,A[Maxn],nex[Maxn];priority_queue
           
            
             ,greater
             
               > q;signed main(){ scanf("%lld",&T); while(T--) { scanf("%lld%lld%lld%lld",&n,&m,&d,&l); las=0; for(Reg int i=1;i<=n;++i) scanf("%lld",&A[i]); ans=0; for(Reg int i=1;i<=m;++i) q.push(0); for(Reg int i=1;i<=n;++i) { while(!q.empty()&&A[i]-A[q.top()]>d) q.pop(); if(q.empty()) break; if(A[i]-A[q.top()]<=d) { q.pop(); q.push(i); } } while(!q.empty()) { if(l-A[q.top()]<=d) ++ans; q.pop(); } if(ans>=m) printf("Excited\n"); else printf("%lld\n",ans); } return 0;}

View Code

线段树维护那几个标记，学长$pdf$中的题解：

实际上,每个加数和删除的操作可以看作是入栈和弹栈操作,之后可以用线段树维护多个操作间的关系。

线段树的下标是操作时间,由于我们想得到整个序列经过修改操作后的结果,因此线段树上维护四个信息:

$s$:区间内加数总和(仅考虑区间内部影响);

$nd$:当前区间向前删除数字的数量;

$na$:当前区间内“净”加的元素数。

$sd$:当前区间被右兄弟删除后的总和。 ※仅对左儿子维护此信息。

我们通过维护以上四个标记,就可以得到答案$(root->s)$。现在我们考虑如何维护信息。

首先,在建树或修改时,只需要将叶子节点的前三个标记维护好即可;

在递归返回时,再计算最后一个。

如果左儿子不够右儿子删,那么非常简单,直接利用这几个标记计算即可,$l->sd=0$。

比较麻烦的是左儿子不被删光的情况。我们先实现一个函数$cal(x)$,利用$sd$标记计算在当前区间中删去$x$个元素后的和。

考虑$cal(x)$的实现(当前节点为$o$):

$1$.若$r->na>x$,那么返回$l->sd+r->cal(x)$。

$2$.若$r->na<x$,那么右儿子不够删,返回$l->cal(x-r->na+r->nd)$ ※这里非常重要,一定要再删掉右儿子要删的

$3$.若$r->na==x$,直接返回$l->sd$。

有了这个函数,我们就可以非常方便地计算左儿子的$sd$,维护其他标记了,不再赘述。

时间复杂度$O(nlog^2)$。

丑陋的代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define Maxn 1000050#define Reg register#define int long long#define New() new Tree#define _max(x,y) ((x)>(y)?(x):(y))#define _min(x,y) ((x)<(y)?(x):(y))using namespace std;int m,q;struct Tree {Tree *ch[2],*fa; int s,na,nd,sd;};Tree *root=New();int cal(Tree *p,int l,int r,int num){    if(l==r)    {        if(num) return 0;        else return p->s;    }    int mid=(l+r)>>1;    if(p->ch[1]->na==num) return p->ch[0]->sd;    else if(p->ch[1]->na
           
            ch[0],l,mid,num-p->ch[1]->na+p->ch[1]->nd); else return p->ch[0]->sd+cal(p->ch[1],mid+1,r,num); return 0;}void up(Tree *p,int l,int r){ int mid=(l+r)>>1; p->nd=p->na=0; if(p->ch[0]->na<=p->ch[1]->nd) { p->ch[0]->sd=0; p->nd+=p->ch[1]->nd-p->ch[0]->na; } else { p->ch[0]->sd=cal(p->ch[0],l,mid,p->ch[1]->nd); p->na+=p->ch[0]->na-p->ch[1]->nd; } p->s=p->ch[0]->sd+p->ch[1]->s; p->na+=p->ch[1]->na; p->nd+=p->ch[0]->nd; return;}void build(Tree *p,int l,int r){ if(l==r) { int k,v; scanf("%lld%lld",&k,&v); if(k==0) p->s=p->sd=v,p->na=1,p->nd=0; else p->s=p->sd=p->na=0,p->nd=v; return; } int mid=(l+r)>>1; if(l<=mid) { if(p->ch[0]==NULL) p->ch[0]=New(),p->ch[0]->fa=p; build(p->ch[0],l,mid); } if(mid+1<=r) { if(p->ch[1]==NULL) p->ch[1]=New(),p->ch[1]->fa=p; build(p->ch[1],mid+1,r); } up(p,l,r); return;}void chan(Tree *p,int l,int r,int c,int k,int v){ if(l==r) { if(k==1) p->s=p->na=p->sd=0,p->nd=v; else p->s=v,p->na=1,p->nd=0,p->sd=v; return; } int mid=(l+r)>>1; if(c<=mid) chan(p->ch[0],l,mid,c,k,v); else chan(p->ch[1],mid+1,r,c,k,v); up(p,l,r); return;}signed main(){ scanf("%lld%lld",&m,&q); build(root,1,m); for(Reg int i=1,k,c,v;i<=q;++i) { scanf("%lld%lld%lld",&c,&k,&v); chan(root,1,m,c,k,v); printf("%lld\n",root->s); } return 0;}