【集训第三天·疯狂训练】哦，顺带学习了manacher

　　虽然说是疯狂训练吧，但是也没写多少题，就把伸展树的操作熟悉了一下，ac了5个题目。

　　一整天没啥可吐槽的，除了昨天在机房打游戏的某位朋友翻车后和教练谈了谈心2333

　　说题吧。。

　　1.BZOJ1208 HNOI2004 宠物收养所

　　这个题思路很简单，当做模板题打，在模板题中也算是简单的了，涉及操作：前驱，后继，插入，删除。。输入进来就插入，领养走就删除，并没有什么可说的。加上一个标记表示现在树上表示的是宠物还是人。

　　另外听说可以用set做，但是我并不会set（？？？set都不会吃屎吧）。

CODE:

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n,size,rt,kind,t1,t2;

 long long ans;

 int tr[][],num[],fa[];

 void rotate(int x,int &k)

 {

     int y=fa[x],z=fa[y],l,r;

     if(tr[y][]==x)l=;else l=;r=l^;

     if(y==k)k=x;

     else{if(tr[z][]==y)tr[z][]=x;else tr[z][]=x;}

     fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;

     tr[y][l]=tr[x][r];tr[x][r]=y;

 }

 void splay(int x,int &k)

 {

     int y,z;

     while(x!=k)

     {

         y=fa[x],z=fa[y];

         if(y!=k)

         {

             if((tr[y][]==x)^(tr[z][]==y))rotate(x,k);

             else rotate(y,k);

         }

         rotate(x,k);

     }

 }

 void ins(int &k,int x,int last)

 {

     if(k==){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;}

     if(x<num[k])ins(tr[k][],x,k);else ins(tr[k][],x,k);

 }

 void del(int x)

 {

     splay(x,rt);

     if(tr[x][]*tr[x][]==)

     {rt=tr[x][]+tr[x][];}

     else

     {

         int k=tr[x][];

         while(tr[k][])k=tr[k][];

         tr[k][]=tr[x][];fa[tr[x][]]=k;

         rt=tr[x][];

     }

     fa[rt]=;

 }

 void ask_before(int k,int x)

 {

     if(k==)return;

     if(num[k]<=x){t1=k;ask_before(tr[k][],x);}

     else ask_before(tr[k][],x);

 }

 void ask_after(int k,int x)

 {

     if(k==)return;

     if(num[k]>=x){t2=k;ask_after(tr[k][],x);}

     else ask_after(tr[k][],x);

 }

 int main()

 {

     scanf("%d",&n);

     int f,x;

     for(int i=;i<=n;i++)

     {

         scanf("%d%d",&f,&x);

         if(!rt){kind=f;ins(rt,x,);}

         else if(kind==f){ins(rt,x,);}

         else

         {

             t1=t2=-;

             ask_before(rt,x);ask_after(rt,x);

             if(t1==-){ans+=num[t2]-x;ans%=;del(t2);}

             else if(t2==-){ans+=x-num[t1];ans%=;del(t1);}

             else

             {

                 if(x-num[t1]>num[t2]-x)  {ans+=num[t2]-x;ans%=;del(t2);}

                 else{ans+=x-num[t1];ans%=;del(t1);}

             }

         }

     }

     cout<<ans<<endl;

     return ;

 }

　　2.codevs1296 营业额统计

　　和前面一题类似，操作基本一样。

　　找出前驱后继，比较它们和当天营业额的差值，取小的那个给答案加上，完美。。

　　PS:前驱和后继初值赋值为正无穷或负无穷，以免找不到前驱/后继而成为 abs（0-当天营业额），影响答案取值。

CODE:

 #include<bits/stdc++.h>

 #define N 32769

 using namespace std;

 int c[N][],val[N],fa[N],tot,ans,n,rt,a,t1,t2;

 int read(){

     char c;int f=,x=;c=getchar();

     while(c>''||c<''){if(c=='-')f=-;c=getchar();}

     while(c<=''&&c>='')x=x*+c-'',c=getchar();

     return f*x;

 }

 void rotate(int x,int &k){

     int y=fa[x],z=fa[y],l,r;

     if(c[y][]==x)l=;else l=;r=l^;

     if(y==k)k=x;

     else c[z][c[z][]==y]=x;

     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

     c[y][l]=c[x][r];c[x][r]=y;

 }

 void splay(int x,int &k){

     while(x!=k){

         int y=fa[x],z=fa[y];

         if(y!=k){

             if((c[y][]==x)^(c[z][]==y))rotate(x,k);

             else rotate(y,k);

         }

         rotate(x,k);

     }

 }

 void insert(int x){

     if(!rt){

         rt=++tot;

         val[tot]=a;

         return;

     }

     int p=rt,z;

     while(p){

         z=p;

         if(a>=val[p])p=c[p][];

         else p=c[p][];

     }

     if(a>=val[z])c[z][]=++tot;

     else c[z][]=++tot;

     val[tot]=a;fa[tot]=z;

     splay(tot,rt);

 }

 void ask_before(int x){

     if(x==)return;

     if(val[x]==a){t1=a;return;}

     if(a>val[x]){t1=val[x];ask_before(c[x][]);}

     else ask_before(c[x][]);

 }

 void ask_after(int x){

     if(x==)return;

     if(val[x]==a){t2=a;return;}

     if(a<val[x]){t2=val[x];ask_after(c[x][]);}

     else ask_after(c[x][]);

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         a=read();

         t1=t2=;

         ask_before(rt);ask_after(rt);

         if(i==)ans+=a;

         else ans+=min(abs(t1-a),abs(t2-a));

         insert(rt);

     }

     printf("%d",ans);

     return ;

 }

　　3.codevs1286 NOI2004郁闷的营销员

