问题描述：在如下的函数体中添加内容，使S(l,r)给a[]中的l到r位置进行排序。

void S(int l,int r){}

一开始我觉得选择排序已经够短了。就像这样：

void S(int l,int r){for(int i=l;i<r;i++)for(int j=i+1;j<=r;j++)if(a[i]>a[j])swap(a[i],a[j]);}

这样一共只用了93B，好像已经不能再优化了（可能再卡一卡还是能略微小一些的，但是大的优化是不多了）。

后来我有了一个诡异的想法，可以巧妙地利用递归：

void S(int l,int r){if(r==l+1){if(a[l]>a[r])swap(a[l],a[r]);}else if(r>l+1)S(l,r-1),S(l+1,r),S(l,r-1);}

这是什么原理呢。。。大家一看就明白了吧。如果序列长度小于2，我们直接不管它。如果长度就是2，我们比较a[l]和a[r]。如果长度大于2，我们进行一个递归。首先，递归排序S(l,r-1)，目的是让最大值不出现在第一个位置。其次，递归排序S(l+1,r)，把最大值放到最后一个位置。这样，a[l]到a[r-1]就只有第l到第r-1的数了。最后，再调用一次S(l,r-1)，完成排序。当然，不要在意它的时间复杂度。（逃

可是这样反而变长了啊。。。那我们再优化一下：

void S(int l,int r){if(a[l]>a[r])swap(a[l],a[r]);if(r>l)S(l,r-1),S(l+1,r);}

我们把r==l+1的条件去掉了。这样省掉了一个if和一个else。同时，由于这样的比较已经保证了a[r]不可能是最小值，第一次递归过后最小值一定在a[l]，于是第三次递归也就不需要了。此外，r>l+1的条件也可以换成r>l，没有什么影响。

这份代码只有75B，完虐选择排序。同时，时间复杂度由$O(3^n)$优化到了$O(2^n)$。

这个问题是不是已经有人研究过了啊？如果大家有想法的话也可以和我交流。以及，有没有人会一个比选择排序更短的多项式算法啊。。。

UPD：现在最短的代码74B：

void S(int l,int r){swap(a[a[l]>a[r]?l:r],a[r]);if(r>l)S(l,r-1),S(l+1,r);}

以及，用指针继续缩短到68B：

void S(int*l,int*r){swap(*(*l>*r?l:r),*r);if(r>l)S(l,r-1),S(l+1,r);}

感谢大家的回复！

写在前面

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dwn(i,a,b) for(int i=a;i>=b;i--)
#define gma(x,y) x=max(x,y)
#define gmi(x,y) x=min(x,y)
using namespace std;
int main(){
    return 0;
}

邻接表

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v;
    node *next;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v){
    node *o=&pool[cnt++];
    o->v=v,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->next=h[v],h[v]=o;
}

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v,d;
    node *next;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v,int d){
    node *o=&pool[cnt++];
    o->v=v,o->d=d,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->d=d,o->next=h[v],h[v]=o;
}

树状数组

struct FenwickTree{
    int p[MAXN];
    void Add(int id,int x){
        while(id<=n)p[id]+=x,id+=id&(-id);
    }
    int Query(int id){
        int s=0;
        while(id)s+=p[id],id-=id&(-id);
        return s;
    }
};

网络流

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v,d;
    node *next,*rev;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v,int d){
    node *o=&pool[cnt++];
    o->v=v,o->d=d,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->d=0,o->next=h[v],h[v]=o;
    h[u]->rev=h[v],h[v]->rev=h[u];
}

并查集

struct UFS{
    int p[MAXN];
    UFS(){memset(p,-1,sizeof(p));}
    void clear(){memset(p,-1,sizeof(p));}
    inline bool Union(int x,int y){x=Find(x),y=Find(y);if(x!=y){p[x]=y;return 1;}return 0;}
    int Find(int x){if(p[x]<0)return x;return p[x]=Find(p[x]);}
};

读入优化（int）

