题解：P6339 [COCI 2007/2008 #2] TURBO

· · 题解

题目传送门

思路与算法：

线段树。

先观察，发现一个数在执行完它的排序步骤后不会对接下来的排序产生影响，由于题目需要分大于等于 \frac{n+1}{2} 下取整的值和大于这个值两种，所以线段树的 sum 要有两个，一个是把这个数从当前位置向前移到指定位置所需步数，另一个则是向后移动到指定位置所需的步数。

线段树定义与建树：


struct xds{
    int l;
    int r;
    int sum1,sum2;//两个方向到指定位置的步数 
    int add1,add2;//同理，有两个sum当然就需要两个懒标记 
    void oin1(int a,int b){
        l=a;
        r=b;
        add1=add2=0;
    }
    void oin2(int c){
        sum1=(c-1);
        sum2=(x-c);
        //初始化输入时的位置 
    }

}tre[500005];//线段树 

void js(int q,int l,int r){
    tre[q].oin1(l,r);
    if(l==r) {
        tre[q].oin2(l);
        return ;
    }
    int mid=l+r>>1;
    js(q*2,l,mid);
    js(q*2+1,mid+1,r);
}//建树，与模板基本无异

接下来处理区间加法，显然的，在一个数向前移动以实现排序时，会对这个数位置后面的所有数的 sum_2 产生 -1 的贡献，对这个数前面的所有数的 sum_1 产生 -1 的贡献，这个很显然，不懂的画个图模拟一下样例即可。

区间加：

void qjjf(int q,int ml,int mr,int k,int t){
    if(ml<=zqj&&mr>=yqj){
        if(t==1){
            tre[q].sum1+=((yqj-zqj+1)*k);
            tre[q].add1+=k;
        }
        else{
            tre[q].sum2+=((yqj-zqj+1)*k);
            tre[q].add2+=k;
        }
        //分辨对sum1操作还是对sum2操作 
        return ;
    }
    pushdown(q);
    int mid=(zqj+yqj)/2;
    if(ml<=mid) qjjf(left,ml,mr,k,t);
    if(mr>mid) qjjf(right,ml,mr,k,t);
}

最后是单点查询，很简单，与模板无异：

int qjqh(int q,int mb,int dc){
    if(zqj==mb&&yqj==mb){
        if(dc<=(x+1)/2) return tre[q].sum1;//判断这个数是向前移还是向后移的 
        else return tre[q].sum2;
    }
    pushdown(q);
    int mid=(zqj+yqj)/2;
    if(mb<=mid) return qjqh(left,mb,dc);
    if(mb>mid) return qjqh(right,mb,dc); 
}

一点细节：

  1. 在输出距离时与 0 取大值，防止输出负数。
  2. pushdown 要同时处理两个 sum 的值。
  3. 对位置不要直接写成输入时的值了，记得映射一个位置。
  4. 本题不用处理区间和，不用写 pushup。

完整代码：

#include <bits/stdc++.h>
using namespace std;

#define left q*2
#define right q*2+1
#define zqj tre[q].l
#define yqj tre[q].r

int x;
int m[100005];

int wz[100005];

struct xds{
    int l;
    int r;
    int sum1,sum2;//两个方向到指定位置的步数 
    int add1,add2;//同理，有两个sum当然就需要两个懒标记 
    void oin1(int a,int b){
        l=a;
        r=b;
        add1=add2=0;
    }
    void oin2(int c){
        sum1=(c-1);
        sum2=(x-c);
        //初始化输入时的位置 
    }

}tre[500005];//线段树 

void pushdown(int q){
    if(tre[q].add1!=0){
        tre[q*2].sum1+=((tre[q*2].r-tre[q*2].l+1)*tre[q].add1);
        tre[q*2].add1+=tre[q].add1;
        tre[q*2+1].sum1+=((tre[q*2+1].r-tre[q*2+1].l+1)*tre[q].add1);
        tre[q*2+1].add1+=tre[q].add1;
    }
    if(tre[q].add2!=0){
        tre[q*2].sum2+=((tre[q*2].r-tre[q*2].l+1)*tre[q].add2);
        tre[q*2].add2+=tre[q].add2;
        tre[q*2+1].sum2+=((tre[q*2+1].r-tre[q*2+1].l+1)*tre[q].add2);
        tre[q*2+1].add2+=tre[q].add2;
    }
    tre[q].add1=tre[q].add2=0;
}

void js(int q,int l,int r){
    tre[q].oin1(l,r);
    if(l==r) {
        tre[q].oin2(l);
        return ;
    }
    int mid=l+r>>1;
    js(q*2,l,mid);
    js(q*2+1,mid+1,r);
}//建树，与模板基本无异 
void qjjf(int q,int ml,int mr,int k,int t){
    if(ml<=zqj&&mr>=yqj){
        if(t==1){
            tre[q].sum1+=((yqj-zqj+1)*k);
            tre[q].add1+=k;
        }
        else{
            tre[q].sum2+=((yqj-zqj+1)*k);
            tre[q].add2+=k;
        }
        //分辨对sum1操作还是对sum2操作 
        return ;
    }
    pushdown(q);
    int mid=(zqj+yqj)/2;
    if(ml<=mid) qjjf(left,ml,mr,k,t);
    if(mr>mid) qjjf(right,ml,mr,k,t);
}

int qjqh(int q,int mb,int dc){
    if(zqj==mb&&yqj==mb){
        if(dc<=(x+1)/2) return tre[q].sum1;//判断这个数是向前移还是向后移的 
        else return tre[q].sum2;
    }
    pushdown(q);
    int mid=(zqj+yqj)/2;
    if(mb<=mid) return qjqh(left,mb,dc);
    if(mb>mid) return qjqh(right,mb,dc); 
}

signed main(){
    cin>>x;
    for(int i=1;i<=x;i++){
        cin>>m[i];
        wz[m[i]]=i;//映射位置 
    }
    js(1,1,x);
    int s=0;
    int mq1=0,mq2=x+1;
    while(1){
        if(s==x) break;
        if(s%2==0){
            mq1++;
            cout<<max(0,qjqh(1,wz[mq1]/*不要写成m[mq1]，下同*/,mq1))<<endl;
            if(wz[mq1]!=x) qjjf(1,wz[mq1]+1,x,-1,1);//对后面数的sum1产生贡献 
            if(wz[mq1]!=1) qjjf(1,1,wz[mq1]-1,-1,2);//对前面数的sum2产生贡献 
            s++;
        } 
        else{
            mq2--;
            cout<<max(0,qjqh(1,wz[mq2],mq2))<<endl;
            if(wz[mq2]!=1) qjjf(1,1,wz[mq2]-1,-1,2);//对前面数的sum2产生贡献 
            if(wz[mq2]!=x) qjjf(1,wz[mq2]+1,x,-1,1);//对后面数的sum1产生贡献 
            s++;
        }
    }
    return 0; 
}