　　大致思路：伸展树基本操作+巧妙的整体修改

　　原本以为使用区间操作，但发现可以把原有人的工资增减变为所有人（包括增减工资后加的人）的增减。只用记录一个all ，然后插入新成员时减去all的值就行。

　　PS:关于下面那个splay操作，其实是可有可无的，只是优化了时间而已。若是懒，可以不打splay和rotate，BZOJ时间限制5s，一样可以水过，但codevs时间限制1s，要TLE几组

　　至于splay优化时间的原因：如果构成了一条长链（超级长，可近似看做一个O(n)的序列），通过splay可以把它的深度减小，变为一棵二叉树

CODE:

 #include<bits/stdc++.h>

 #define N 32769

 using namespace std;

 int c[N][],val[N],fa[N],tot,ans,n,rt,a,t1,t2;

 int read(){

     char c;int f=,x=;c=getchar();

     while(c>''||c<''){if(c=='-')f=-;c=getchar();}

     while(c<=''&&c>='')x=x*+c-'',c=getchar();

     return f*x;

 }

 void rotate(int x,int &k){

     int y=fa[x],z=fa[y],l,r;

     if(c[y][]==x)l=;else l=;r=l^;

     if(y==k)k=x;

     else c[z][c[z][]==y]=x;

     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

     c[y][l]=c[x][r];c[x][r]=y;

 }

 void splay(int x,int &k){

     while(x!=k){

         int y=fa[x],z=fa[y];

         if(y!=k){

             if((c[y][]==x)^(c[z][]==y))rotate(x,k);

             else rotate(y,k);

         }

         rotate(x,k);

     }

 }

 void insert(int x){

     if(!rt){

         rt=++tot;

         val[tot]=a;

         return;

     }

     int p=rt,z;

     while(p){

         z=p;

         if(a>=val[p])p=c[p][];

         else p=c[p][];

     }

     if(a>=val[z])c[z][]=++tot;

     else c[z][]=++tot;

     val[tot]=a;fa[tot]=z;

     splay(tot,rt);

 }

 void ask_before(int x){

     if(x==)return;

     if(val[x]==a){t1=a;return;}

     if(a>val[x]){t1=val[x];ask_before(c[x][]);}

     else ask_before(c[x][]);

 }

 void ask_after(int x){

     if(x==)return;

     if(val[x]==a){t2=a;return;}

     if(a<val[x]){t2=val[x];ask_after(c[x][]);}

     else ask_after(c[x][]);

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         a=read();

         t1=t2=;

         ask_before(rt);ask_after(rt);

         if(i==)ans+=a;

         else ans+=min(abs(t1-a),abs(t2-a));

         insert(rt);

     }

     printf("%d",ans);

     return ;

 }

　　4.codevs3303 翻转区间

　　就是一个模板题啊，多次翻转区间，加上lazy标记就好

CODE:

 #include<bits/stdc++.h>

 #define N 100005

 using namespace std;

 int c[N][],fa[N],a[N],size[N],rev[N],rt,n,m;

 int read(){

     char c;int f=,x=;c=getchar();

     while(c>''||c<''){if(c=='-')f=-;c=getchar();}

     while(c<=''&&c>='')x=x*+c-'',c=getchar();

     return f*x;

 }

 void update(int x){

     int l=c[x][],r=c[x][];

     size[x]=size[l]+size[r]+;

 }

 void pushdown(int x){

     if(rev[x]){

         swap(c[x][],c[x][]);rev[x]=;

         rev[c[x][]]^=;rev[c[x][]]^=;

     }

 }

 void rotate(int x,int &k){

     int y=fa[x],z=fa[y],l,r;

     if(c[y][]==x)l=;else l=;r=l^;

     if(y==k)k=x;

     else c[z][c[z][]==y]=x;

     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

     c[y][l]=c[x][r];c[x][r]=y;

     update(y);update(x);

 }

 void splay(int x,int &k){

     while(x!=k){

         int y=fa[x],z=fa[y];

         if(y!=k){

             if(c[y][]==x^c[z][]==y)rotate(x,k);

             else rotate(y,k);

         }

         rotate(x,k);

     }

 }

 void build(int l,int r,int f){

     if(l>r)return;

     if(l==r){

         size[l]=;fa[l]=f;

         if(l>f)c[f][]=l;

         else c[f][]=l;

         return;

     }

     int mid=(l+r)>>;

     build(l,mid-,mid);build(mid+,r,mid);

     update(mid);fa[mid]=f;c[f][mid>f]=mid;

 }

 int find(int x,int k){

     pushdown(x);

     int l=c[x][],r=c[x][];

     if(size[l]+==k)return x;

     if(size[l]+>k)return find(l,k);

     return find(r,k--size[l]);

 }

 int main(){

     n=read();m=read();

     for(int i=;i<=n+;i++)a[i]=i;

     build(,n+,);rt=(+n)>>;

     int x,y;

     for(int i=;i<=m;i++){

         x=read(),y=read();

         int l=find(rt,x),r=find(rt,y+);

         splay(l,rt);splay(r,c[l][]);

         rev[c[r][]]^=;

     }

     for(int i=;i<=n+;i++)

     printf("%d ",find(rt,i)-);

     return ;

 }

　　5.NOI2005　维修数列

　　就是那道恶心的题，今天磨了好久，终于自己打出来了，代码就不贴了，恶心恶心。。

　　在晚上8:30时，教练硬是把我们拖出去讲了manacher，很简单。。。30min讲完大家都懂了，代码超级短，也是不想多说什么。

　　愉快的一天终于结束了，基本掌握伸展树，可以的，回去写英语阅读了！　　

巴特西

【集训第三天·疯狂训练】哦，顺带学习了manacher

最新文章

热门文章