int _(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

读入优化（long long）

long long _(){
    long long x=0;
    int f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

输出优化

void __(ll x){
    if(!x){puts("0");return;}
    char c[30]={};
    int i=0;
    while(x)c[i++]=x%10+'0',x/=10;
    while(i)putchar(c[--i]);
    puts("");
}

线性筛

namespace Mobius{
    int n,t,miu[MAXN],phi[MAXN],pri[MAXN],cnt,d[MAXN];
    void Init(){
        miu[1]=1;
        phi[1]=1;
        for(int i=2;i<=n;i++){
            if(!d[i])pri[++cnt]=i,d[i]=cnt,miu[i]=-1,phi[i]=i-1;
            for(int j=1;i*pri[j]<=n&&j<=d[i];j++){
                t=i*pri[j];
                d[t]=j;
                miu[t]=j<d[i]?-miu[i]:0;
                phi[t]=j<d[i]?phi[i]*(pri[j]-1):phi[i]*pri[j];
            }
        }
    }
}

倍增LCA

#define enu() for(node *o=h[u];o;o=o->next)if(o->v!=pnt[u])

namespace LCA{
    const int LOG=17,MAXL=20;
    int lpnt[MAXN][MAXL];
    void work(int u,int lev){
        if(lpnt[u][lev])lpnt[u][lev+1]=lpnt[lpnt[u][lev]][lev];
        enu()work(o->v,lev);
    }
    int LCA(int u,int v){
        if(dep[u]<dep[v])swap(u,v);
        dwn(i,LOG,0)if(lpnt[u][i]&&dep[lpnt[u][i]]>=dep[v])u=lpnt[u][i];
        dwn(i,LOG,0)if(lpnt[u][i]!=lpnt[v][i])u=lpnt[u][i],v=lpnt[v][i];
        if(u==v)return u;return pnt[u];
    }
    void Init(){rep(i,1,n)lpnt[i][0]=pnt[i];rep(i,0,LOG)work(1,i);}
}

ST表LCA

namespace LCA{
    const int LOG=22,MAXL=25;
    int ST[MAXL][2*MAXN],pos[MAXL][2*MAXN],num[MAXN],pnt[MAXN],Log[2*MAXN],Depth[MAXN];
    int dfn;
    void dfs0(int u,int dep){
        num[u]=++dfn,Depth[u]=dep,pos[0][dfn]=u;
        ST[0][dfn]=dep;
        for(node *o=h[u];o;o=o->next)if(o->v!=pnt[u]){
            pnt[o->v]=u;
            dfs0(o->v,dep+1);
            ST[0][++dfn]=dep,pos[0][dfn]=u;
        }
    }
    void Init(){
        for(int i=0;i<=LOG;i++)for(int j=1;j<=2*n;j++)ST[i][j]=0;
        dfn=pnt[1]=0;
        dfs0(1,1);
        for(int i=0;i<=20&&(1<<i)<=dfn;i++)
            for(int j=(1<<i);j<(1<<i+1)&&j<=dfn;j++)Log[j]=i;
        for(int i=1;i<=20;i++)
            for(int j=1;j+(1<<i)<=dfn+1;j++){
                if(ST[i-1][j]<ST[i-1][j+(1<<i-1)])ST[i][j]=ST[i-1][j],pos[i][j]=pos[i-1][j];
                else ST[i][j]=ST[i-1][j+(1<<i-1)],pos[i][j]=pos[i-1][j+(1<<i-1)];
            }
    }
    int LCA(int u,int v){
        if(u==v)return u;
        int x=num[u],y=num[v];
        if(x>y)swap(x,y);
        y++;
        int t=Log[y-x];
        if(ST[t][x]<ST[t][y-(1<<t)])return pos[t][x];else return pos[t][y-(1<<t)];
    }
}

当你在上面跑费用流的时候。

今天（4月16日）总算到了BJ省选day1的日子啦，一大早起来去北WA路考试。到了以后晃了两圈按照要求在机器上装了个Dev-C++5.11就没有事做，过了一会看到别人已经在看PDF了，这才发现考试开始了。。。

第一题。makina？一看这出题人就是个死宅。题目背景好几页，读了五分钟看不懂，果断弃。第二题描述很简练。树分治？想了那么三分钟觉得挺可做的，就去看第三题。第三题是个字符串题，没怎么想，推了推第二题，就开始写，觉得几个数组推一推就搞定了。这时已经八点二十了。问了一下栈的大小，结果两个监考员嘀咕了半天，告诉我在Windows下用cena评测。算了不耽误时间了，BFS保平安吧。

T2写了一会发现分治后数组上扫好像不那么显然，可能要一个set。马上又发现智障了，复杂度还不对，应该是线段树。20w，2s，不开O2，$log^2 n$，线段树？看来要被卡常卡掉几个点了。犹豫了一会，开始写。各种困，各种不想写。

写完了开始编译。max undefined？5.11的锅吧，自己写了一个。queue undefined？什么鬼啊。sort也undefined？总算发现using namespace std;没开，智障。。。十点刚过的时候T2过了样例，敲了个对拍和datamaker。小数据都顺利地过了。测了个20w，发现树分治跑了2s多。又测了一组链的情况，卧槽，22s！这就肯定不是常数问题了，一定是复杂度出了锅。然后各种调试，各种计数器。。。程序还TM跑的那么慢。。。中间等对拍跑的时候看了看第三题，发现前六十分就是裸的AC自动机，很好拿。十点五十的时候我想要是到了十一点T2还没有进展就果断弃聊，先干掉AC自动机。

终于到了十点五十七分，我发现了线段树的Change和Query居然一共调用了60多亿次！计数器都爆int了，开了long long才记下来。线段树还能错？我盯着哪个Query检查。if(left==right)return o->d;？？？就是说Query的时候一定会递归到底。MDZZ，赶紧改过来。又跑了一组数据。WA了？原来Change也错了，改过来，测了一下极限数据，跑了2.4s，凑活了吧，就当会T两个点。

这时十一点一刻。花了二十分钟把AC自动机写出来，测了测过了样例，应该能有60分。后40分是矩阵快速幂？这跟去年的打字机有什么区别啊，出题人也太省事了吧。后面有20还挺水的，马上开始矩阵快速幂。很快写出来了，结果快速幂部分莫名RE。怎么改也不对，把结构体名字从matrix改成Matrix也没用。最可气的是就算把文件输入输出全注释掉，改成屏幕读写，一运行，直接就RE，连数据都还没有输入。。。在RE的地方前面加个while(1);就好了，莫名其妙。。。折腾来折腾去也没有结果。

过了一会已经十二点半了，想着今天题这么水应该有好多上200的吧。看来要滚粗了。十二点三十四分的时候弃疗，去写T1的30分特大暴力。这时周围的键盘声已经没有那样密集了，很多人已经开始扫雷了。使劲码，WA了几次，到十二点五十几的时候总算过了样例。然后迅速看了看文件名，输入输出，把代码复制进提交文件夹里。看了看表，十二点五十九分零四秒！然后在草稿纸上写下大大的GG，瘫倒在座位上。

预估30+80+60=170

吃饭时moorhsum说他炸了。他跟QHF（初中母校）的wys（和某位大神的姓名缩写重名的另一位大神）互相赌20块钱谁考得低。。。

吃完饭在操场上转了一圈，觉得最放不下心的是AC自动机没对拍。想想也没有关系，今年滚粗了就好好学课内，明年再来。。。

过了好久总算测完了，居然是25+90+60=175，T1暴力有一个地方把n写成m了，WA了5分（居然只少了5分），T2只T了一个点。hld67890好强啊，220rank3。上200的人其实只有4个，看来BJ变得比去年弱了。

正解T1管道取珠，$n^4$的DP。T2单调队列，T3就是快速幂。还是太弱了，T1T2正解都想不出来。

今天还算不错吧，并列rank7，争取下周好好考，进BJ队还是有那么一点点希望的。