[关闭]
@jesseliu612 2017-02-27T21:32:46.000000Z 字数 38328 阅读 2669

2017寒假学习总结

学习总结 CJOI 2017 长郡中学刘俊琦

目录

52题计划

关于52题计划

52题计划是一个致力于高效准确解题的训练计划，通过对多个知识点的综合训练来提升解题能力和一遍通过能力。

计划内容

将oi学习分为多个阶段，在每个阶段中完成至少52道具有代表性的、实现方式不重复的训练题，并将完成情况登记在本页面上。在训练过程中强化知识掌握，提高审题能力和代码能力。
在本阶段，52题计划的主要方向为：高级数据结构的应用、数学专题、具有思维难度的动态规划及其dp优化、贪心思想的应用等。难度在省选以下，联赛以上。鉴于学习水平仍不够高，在实施过程中暂且允许查看题解，但在题目完成后必须独立完成解题报告，详细阐述算法思想、解题中遇到的问题和该解题思路的扩展应用。
本阶段时间：2017.1.20-2017.2.28

完成情况和解题报告链接

第一阶段

1.【52题计划】新春晚会（2-SAT）
2.【52题计划】网络攻击（校内）
3.【52题计划】线性模方程组的计算

新春欢乐赛系列：
Provider / Jesse Liu
4.【52题计划】天团 - 网络流
5.【52题计划】录音 - 条件概率
6.【52题计划】开场 - 二分dp优化
7.【52题计划】同学缘 - 数位计数问题
以上见【52题计划】2月4日欢乐赛题解
8.【52题计划】典礼 - 欧拉函数&莫比乌斯函数

9.【52题计划】小Z的袜子 - 莫队算法
10.【52题计划】Monkey King - 左偏树
11.【52题计划】球形空间产生器 - 高斯消元
12.【52题计划】区间k小数查询 - 主席树
13.【52题计划】SJY摆棋子 - KD树
14.【52题计划】[SCOI2005]王室联邦
15.【52题计划】Count on a tree II - 未AC
16.【52题计划】XOR和路径 - 高斯消元 - 校内

数论

数论初步

欧几里得算法

  1. int gcd(int a,int b){
  2.     return b==0?a:gcd(b,a%b);
  3. }

扩展欧几里得算法

  1. void gcd(int a,int b,int d,int x,int y){
  2.     if(!b){ d=a;x=1;y=0; }
  3.     else{ gcd(b,a%b,d,y,x); y-=x*(a/b); }
  4. }

唯一分解定理

每一个数都可以唯一分解成若干个质数相乘的形式，可以用来避免高精度运算。

素数筛法

Eratosthenes筛法

  1. int m=sqrt(n+0.5);
  2. memset(vis,0,sizeof(vis));
  3. for(int i=2;i<=m;i++)if(!vis[i])
  4.     for(int j=i*i;j<=n;j+=i) vis[j]=1;

线性筛（包含求莫比乌斯函数）

  1. void sieve(){
  2.     mu[1]=1;sigma[1]=1;
  3.     for(int i=2;i<maxn;i++){
  4.         if(!vis[i]){ mu[i]=-1;prime[++pnt]=i; }
  5.         for(int j=1;j<=pnt && i*prime[j]<maxn;j++){
  6.             vis[i*prime[j]]=true;
  7.             if(i%prime[j]==0){
  8.                 mu[i*prime[j]]=0;
  9.                 break;
  10.             }
  11.            else{
  12.                 mu[i*prime[j]]=-mu[i];
  13.             }
  14.         }
  15.         sigma[i]=sigma[i-1]+mu[i];
  16.     }
  17. }

线性模方程组的解法

将模方程合并。
x%mo1=a1,x%mo2=a2 => x=k1*mo1+a1=k2*mo2+a2 （1）
=> mo1*k1-mo2*k2=a2-a1
=> gcd可以求出k1和k2
=> 代入（1）求出x的一个解，通解为x%(lcm(mo1,mo2))=k1*mo1+a1
至此，两个方程合并成了一个。
以此类推，可以求出所有方程合并之后的方程。最后计算那个方程的解的个数即可。

  1. int eqmo(){
  2.     int a1=a[1],mo1=mo[1];
  3.     for(int i=2;i<=m;i++){
  4.         int a2=a[i],mo2=mo[i];
  5.         int d,k1,k2;
  6.         gcd(mo1,mo2,d,k1,k2);
  7.         k1=k1*((a2-a1)/d);
  8.         if((a2-a1)%d!=0)return 0;
  9.         a1=(k1*mo1+a1)%((mo1/d)*mo2);
  10.         if(a1<0)a1+=(mo1/d)*mo2;
  11.         mo1=(mo1/d)*mo2;
  12.     }
  13.     int ret=n/mo1;
  14.     if(n%mo1>=a1)ret++;
  15.     if(a1==0 && ret!=0)--ret;
  16.     return ret;
  17. }

欧拉函数

欧拉函数指的是小于n且与n互质的整数个数。
对于质数x，。
一般地，


其中k为质因子个数。

离散概率

全概率公式

条件概率


递推

Catalan数


数学期望

期望的线性性

全期望公式

与全概率公式类似。

莫比乌斯函数

莫比乌斯函数是在卷积意义下的逆，即。
的值如下：
当时，。
若x的每个质因子有不止1个，。
否则：若x有奇数个质因子，，若x有偶数个质因子，。
根据莫比乌斯函数的定义，我们知道


详见校内题 - 典礼

图论

网络流

最大流的Dinic算法

通过构建层次网络，每次增广层次最少的增广路。

  1. int st[maxn],pt[maxm],nxt[maxm],flow[maxm],cap[maxm],d[maxn],q[maxm],ent=1;
  2. void adde(int u,int v,int fl){
  3.     pt[++ent]=v;nxt[ent]=st[u];st[u]=ent;flow[ent]=0;cap[ent]=fl;
  4.     pt[++ent]=u;nxt[ent]=st[v];st[v]=ent;flow[ent]=0;cap[ent]=0;
  5. }
  6. bool bfs(){
  7.     memset(d,-1,sizeof(d));
  8.     int hd=0,tl=0;
  9.     q[++tl]=s;d[s]=0;
  10.     while(hd<tl){
  11.         int r=q[++hd];
  12.         if(r==t)return true;
  13.         for(int i=st[r];i;i=nxt[i]){
  14.             if(flow[i]>=cap[i])continue;
  15.             if(d[pt[i]]!=-1)continue;
  16.             d[pt[i]]=d[r]+1;
  17.             q[++tl]=pt[i];
  18.         }
  19.     }
  20.     return false;
  21. }
  22. int dfs(int x,int a){
  23.     if(x==t || a==0)return a;
  24.     int f,fl=0,bef=a;
  25.     for(int i=st[x];i;i=nxt[i]){
  26.         if(flow[i]>=cap[i] || d[pt[i]]!=d[x]+1)continue;
  27.         if((f=dfs(pt[i],min(a,cap[i]-flow[i])))>0){
  28.             fl+=f;flow[i]+=f;flow[i^1]-=f;a-=f;
  29.             if(a==0)break;
  30.         }
  31.     }
  32.     if(bef==a)d[x]=-1; //非常有用的剪枝
  33.     return fl;
  34. }
  35. int dinic(){
  36.     int ret=0;
  37.     while(bfs()){
  38.         ret+=dfs(s,inf);
  39.     }
  40.     return ret;
  41. }

上述代码片段中，dinic的函数返回的是最大流。注意dfs函数中的剪枝，实测效果非常优秀，比当前弧优化更能够提高代码效率。该代码片段出于简便考虑，没有添加当前弧优化。

最小费用最大流的spfa算法

  1. int st[maxn],pt[maxm],nxt[maxm],flow[maxm],cap[maxm],cost[maxm],dis[maxn],fa[maxn],fae[maxn],q[maxm],ent=1;
  2. int m,n,s,t;
  3. int cst=0;
  4. char vis[maxn];
  5. void connect(int u,int v,int c,int mf){
  6.     pt[++ent]=v;nxt[ent]=st[u];st[u]=ent;flow[ent]=0;cap[ent]=mf;cost[ent]=-c;
  7.     pt[++ent]=u;nxt[ent]=st[v];st[v]=ent;flow[ent]=0;cap[ent]=0;cost[ent]=c;
  8. }
  9. bool spfa(){
  10.     memset(dis,127/3,sizeof(dis));
  11.     memset(vis,0,sizeof(vis));
  12.     int hd=0,tl=0;
  13.     q[++tl]=s;dis[s]=0;
  14.     while(hd<tl){
  15.         int r=q[++hd];
  16.         vis[r]=false;
  17.         for(int i=st[r];i;i=nxt[i]){
  18.             if(cap[i]>flow[i]){
  19.                 if(dis[pt[i]]>dis[r]+cost[i]){
  20.                     fa[pt[i]]=r;fae[pt[i]]=i;
  21.                     dis[pt[i]]=dis[r]+cost[i];
  22.                     if(!vis[pt[i]]){
  23.                         vis[pt[i]]=true;
  24.                         q[++tl]=pt[i];
  25.                     }
  26.                 }
  27.             }
  28.         }
  29.     }
  30.     if(dis[t]<707406378){
  31.         int u=t;
  32.         int minf=2147483640;
  33.         while(u!=s){
  34.             minf=min(minf,cap[fae[u]]-flow[fae[u]]);
  35.             u=fa[u];
  36.         }
  37.         u=t;
  38.         while(u!=s){
  39.             flow[fae[u]]+=minf;flow[fae[u]^1]-=minf;
  40.             u=fa[u];
  41.         }
  42.         cst+=minf*dis[t];
  43.         return true;
  44.     }
  45.     return false;
  46. }

上述代码片段的调用方法为

  1. cst=0;
  2. while(spfa());

执行完后，cst中存储的是答案。
如果确定每条弧的流量均为1，那么增广的时候可以省略掉获取当前增广流量的部分，以加速代码运行。

遇上splay的不同凡想

Splay（伸展树）是平衡二叉树的一种，以功能强大而代码简洁明了著称，被广泛应用于信息学竞赛中。它不仅可以高效实现二叉树的基本功能，还因其可以任意旋转的特点能够实现与数列有关的其他问题，在某些方面甚至可以替代线段树完成任务。因此，对于它的学习是很有必要的。

1. Splay的基本操作

1.1 建树

Splay的本质是一棵二叉搜索树，因此在建树的过程中要确保其左子树的结点均小于它，右子树的结点均大于它，重复的结点使用cnt来计数。建树的过程如下：

  1. int newnode(int v,int f){ //create a new splay node, retrun the number of it
  2.         ++ndcnt;
  3.         fa[ndcnt]=f;
  4.         val[ndcnt]=v;
  5.         return ndcnt;
  6. }
  7. int ins(ll v){ //insert a node to splay, need to use function "newnode"
  8.         //special judgement for an emply splay
  9.         if(fst) {
  10.                 val[root]=v;
  11.                 fst=0;
  12.                 size[root]=1; cnt[root]=1;
  13.                 return root;
  14.         }
  15.         int cur=root;
  16.         while (ch[cur][val[cur]<v]) {
  17.                 ++size[cur];
  18.                 //special judgement for repeated value
  19.                 if(val[cur]==v) {
  20.                         cnt[cur]++;
  21.                         splay(cur,0);
  22.                         return -1;
  23.                 }
  24.                 cur=ch[cur][val[cur]<v];
  25.         }
  26.         ++size[cur];
  27.         if(val[cur]==v) {
  28.                 cnt[cur]++;
  29.                 splay(cur,0);
  30.                 return -1;
  31.         }
  32.         ch[cur][val[cur]<v]=newnode(v,cur);
  33.         cur=ch[cur][val[cur]<v];
  34.         ++size[cur];
  35.         ++cnt[cur];
  36.         splay(cur,0);
  37.         return cur;
  38. }

比较麻烦的是fst和对于重复结点的特判，要记得每次都要特判一下。fst代表splay为空，因为不方便真的把0号节点建出来，所以也是特判处理第一个节点的。

1.2 旋转

Splay的主要操作是把某一个节点旋转到任意一个其上方其他节点的儿子处，一般只需要旋转到根或者第二层（方便区间提取等），所以不需要考虑往下移动。旋转的实质是不断将节点和它父亲节点互换位置，根据二叉树的基本性质来重新分配儿子，达到提高某节点位置的目的。
具体的旋转操作分为单旋（只用于转奇数次的最后一次）、双旋（一次把它的父亲和它同时处理，分为一字形和之字形。一字形是先把父亲和祖父交换，再把它和父亲交换；之字形只能连续把自己和父亲交换两次。想想为什么？）。之所以要用到双旋，是为了降低树的深度，提高算法效率。
对于将某节点和它父亲节点交换的操作，可以写二合一的函数（适用于左儿子和右儿子两种情况）。具体的操作步骤还是要自己推导一下，注意同步更新size和fa。

  1. //rot and splay are the basic functions of splay tree
  2. void rot(int cur,int op){      //if cur is the left child of its father, let op = 0. Otherwise, let op = 1;
  3.         int y=fa[cur];
  4.         if(ch[y][op]!=0) {ch[y][op]=ch[cur][!op]; fa[ch[y][op]]=y; }
  5.         ch[fa[y]][ch[fa[y]][15]==y]=cur;
  6.         fa[cur]=fa[y];
  7.         ch[cur][!op]=y; fa[y]=cur;
  8.         size[y]=size[ch[y][0]]+size[ch[y][16]]+cnt[y];
  9.         size[cur]=size[ch[cur][0]]+size[ch[cur][17]]+cnt[cur];
  10. }
  11. void splay(int cur,int goal){      //goal is the father of cur when finished
  12.         while(fa[cur]!=goal) {
  13.                 if(fa[fa[cur]]==goal) {
  14.                         rot(cur,ch[fa[cur]][0]!=cur);
  15.                 }
  16.                 else{
  17.                         int fad=(ch[fa[fa[cur]]][0]!=fa[cur]);
  18.                         int sond=(ch[fa[cur]][0]!=cur);
  19.                         if(fad==sond) {
  20.                                 rot(fa[cur],fad);
  21.                                 rot(cur,sond);
  22.                         }
  23.                         else{
  24.                                 rot(cur,sond);
  25.                                 rot(cur,fad);
  26.                         }
  27.                 }
  28.         }
  29.         if(goal==0) root=cur;
  30. }

2. Splay的应用

2.1 基本二叉树应用

由于Splay可以不断旋转改变树的形态，对于搜索二叉树的题目可以使用Splay把复杂度稳定在O(nlogn），避免树退化。每次查询完后就把查询到的节点旋转到根，这样就可以让树的形态不断改变，使查询的均摊复杂度降低。

例题

T1296（codevs）:

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

该天的最小波动值 = min{|该天以前某一天的营业额-该天营业额|}

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。

第一天的最小波动值为第一天的营业额。

解析
这道题有两种解法，一种是用线段树维护最大最小值，然后查询；另一种是使用Splay，每次将要查询的节点旋转到根，然后先向左再一直向右，先向右再一直向左来得到结果。注意查询的时候要优化写法，否则常数会太大。
具体代码实现：

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <vector>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. using namespace std;
  13. const int inf = 2147483640;
  14. const int maxn = 32767 + 100;
  15. typedef long long ll;
  16. ll geti(){
  17.         char ch=getchar(); while((ch<'0' || ch>'9')&&ch!='-') ch=getchar();
  18.         ll ret=0,k=1;
  19.         if(ch=='-') k=-1,ch=getchar();
  20.         while(ch>='0' && ch<='9') ret=ret*10+ch-'0',ch=getchar();
  21.         return ret*k;
  22. }
  23. struct Splay {
  24.         int fa[maxn],ch[maxn][18],val[maxn],root,fst,ndcnt;
  25.         Splay(){
  26.                 memset(fa,0,sizeof(fa));
  27.                 memset(ch,0,sizeof(ch));
  28.                 memset(val,0,sizeof(val));
  29.                 root=1; fa[root]=0; fst=1; ndcnt=1;
  30.         }
  31.         int newnode(int v,int f){
  32.                 ++ndcnt;
  33.                 fa[ndcnt]=f;
  34.                 val[ndcnt]=v;
  35.                 return ndcnt;
  36.         }
  37.         int ins(int v){
  38.                 if(fst) {
  39.                         val[root]=v;
  40.                         fst=0;
  41.                         return root;
  42.                 }
  43.                 int cur=root;
  44.                 while (ch[cur][val[cur]<v]) {
  45.                         if(val[cur]==v) {
  46.                                 ctg(cur,0);
  47.                                 return -1;
  48.                         }
  49.                         cur=ch[cur][val[cur]<v];
  50.                 }
  51.                 ch[cur][val[cur]<v]=newnode(v,cur);
  52.                 cur=ch[cur][val[cur]<v];
  53.                 ctg(cur,0);
  54.                 return cur;
  55.         }
  56.         void rot(int cur,int op){ //if cur is the left child of its father, let op = 0. Otherwise, let op = 1;
  57.                 int y=fa[cur];
  58.                 if(ch[y][op]!=0) {ch[y][op]=ch[cur][!op]; fa[ch[y][op]]=y; }
  59.                 ch[fa[y]][ch[fa[y]][19]==y]=cur;
  60.                 fa[cur]=fa[y];
  61.                 ch[cur][!op]=y; fa[y]=cur;
  62.         }
  63.         void ctg(int cur,int goal){ //goal is the father of cur when finished
  64.                 while(fa[cur]!=goal) {
  65.                         if(fa[fa[cur]]==goal) {
  66.                                 rot(cur,ch[fa[cur]][0]!=cur);
  67.                         }
  68.                         else{
  69.                                 int fad=(ch[fa[fa[cur]]][0]!=fa[cur]);
  70.                                 int sond=(ch[fa[cur]][0]!=cur);
  71.                                 if(fad==sond) {
  72.                                         rot(fa[cur],fad);
  73.                                         rot(cur,sond);
  74.                                 }
  75.                                 else{
  76.                                         rot(cur,sond);
  77.                                         rot(cur,fad);
  78.                                 }
  79.                         }
  80.                 }
  81.                 if(goal==0) root=cur;
  82.         }
  83.         int get_pre() {
  84.                 int tmp=ch[root][0];
  85.                 if (tmp==0) return 2147483640;
  86.                 while (ch[tmp][20]) tmp=ch[tmp][21];
  87.                 return val[tmp];
  88.         }
  89.         int get_next() {
  90.                 int tmp=ch[root][22];
  91.                 if (tmp==0) return 2147483640;
  92.                 while (ch[tmp][0]) tmp=ch[tmp][0];
  93.                 return val[tmp];
  94.         }
  95.         int query(int obj){
  96.                 ctg(obj,0);
  97.                 int a=get_pre(); int b=get_next();
  98.                 return min(abs(a-val[root]),abs(val[root]-b));
  99.         }
  100.         void debug(int pw){
  101.                 if(pw==1024) {
  102.                         for(int i=1; i<=ndcnt; i++) {
  103.                                 printf("node %d : %d %d %d lft = %d , rgt = %d\n",i,val[ch[i][0]],val[i],val[ch[i][23]],ch[i][0],ch[i][24]);
  104.                         }
  105.                 }
  106.         }
  107. } T;
  108. int n;
  109. int main(){
  110.         n=geti();
  111.         ll ans=0; int rd,ret1,ret2;
  112.         for(int i=1; i<=n; i++) {
  113.                 rd=geti();
  114.                 ret1=T.ins(rd);
  115.                 if(ret1==-1) {
  116.                         continue;
  117.                 }
  118.                 ret2=T.query(ret1);
  119.                 if(i!=1) ans+=ret2;
  120.                 else ans+=rd;
  121.         }
  122.         printf("%lld",ans);
  124.         fclose(stdin);
  125.         fclose(stdout);
  126.         return 0;
  127. }
  128. //73ms

2.2 Splay维护无序数集

2.2.1 数集的插入

由于是无序数集，所以插入的时候无需处理顺序，直接根据数值来建树就可以了。

2.2.2 元素的删除

删除的时候，如果cnt大于1，只需修改cnt，否则先把这个节点旋转到根，根据上题的方法找到小于它最大的节点a和大于它最小的节点b，把a旋转到根，b旋转到a的儿子处，此时b的左子树中只包含这一个节点了，断掉b和它左子树的连边就可以了。当然是需要特判，分三种情况

  1. a存在，b不存在，即这个节点为最大值。把a旋转到根，断掉a和右儿子的连边即可。
  2. a不存在，b存在，即这个节点为最小值。把b旋转到根，断掉b和左儿子的连边即可。
  3. a和b均不存在，即splay在删除这个节点后会变为空树，因此只需要把fst置为1，将ndcnt自增，root赋为ndcnt。

2.2.3 数集的批量删除

如果要将某一范围内的数[x,y]批量删除，那么就可以把小于这一范围的最大的节点a旋转到根，大于这一范围的最小节点b旋转到a的儿子处，删除b的左子树即可。具体的实现方法仍在探索中，只是理论可行。
目前对于实现的思路如下：
使用上方的方法新增一个节点x，找到小于x的最大节点a，删除x。同理新增y，找到大于y的最小节点b，删除y。把a转到根，b转到第二层即可。
当然，也需要像上面一样特判：
1. a存在，b不存在，那么只需要把a旋转到根，断掉a和右儿子的连边
2. b存在，a不存在，那么只需要把b旋转到根，断掉b和左儿子的连边
3. a、b均不存在，也就意味着[x,y]包含了整棵splay中的所有节点，即splay在删除这个节点后会变为空树，因此只需要把fst置为1，将ndcnt自增，root赋为ndcnt。

2.2.4 数集的k大数查询

在splay的过程中，我们已经维护了每一个点子树的大小size，因此只需要递归地查询即可，实现的时候记得考虑节点的cnt。代码实现如下：

  1. //query the kth number from subtree x
  2. ll kth(int x,int k){
  3.         if(ch[x][25]!=0) {
  4.                 if(size[ch[x][26]]<k && size[ch[x][27]]+cnt[x]>=k) return val[x];
  5.         }
  6.         else{
  7.                 if(k<=cnt[x]) return val[x];
  8.         }
  9.         if(ch[x][28]!=0) {
  10.                 if(size[ch[x][29]]>=k) return kth(ch[x][30],k);
  11.                 return kth(ch[x][0],k-size[ch[x][31]]-cnt[x]);
  12.         }
  13.         return kth(ch[x][0],k-cnt[x]);
  14. }

例题

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。
好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

看起来这道题需要在一个动态更新的数集中找到第k大，事实上这个题目无需动态更新，只需用到类似NOIP2016 earthworm的化加为减的方法就可以了。当然，Splay在维护数集的时候是可以实现更新修改的，只是无需使用罢了。

代码实现：

  1. /*
  2.    郁闷的出纳员
  3.    created by Liu Junqi. All rights reserved.
  4.    2017.1.14
  5.    487ms
  6.  */
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <cstring>
  10. #include <algorithm>
  11. #include <iostream>
  12. #include <cmath>
  13. #include <ctime>
  14. #include <vector>
  15. #include <queue>
  16. #include <map>
  17. #include <set>
  18. using namespace std;
  19. const int inf = 2147483640;
  20. const int maxn = 100000 + 100;
  21. typedef long long ll;
  22. ll geti(){
  23.         char ch=getchar(); while((ch<'0' || ch>'9')&&ch!='-') ch=getchar();
  24.         ll ret=0,k=1;
  25.         if(ch=='-') k=-1,ch=getchar();
  26.         while(ch>='0' && ch<='9') ret=ret*10+ch-'0',ch=getchar();
  27.         return ret*k;
  28. }
  29. ll mini,delta=0;
  30. int ans=0;
  31. struct Splay {
  32.         int fa[maxn],ch[maxn][32],size[maxn],cnt[maxn],root,fst,ndcnt;
  33.         ll val[maxn];
  34.         Splay(){ //construct function for initialization
  35.                 memset(fa,0,sizeof(fa));
  36.                 memset(ch,0,sizeof(ch));
  37.                 memset(val,0,sizeof(val));
  38.                 memset(size,0,sizeof(size));
  39.                 memset(cnt,0,sizeof(cnt));
  40.                 root=1; fa[root]=0; fst=1; ndcnt=1;
  41.         }
  42.         int newnode(int v,int f){ //create a new splay node, retrun the number of it
  43.                 ++ndcnt;
  44.                 fa[ndcnt]=f;
  45.                 val[ndcnt]=v;
  46.                 return ndcnt;
  47.         }
  48.         int ins(ll v){ //insert a node to splay, need to use function "newnode"
  49.                 //special judgement for an emply splay
  50.                 if(fst) {
  51.                         val[root]=v;
  52.                         fst=0;
  53.                         size[root]=1; cnt[root]=1;
  54.                         return root;
  55.                 }
  56.                 int cur=root;
  57.                 while (ch[cur][val[cur]<v]) {
  58.                         ++size[cur];
  59.                         //special judgement for repeated value
  60.                         if(val[cur]==v) {
  61.                                 cnt[cur]++;
  62.                                 splay(cur,0);
  63.                                 return -1;
  64.                         }
  65.                         cur=ch[cur][val[cur]<v];
  66.                 }
  67.                 ++size[cur];
  68.                 if(val[cur]==v) {
  69.                         cnt[cur]++;
  70.                         splay(cur,0);
  71.                         return -1;
  72.                 }
  73.                 ch[cur][val[cur]<v]=newnode(v,cur);
  74.                 cur=ch[cur][val[cur]<v];
  75.                 ++size[cur];
  76.                 ++cnt[cur];
  77.                 splay(cur,0);
  78.                 return cur;
  79.         }
  80.         //rot and splay are the basic functions of splay tree
  81.         void rot(int cur,int op){ //if cur is the left child of its father, let op = 0. Otherwise, let op = 1;
  82.                 int y=fa[cur];
  83.                 if(ch[y][op]!=0) {ch[y][op]=ch[cur][!op]; fa[ch[y][op]]=y; }
  84.                 ch[fa[y]][ch[fa[y]][33]==y]=cur;
  85.                 fa[cur]=fa[y];
  86.                 ch[cur][!op]=y; fa[y]=cur;
  87.                 size[y]=size[ch[y][0]]+size[ch[y][34]]+cnt[y];
  88.                 size[cur]=size[ch[cur][0]]+size[ch[cur][35]]+cnt[cur];
  89.         }
  90.         void splay(int cur,int goal){ //goal is the father of cur when finished
  91.                 while(fa[cur]!=goal) {
  92.                         if(fa[fa[cur]]==goal) {
  93.                                 rot(cur,ch[fa[cur]][0]!=cur);
  94.                         }
  95.                         else{
  96.                                 int fad=(ch[fa[fa[cur]]][0]!=fa[cur]);
  97.                                 int sond=(ch[fa[cur]][0]!=cur);
  98.                                 if(fad==sond) {
  99.                                         rot(fa[cur],fad);
  100.                                         rot(cur,sond);
  101.                                 }
  102.                                 else{
  103.                                         rot(cur,sond);
  104.                                         rot(cur,fad);
  105.                                 }
  106.                         }
  107.                 }
  108.                 if(goal==0) root=cur;
  109.         }
  110.         //query the kth number
  111.         ll kth(int x,int k){
  112.                 if(ch[x][36]!=0) {
  113.                         if(size[ch[x][37]]<k && size[ch[x][38]]+cnt[x]>=k) return val[x];
  114.                 }
  115.                 else{
  116.                         if(k<=cnt[x]) return val[x];
  117.                 }
  118.                 if(ch[x][39]!=0) {
  119.                         if(size[ch[x][40]]>=k) return kth(ch[x][41],k);
  120.                         return kth(ch[x][0],k-size[ch[x][42]]-cnt[x]);
  121.                 }
  122.                 return kth(ch[x][0],k-cnt[x]);
  123.         }
  124.         //delete the number which is lower than mini ( only for this problem )
  125.         void del(){
  126.                 //special judge for an empty splay
  127.                 if(fst) return;
  128.                 int cur=root,st=-1; int k=mini-delta;
  129.                 while(ch[cur][val[cur]<k]) {
  130.                         if(val[cur]>=k) {
  131.                                 if(st!=-1) st=val[cur]<val[st] ? cur : st;
  132.                                 else st=cur;
  133.                         }
  134.                         cur=ch[cur][val[cur]<k];
  135.                 }
  136.                 if(val[cur]>=k) {
  137.                         if(st!=-1) st=val[cur]<val[st] ? cur : st;
  138.                         else st=cur;
  139.                 }
  140.                 if(st!=-1) {
  141.                         splay(st,0);
  142.                         size[st]-=size[ch[st][0]]; ans+=size[ch[st][0]];
  143.                         ch[st][0]=0;
  144.                 }
  145.                 else{
  146.                         //special judge for causing an empty splay
  147.                         ans+=size[root];
  148.                         ++ndcnt; root=ndcnt; fa[root]=0; fst=1; size[root]=0; ch[root][0]=0; ch[root][43]=0; val[root]=0;
  149.                 }
  150.         }
  151. } T;
  152. int n;
  153. int main(){
  154.         freopen("input.txt","r",stdin);
  155.         freopen("output.txt","w",stdout);
  157.         n=geti(); mini=geti();
  158.         ll rd;
  159.         char str[5];
  160.         for(int i=1; i<=n; i++) {
  161.                 scanf("%s",str); rd=geti();
  162.                 if(str[0]=='I') {if(rd<mini) {continue; } T.ins(rd-delta); }
  163.                 else if(str[0]=='A') {delta+=rd; }
  164.                 else if(str[0]=='S') {delta-=rd; T.del(); }
  165.                 else{printf("%lld\n",T.size[T.root]<rd ? -1 : T.kth(T.root,rd)+delta); }
  166.         }
  167.         printf("%d",ans);
  169.         fclose(stdin);
  170.         fclose(stdout);
  171.         return 0;
  172. }

2.3 Splay维护有序数列

2.3.1 有序数列的插入

对于有序数列，我们显然不能按照节点的值来构建splay，为了能够维持数列的有序性，考虑到splay不改变二叉树的中序遍历，因此我们把原始数列作为中序遍历的结果。因此，我们的插入操作便非常简便了，只需要把当前的数作为整棵splay中一路往右走的最后一个节点的右儿子即可。如果题目有指定编号则按他说的来（参见hihocoder）。

2.3.2 有序数列的批量插入

首先把需要插入的元素递归地构建成一颗完全平衡的二叉树，然后把原序列中的最后一个元素旋转到根，将这颗新建出来的二叉树的根作为它的右儿子。

2.3.3 有序数列的删除和批量删除

删除[a,b]（这里允许a和b相等）中的节点，那么就把a-1转到根，b+1转到a-1的儿子处，然后删除b+1的左子树即可。特判依旧同上。

2.3.4 有序数列的单点修改

对于单点修改，我们要使用和线段树不一样的方法，先删除这个节点，再添加一个序号相同的新节点

2.3.5 有序数列的区间修改

使用在2.2中提及到的区间提取方法，使用lazy数组进行下放（一旦点在旋转中受影响就下放）

2.3.6 有序数列的区间求和

使用和维护size类似的方法维护区间和即可

2.3.7 有序数列的区间翻转

打标记，有标记的节点的左右子树需要交换，然后下放标记。

2.3.8 参考例题

NOI2005 维护数列
此处输入图片的描述
此处输入图片的描述

题解和代码均来自hzwer

c分别是结点左右儿子，fa是结点父亲
size是子树大小，sum是子树权值和，v是结点权值，mx是当前子树的最大子串和
lx是一个子树以最左端为起点向右延伸的最大子串和，rx类似
tag是结点的修改标记，修改值为v，rev是翻转标记

  1. #include<queue>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<iostream>
  7. #include<algorithm>
  8. #define inf 1000000000
  9. #define N 1000005
  10. using namespace std;
  11. int read()
  12. {
  13.     int x=0,f=1;char ch=getchar();
  14.     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  15.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  16.     return x*f;
  17. }
  18. int n,m,rt,cnt;
  19. int a[N],id[N],fa[N],c[N][46];
  20. int sum[N],size[N],v[N],mx[N],lx[N],rx[N];
  21. bool tag[N],rev[N];
  22. queue<int> q;
  23. void update(int x)
  24. {
  25.     int l=c[x][0],r=c[x][47];
  26.     sum[x]=sum[l]+sum[r]+v[x];
  27.     size[x]=size[l]+size[r]+1;
  28.     mx[x]=max(mx[l],mx[r]);
  29.     mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);
  30.     lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
  31.     rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
  32. }
  33. void pushdown(int x)
  34. {
  35.     int l=c[x][0],r=c[x][48];
  36.     if(tag[x])
  37.     {
  38.         rev[x]=tag[x]=0;
  39.         if(l)tag[l]=1,v[l]=v[x],sum[l]=v[x]*size[l];
  40.         if(r)tag[r]=1,v[r]=v[x],sum[r]=v[x]*size[r];
  41.         if(v[x]>=0)
  42.         {
  43.             if(l)lx[l]=rx[l]=mx[l]=sum[l];
  44.             if(r)lx[r]=rx[r]=mx[r]=sum[r];
  45.         }
  46.         else 
  47.         {
  48.             if(l)lx[l]=rx[l]=0,mx[l]=v[x];
  49.             if(r)lx[r]=rx[r]=0,mx[r]=v[x];
  50.         }
  51.     }
  52.     if(rev[x])
  53.     {
  54.         rev[x]^=1;rev[l]^=1;rev[r]^=1;
  55.         swap(lx[l],rx[l]);swap(lx[r],rx[r]);
  56.         swap(c[l][0],c[l][49]);swap(c[r][0],c[r][50]);
  57.     }
  58. }
  59. void rotate(int x,int &k)
  60. {
  61.     int y=fa[x],z=fa[y],l,r;
  62.     l=(c[y][51]==x);r=l^1;
  63.     if(y==k)k=x;
  64.     else c[z][c[z][52]==y]=x;
  65.     fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
  66.     c[y][l]=c[x][r];c[x][r]=y;
  67.     update(y);update(x);
  68. }
  69. void splay(int x,int &k)
  70. {
  71.     while(x!=k)
  72.     {
  73.         int y=fa[x],z=fa[y];
  74.         if(y!=k)
  75.         {
  76.             if(c[y][0]==x^c[z][0]==y)rotate(x,k);
  77.             else rotate(y,k);
  78.         }
  79.         rotate(x,k);
  80.     }
  81. }
  82. int find(int x,int rk)
  83. {
  84.     pushdown(x);
  85.     int l=c[x][0],r=c[x][53];
  86.     if(size[l]+1==rk)return x;
  87.     if(size[l]>=rk)return find(l,rk);
  88.     return find(r,rk-size[l]-1);
  89. }
  90. void rec(int x)
  91. {
  92.     if(!x)return;
  93.     int l=c[x][0],r=c[x][54];
  94.     rec(l);rec(r);q.push(x);
  95.     fa[x]=c[x][0]=c[x][55]=0;
  96.     tag[x]=rev[x]=0;
  97. }
  98. int split(int k,int tot)
  99. {
  100.     int x=find(rt,k),y=find(rt,k+tot+1);
  101.     splay(x,rt);splay(y,c[x][56]);
  102.     return c[y][0];
  103. }
  104. void query(int k,int tot)
  105. {
  106.     int x=split(k,tot);
  107.     printf("%d\n",sum[x]);
  108. }
  109. void modify(int k,int tot,int val)
  110. {
  111.     int x=split(k,tot),y=fa[x];
  112.     v[x]=val;tag[x]=1;sum[x]=size[x]*val;
  113.     if(val>=0)lx[x]=rx[x]=mx[x]=sum[x];
  114.     else lx[x]=rx[x]=0,mx[x]=val;
  115.     update(y);update(fa[y]);
  116. }
  117. void rever(int k,int tot)
  118. {
  119.     int x=split(k,tot),y=fa[x];
  120.     if(!tag[x])
  121.     {
  122.         rev[x]^=1;
  123.         swap(c[x][0],c[x][57]);
  124.         swap(lx[x],rx[x]);
  125.         update(y);update(fa[y]);
  126.     }
  127. }
  128. void erase(int k,int tot)
  129. {
  130.     int x=split(k,tot),y=fa[x];
  131.     rec(x);c[y][0]=0;
  132.     update(y);update(fa[y]);
  133. }
  134. void build(int l,int r,int f)
  135. {
  136.     if(l>r)return;
  137.     int mid=(l+r)>>1,now=id[mid],last=id[f];
  138.     if(l==r)
  139.     {
  140.         sum[now]=a[l];size[now]=1;
  141.         tag[now]=rev[now]=0;
  142.         if(a[l]>=0)lx[now]=rx[now]=mx[now]=a[l];
  143.         else lx[now]=rx[now]=0,mx[now]=a[l];
  144.     }
  145.     else build(l,mid-1,mid),build(mid+1,r,mid);
  146.     v[now]=a[mid];fa[now]=last;update(now);
  147.     c[last][mid>=f]=now;
  148.    }
  149. void insert(int k,int tot)
  150. {
  151.     for(int i=1;i<=tot;i++)a[i]=read();
  152.     for(int i=1;i<=tot;i++)
  153.         if(!q.empty())id[i]=q.front(),q.pop();
  154.         else id[i]=++cnt;
  155.     build(1,tot,0);int z=id[(1+tot)>>1];
  156.     int x=find(rt,k+1),y=find(rt,k+2);
  157.     splay(x,rt);splay(y,c[x][58]);
  158.     fa[z]=y;c[y][0]=z;
  159.     update(y);update(x);
  160. }
  161. int main()
  162. {
  163.     n=read();m=read();
  164.     mx[0]=a[1]=a[n+2]=-inf;
  165.     for(int i=1;i<=n;i++)a[i+1]=read();
  166.     for(int i=1;i<=n+2;i++)id[i]=i;
  167.     build(1,n+2,0);
  168.     rt=(n+3)>>1;cnt=n+2;
  169.     int k,tot,val;
  170.     char ch[10];
  171.     while(m--)
  172.     {
  173.         scanf("%s",ch);
  174.         if(ch[0]!='M'||ch[2]!='X')k=read(),tot=read();
  175.         if(ch[0]=='I')insert(k,tot);
  176.         if(ch[0]=='D')erase(k,tot);
  177.         if(ch[0]=='M')
  178.         {
  179.             if(ch[2]=='X')printf("%d\n",mx[rt]);
  180.             else val=read(),modify(k,tot,val);
  181.         }
  182.         if(ch[0]=='R')rever(k,tot);
  183.         if(ch[0]=='G')query(k,tot);
  184.     }
  185.     return 0;
  186. }

其他数据结构

主席树

可持久化线段树，通过复用节点、多根设计与动态开点实现。
下面的代码是查询区间第k小。注意，主席树查询区间第k小的时候不能修改。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <vector>
  12. using namespace std;
  13. typedef long long ll;
  14. ll geti(){
  15.     char ch=getchar();
  16.     while((ch<'0' || ch>'9') && ch!='-')ch=getchar();
  17.     ll ret=0,k=0;
  18.     if(ch=='-')k=1,ch=getchar();
  19.     while(ch>='0' && ch<='9')ret=ret*10+ch-48,ch=getchar();
  20.     return k?-ret:ret;
  21. }
  22. const int maxn = 110000;
  23. int n,m;
  24. int root[maxn],ls[maxn*20],rs[maxn*20],val[maxn*20],sz;
  25. void build(int &x,int l,int r){
  26.     x=++sz;
  27.     if(l==r)return;
  28.     int mid=(l+r)>>1;
  29.     build(ls[x],l,mid);
  30.     build(rs[x],mid+1,r);
  31. }
  32. void update(int x,int &y,int l,int r,int p){
  33.     y=++sz;
  34.     val[y]=val[x]+1;
  35.     if(l==r)return;
  36.     int mid=(l+r)>>1;
  37.     ls[y]=ls[x];rs[y]=rs[x];
  38.     if(p<=mid)update(ls[x],ls[y],l,mid,p);
  39.     else update(rs[x],rs[y],mid+1,r,p);
  40. }
  41. int query(int x1,int x2,int l,int r,int k){
  42.     if(l==r)return l;
  43.     int mid=(l+r)>>1;
  44.     int cnt=val[ls[x2]]-val[ls[x1]];
  45.     if(k<=cnt)return query(ls[x1],ls[x2],l,mid,k);
  46.     else return query(rs[x1],rs[x2],mid+1,r,k-cnt);
  47. }
  48. int a[maxn],b[maxn];
  49. int main(){
  50.     freopen("input.txt","r",stdin);
  51.     freopen("output.txt","w",stdout);
  53.     int T=geti();
  54.     while(T--){
  55.         memset(ls,0,sizeof(ls));
  56.         memset(rs,0,sizeof(rs));
  57.         memset(val,0,sizeof(val));
  58.         memset(root,0,sizeof(root));
  59.         sz=0;
  60.         n=geti();m=geti();
  61.         for(int i=1;i<=n;i++)a[i]=(b[i]=geti());
  62.         sort(b+1,b+n+1);
  63.         int cnt=unique(b+1,b+n+1)-b-1;
  64.         build(root[0],1,cnt);
  65.         for(int i=1;i<=n;i++){
  66.             int op=lower_bound(b+1,b+1+cnt,a[i])-b;
  67.             update(root[i-1],root[i],1,cnt,op);
  68.         }
  69.         int l,r,k;
  70.         for(int i=1;i<=m;i++){
  71.             l=geti();r=geti();k=geti();
  72.             printf("%d\n",b[query(root[l-1],root[r],1,cnt,k)]);
  73.         }
  74.     }
  76.     return 0;
  77. }

KD树

KD树有一道经典题，sjy摆棋子，下面以此题为例简介kd树的操作。
kd树是一棵二叉搜索树，可以用于n维空间上点的查询。
对于kd树的定义这里不再赘述，网上有很多博客都讲得很清楚。
这里具体分析一下kd树的代码实现。

植树

由于kd树是二叉搜索树，每个节点都代表平面上的一个点，而且有左右儿子。

存储方式

我们定义如下的结构体来储存每一个kd树节点。

  1. struct P{
  2.     int d[2],mn[2],mx[2],l,r;
  3.     int& operator[](int x){
  4.         return d[x];
  5.     }
  6.     P(int x=0,int y=0){
  7.         d[0]=x;d[1]=y;l=0;r=0;
  8.     }
  9. }p[maxn];

表示的是这个节点在2个维度上的坐标，和表示这个节点的子树中2个维度的最小和最大值（便于查询），和表示左右儿子。
下面的重载运算符实现了快速访问到一个节点的坐标的方式，可以有效降低编程复杂度。
第三个构造函数便于传参。
整棵kd树我们用如下结构体存储：

  1. struct KDTree{
  2.     P t[maxn],T;
  3.     int ans,root;
  4. }kd;

是kd树中的节点数组，为一个临时的kd树节点。为查询结果的临时函数，是kd树的树根。
接下来涉及到的函数未加说明，都放在这个结构体里面。

构建

对于已经给予初始点集的题目，我们需要首先构建一棵初始的kd树。构造方法如下：

  1.     void build(int n){
  2.         root=build(1,n,0);
  3.     }
  4.     int build(int l,int r,int ct){
  5.         D=ct;
  6.         int mid=(l+r)>>1;
  7.         nth_element(p+l,p+mid,p+r+1);
  8.         t[mid]=p[mid];
  9.         init(mid);
  10.         if(l<mid)t[mid].l=build(l,mid-1,ct^1);
  11.         if(r>mid)t[mid].r=build(mid+1,r,ct^1);
  12.         update(mid);
  13.         return mid;
  14.     }

这里用到了c++的特性，同名不同参的函数是可以重复定义的。上面的 void build(int n); 提供了对主程序的接口，然后调用结构体内的函数实现建树。
这里的数组是一个全局数组，用于从主函数中读入数据。
值得一提的是nth_element()函数，它可以把一个序列中的某个点置为排名正确的点，把它左边的点置为比它小的点，右边的置为比它大的点。这样我们便可以很方便地提取到一个无序序列的中位数，并得到可以用于递归处理的序列。
是当前比较的维度，kd树一般是轮换当前比较维度的，这里由于只有两维，所以可以使用位运算简化编程。
是一个全局变量，实时更新为的值，用于nth_element()函数的比较。这里nth_element()函数是对一个自定义结构体操作，而系统是不支持结构体比较的，所以我们需要自定义一个比较函数，放在结构体外面：

  1. //for nth_element() function
  2. bool operator < (P a,P b){
  3.     return a[D]<b[D];
  4. }

最后要讲的是函数和函数，它们分别用于初始化和用子树数据更新一个节点的和值。

  1.     void init(int x){
  2.         t[x].l=0;t[x].r=0;
  3.         for(int i=0;i<2;i++){
  4.             t[x].mn[i]=t[x].mx[i]=t[x][i];
  5.         }
  6.     }
  7.     void update(int k){
  8.         int ls=t[k].l,rs=t[k].r;
  9.         for(int i=0;i<2;i++){
  10.             if(ls){
  11.                 t[k].mn[i]=min(t[k].mn[i],t[ls].mn[i]);
  12.                 t[k].mx[i]=max(t[k].mx[i],t[ls].mx[i]);
  13.             }
  14.             if(rs){
  15.                 t[k].mn[i]=min(t[k].mn[i],t[rs].mn[i]);
  16.                 t[k].mx[i]=max(t[k].mx[i],t[rs].mx[i]);
  17.             }
  18.         }
  19.     }

另外，为了避免RE，所有对左右儿子的操作都应检查相应的儿子是否存在。

插入

插入操作可以向kd树中插入一个节点，用的方法类似平衡树：

  1.     void insert(P x){
  2.         T=x;insert(root,0);
  3.     }
  4.     void insert(int k,int ct){
  5.         if(T[ct]<=t[k][ct]){
  6.             if(t[k].l)insert(t[k].l,ct^1);
  7.             else{
  8.                 t[k].l=++n;
  9.                 t[n]=T;
  10.                 init(n);
  11.             }
  12.         }
  13.         else{
  14.             if(t[k].r)insert(t[k].r,ct^1);
  15.             else{
  16.                 t[k].r=++n;
  17.                 t[n]=T;
  18.                 init(n);
  19.             }
  20.         }
  21.         update(k);
  22.     }

插入操作使用到了之前提到的数组，临时存储要插入的节点，避免传参。具体的操作与平衡树十分类似，不作分析。

砍树（剪枝）

砍树主要指查询的过程。kd树本身并不能按照平衡树那样做到完美的查询，因为每次轮换划分的维度，并不能保证离查询的点最近的节点一定在如果把这个点插入kd树它所在的位置附近。很多博客都对这一个性质有介绍。
kd树的查询复杂度主要靠砍树，不剪枝的话查询会是的。

估价函数

根据我们之前的插入操作，每个节点子树的点所在区间范围是明确的。我们可以使用估价函数get()获取查询的节点到某棵子树中点的范围的距离。注意get()函数是用于砍树的，所以一定要是乐观估价函数。
这道题我们求的是曼哈顿距离，且要求答案最小，所以我们的函数要求出这个点到点范围的最小值。

  1.     int get(int k,P p){
  2.         int ret=0;
  3.         for(int i=0;i<2;i++){
  4.             ret+=max(0,t[k].mn[i]-p[i])+max(0,p[i]-t[k].mx[i]);
  5.         }
  6.         return ret;
  7.     }

可以手动模拟一下这个过程来了解它为什么是对的。
不用担心，这里的点作用域就在本函数内，与外面的数组是无关的，且会在本函数内覆盖掉数组的定义。
k是查询的子树的根节点序号。

四种估价函数

根据题目要求的不同，有四种常用的估价函数。
第一种是上面提到的曼哈顿距离最小值。
第二种是曼哈顿距离最大值：


定义函数是平方函数
第三种是欧几里得距离最小值：

第四种是欧几里得距离最大值：

具体查询

有了上面的估价函数，查询操作便迎刃而解了。

  1.     int query(P x){
  2.         T=x;ans=inf;query(root,0);
  3.         return ans;
  4.     }
  5.     void query(int k,int ct){
  6.         int cur,dl=inf,dr=inf;
  7.         cur=dis(t[k],T);
  8.         ans=min(ans,cur);
  9.         if(t[k].l)dl=get(t[k].l,T);
  10.         if(t[k].r)dr=get(t[k].r,T);
  11.         if(dl<dr){
  12.             if(dl<ans)query(t[k].l,ct^1);
  13.             if(dr<ans)query(t[k].r,ct^1);
  14.         }
  15.         else{
  16.             if(dr<ans)query(t[k].r,ct^1);
  17.             if(dl<ans)query(t[k].l,ct^1);
  18.         }
  19.     }

是查询到的节点，是当前比较维度。每查询到一个节点都更新答案。
注意搜索顺序要从get()小的子树搜起，这样比较容易得到更优的答案，或许另一棵子树就被砍掉了。
dis()函数计算两点距离，代码如下：

  1.     int dis(P x,P y){
  2.         return abs(x[0]-y[0])+abs(x[1]-y[1]);
  3.     }

这样，kd树的基本操作我们就写完了，现在可以愉快地做这道题了。

莫队算法

CZH说这也是数据结构，那就当它是数据结构好了。
将区间分成sqrt(n)块，按照左端点所在块和右端点排序查询，然后暴力更新答案。
下面的代码是小z的袜子。

  1. /**************************************************************
  2.     Problem: 2038
  3.     User: jesseliu612
  4.     Language: C++
  5.     Result: Accepted
  6.     Time:1028 ms
  7.     Memory:4584 kb
  8. ****************************************************************/
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <cmath>
  14. #include <algorithm>
  15. #include <iostream>
  16. using namespace std;
  17. typedef long long ll;
  18. const int maxn = 70000;
  19. struct Query{
  20.     int l,r,id,blk;
  21. }q[maxn];
  22. int n,Q,a[maxn],s[maxn],block;
  23. ll cc[maxn];
  24. ll ans=0,ra[maxn],rb[maxn];
  25. int geti(){
  26.     char ch=getchar();
  27.     while(ch<'0' || ch>'9')ch=getchar();
  28.     int ret=0;
  29.     while(ch>='0' && ch<='9')ret=ret*10+ch-48,ch=getchar();
  30.     return ret;
  31. }
  32. inline char cmp(const Query &x,const Query &y){
  33.     return x.blk<y.blk || (x.blk==y.blk && x.r<y.r);
  34. }
  35. inline ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
  36. inline void update(int p,int add){
  37.     ans-=cc[s[a[p]]];s[a[p]]+=add;ans+=cc[s[a[p]]];
  38. }
  39. int main(){
  40.     n=geti();Q=geti();
  41.     cc[0]=0,cc[1]=0;
  42.     for(register int i=2;i<=n;i++)cc[i]=(ll)i*(i-1);
  43.     for(register int i=1;i<=n;i++)scanf("%d",a+i);
  44.     block=floor(sqrt(n));
  45.     for(register int i=1;i<=Q;i++)q[i].l=geti(),q[i].r=geti(),q[i].id=i,q[i].blk=q[i].l/block;
  46.     sort(q+1,q+1+Q,cmp);
  47.     int l=1,r=0;
  48.     for(register int i=1;i<=Q;i++){
  49.     for(;l<q[i].l;l++)update(l,-1);
  50.     for(;l>q[i].l;l--)update(l-1,1);
  51.     for(;r<q[i].r;r++)update(r+1,1);
  52.     for(;r>q[i].r;r--)update(r,-1);
  53.     register ll rra,rrb;
  54.     rra=ans;
  55.     rrb=cc[q[i].r-q[i].l+1];
  56.     if(rra==0){ra[q[i].id]=0;rb[q[i].id]=1;continue;}
  57.     register ll d=gcd(rra,rrb);
  58.     ra[q[i].id]=rra/d;rb[q[i].id]=rrb/d;
  59.     }
  60.     for(register int i=1;i<=Q;i++)printf("%lld/%lld\n",ra[i],rb[i]);
  62.     return 0;
  63. }

左偏树

可并堆的一种，兼顾效率和代码难度。dis是向右走能够走的距离。整棵树保证向左边偏，合并都在右边操作。

  1. struct MergeableHeap{
  2.     int ch[maxn][59],fa[maxn],val[maxn],dis[maxn];
  3.     void init(){
  4.     dis[0]=0;
  5.     memset(fa,0,sizeof(fa));
  6.     memset(ch,0,sizeof(ch));
  7.     memset(dis,0,sizeof(dis));
  8.     }
  9.     int anc(int x){
  10.     return fa[x]==0?x:anc(fa[x]);
  11.     }
  12.     int merge(int h,int s){
  13.     if(h==0)return s;if(s==0)return h;
  14.     if(val[h]<val[s])swap(h,s);
  15.     if(dis[ch[h][0]]<dis[ch[h][60]])swap(ch[h][0],ch[h][61]);
  16.     if(ch[h][62]!=0){
  17.         int y=merge(ch[h][63],s);
  18.         ch[h][64]=y;
  19.         fa[y]=h;
  20.     }
  21.     else{
  22.         ch[h][65]=s;
  23.         fa[s]=h;
  24.     }
  25.     if(ch[h][66])dis[h]=dis[ch[h][67]]+1;
  26.     else dis[h]=0;
  27.     return h;
  28.     }
  29.     int rebuild(int a){
  30.     fa[ch[a][0]]=0;fa[ch[a][68]]=0;
  31.     int h=merge(ch[a][0],ch[a][69]);
  32.     ch[a][0]=0;ch[a][70]=0;dis[a]=0;
  33.     int s=merge(a,h);
  34.     return s;
  35.     }
  36. }h;

基础算法

高斯消元

个人常用的是高斯-约当消元法，可以比较简便地得到答案。大多数题目都不需要注意精度问题。
把方程转化成矩阵，首先选取主元，然后把行除以主元，接着把列减成0。最后得到的矩阵就是结果。
下面的代码对应的是球形空间生成器。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <cmath>
  6. using namespace std;
  7. const int maxn = 20;
  8. const double eps = 1e-9;
  9. int n;
  10. double img[maxn][maxn],xmg[maxn][maxn];
  11. int main(){
  12.     freopen("input.txt","r",stdin);
  13.     freopen("output.txt","w",stdout);
  15.     scanf("%d",&n);
  16.     for(int i=1;i<=n+1;++i){
  17.     for(int j=1;j<=n;++j){
  18.         scanf("%lf",&img[i][j]);
  19.     }
  20.     }
  21.     for(int i=1;i<=n;i++){
  22.     for(int j=1;j<=n;j++){
  23.         xmg[i][j]=2*(img[i+1][j]-img[i][j]);
  24.     }
  25.     for(int j=1;j<=n;j++){
  26.         xmg[i][n+1]+=img[i+1][j]*img[i+1][j]-img[i][j]*img[i][j];
  27.     }
  28.     }
  29.     for(int i=1;i<=n;i++){
  30.     if(fabs(xmg[i][i])<=eps){
  31.         for(int j=i+1;j<=n;j++){ //row |
  32.         if(fabs(xmg[j][i])>eps){
  33.             for(int k=1;k<=n+1;k++){ //line --
  34.             swap(xmg[i][k],xmg[j][k]);
  35.             }
  36.         }
  37.         }
  38.     }
  39.     double vv=xmg[i][i];
  40.     for(int j=1;j<=n+1;j++){ //line --
  41.         xmg[i][j]/=vv;
  42.     }
  43.     for(int j=1;j<=n;j++){ //row | 
  44.         if(j==i)continue;
  45.         double div=xmg[j][i]/xmg[i][i];
  46.         for(int k=1;k<=n+1;k++){ //line --
  47.         xmg[j][k]-=xmg[i][k]*div;
  48.         }
  49.     }
  50.     }
  51.     for(int i=1;i<=n;i++){
  52.     if(i>1)putchar(' ');
  53.     printf("%.3lf",xmg[i][n+1]);
  54.     }
  56.     return 0;
  57. }

整体二分

二分答案，检验答案，把小于答案的询问放左边，否则放右边。递归处理。
比较麻烦的地方是边界的判定和符号的选取。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <vector>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. using namespace std;
  13. const int inf = 2147483640;
  14. typedef long long ll;
  15. ll geti(){
  16.         char ch=getchar(); while((ch<'0' || ch>'9')&&ch!='-') ch=getchar();
  17.         ll ret=0,k=1;
  18.         if(ch=='-') k=-1,ch=getchar();
  19.         while(ch>='0' && ch<='9') ret=ret*10+ch-'0',ch=getchar();
  20.         return ret*k;
  21. }
  22. const int maxn = 200000;
  23. int n,Q,a[maxn],ans[maxn];
  24. struct Qst {
  25.         int t,v,l,r,k;
  26. } q[maxn],t1[maxn],t2[maxn];
  27. struct TreelikeArray {
  28.         int mx[maxn];
  29.         int lowbit(int k){
  30.                 return k&(-k);
  31.         }
  32.         void update(int x,int v){
  33.                 for(int i=x; i<maxn; i+=lowbit(i)) mx[i]+=v;
  34.         }
  35.         int query(int x){
  36.                 int ret=0;
  37.                 for(int i=x; i>=1; i-=lowbit(i)) ret+=mx[i];
  38.                 return ret;
  39.         }
  40. } T;
  41. void solve(int l,int r,int xl,int xr){
  42.         if(xl>=xr || l>r) return;
  43.         if(l==r) {
  44.                 for(int i=xl; i<=xr; i++) if(q[i].t==2) ans[q[i].v]=a[l];
  45.                 return;
  46.         }
  47.         int mid=(l+r)>>1; int mv=a[mid];
  48.         int m=1,g=1,cnt=0;
  49.         for(int i=xl; i<=xr; i++) {
  50.                 if(q[i].t==1) {
  51.                         if(q[i].v<=mv) {
  52.                                 T.update(q[i].k,1); t1[m++]=q[i]; if(q[i].v==mv) ++cnt;
  53.                         }
  54.                         else t2[g++]=q[i];
  55.                 }
  56.                 else{
  57.                         int s=T.query(q[i].r)-T.query(q[i].l-1);
  58.                         if(s>=q[i].k) {
  59.                                 t1[m++]=q[i];
  60.                         }
  61.                         else{
  62.                                 q[i].k-=s;
  63.                                 t2[g++]=q[i];
  64.                         }
  65.                 }
  66.         }
  67.         for(int i=xl; i<=xr; i++) {
  68.                 if(q[i].t==1 && q[i].v<=mv) T.update(q[i].k,-1);
  69.         }
  70.         int p=xl,tmp;
  71.         for(int i=1; i<m; i++) q[p++]=t1[i];
  72.         tmp=p;
  73.         for(int i=1; i<g; i++) q[p++]=t2[i];
  74.         solve(l,mid,xl,tmp-1);
  75.         solve(mid+1,r,tmp,p-1);
  76. }
  77. int main(){
  78.         freopen("input.txt","r",stdin);
  79.         freopen("output.txt","w",stdout);
  81.         n=geti(); Q=geti();
  82.         for(int i=1; i<=n; i++) {a[i]=geti(); q[i].t=1; q[i].v=a[i]; q[i].k=i; }
  83.         sort(a+1,a+1+n);
  84.         for(int i=1; i<=Q; i++) {
  85.                 q[n+i].t=2; q[n+i].l=geti(); q[n+i].r=geti(); q[n+i].k=geti();
  86.                 q[n+i].v=i;
  87.                 if(q[n+i].l>q[n+i].r) swap(q[n+i].l,q[n+i].r);
  88.         }
  89.         solve(1,n,1,n+Q);
  90.         for(int i=1; i<=Q; i++) printf("%d\n",ans[i]);
  92.         fclose(stdin);
  93.         fclose(stdout);
  94.         return 0;
  95. }

上面的代码是k小数查询（和上面主席树是一个题）。

cdq分治

俗话说，“一维排序，二维树状数组，三维cdq分治。”cdq分治把询问按时间分治，用前一半的修改更新后一半的查询，递归处理，在）的时间内得出三维偏序的答案。同时，cdq分治还可用于优化dp的转移。
IOI有道题叫移动电话，是二维树状数组的模板题。我们可以使用cdq分治解决它（慢得多）。
正常版：

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <vector>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. using namespace std;
  13. const int inf = 2147483640;
  14. typedef long long ll;
  15. ll geti(){
  16.         char ch=getchar(); while((ch<'0' || ch>'9')&&ch!='-') ch=getchar();
  17.         ll ret=0,k=1;
  18.         if(ch=='-') k=-1,ch=getchar();
  19.         while(ch>='0' && ch<='9') ret=ret*10+ch-'0',ch=getchar();
  20.         return ret*k;
  21. }
  22. const int maxn = 600020;
  23. struct Qst {
  24.         int op,x,y,a,id,t;
  25. } q[maxn],t1[maxn],t2[maxn];
  26. int ans[maxn];
  27. struct TreelikeArray{
  28.         int mx[maxn];
  29.         TreelikeArray(){
  30.                 memset(mx,0,sizeof(mx));
  31.         }
  32.         int lowbit(int x){
  33.                 return x&(-x);
  34.         }
  35.         void update(int x,int v){
  36.                 x+=1;
  37.                 for(int i=x;i<maxn;i+=lowbit(i))mx[i]+=v;
  38.         }
  39.         int query(int r){
  40.                 r+=1;
  41.                 int ret=0;
  42.                 for(int i=r;i>=1;i-=lowbit(i))ret+=mx[i];
  43.                 return ret;
  44.         }
  45. }T;
  46. void solve(int l,int r){ //[l,r]为时间维度，[xl,xr]为x维的位置
  47.         if(l>=r)return;
  48.         int mid=(l+r)>>1;int m=0,g=0;
  49.         for(int i=l;i<=r;i++){
  50.                 if(q[i].op==1){
  51.                         if(q[i].t<=mid){
  52.                                 T.update(q[i].y,q[i].a);
  53.                                 t1[++m]=q[i];
  54.                         }
  55.                         else{
  56.                                 t2[++g]=q[i];
  57.                         }
  58.                 }
  59.                 else if(q[i].op==2){
  60.                         if(q[i].t>mid){
  61.                                 ans[q[i].id]+=q[i].a*T.query(q[i].y);
  62.                                 t2[++g]=q[i];
  63.                         }
  64.                         else{
  65.                                 t1[++m]=q[i];
  66.                         }
  67.                 }
  68.         }
  69.         for(int i=l;i<=r;i++)if(q[i].op==1 && q[i].t<=mid)T.update(q[i].y,-q[i].a);
  70.         int p=0;
  71.         for(int i=l;i<=mid;i++)q[i]=t1[++p];
  72.         p=0;
  73.         for(int i=mid+1;i<=r;i++)q[i]=t2[++p];
  74.         solve(l,mid);
  75.         solve(mid+1,r);
  76. }
  77. bool cmp(Qst x,Qst y){
  78.         if(x.x!=y.x)return x.x<y.x;
  79.         else if(x.t!=y.t) return x.t<y.t;
  80.         else return x.y<y.y;
  81. }
  82. int main(){
  83.         freopen("input.txt","r",stdin);
  84.         freopen("output.txt","w",stdout);
  86.         int op,id=0,p=0;
  87.         while(1) {
  88.                 op=geti();
  89.                 if(op==3) break;
  90.                 if(op==0) {op=geti();continue;}
  91.                 if(op==1) {
  92.                         q[++p].op=1; q[p].x=geti(); q[p].y=geti(); q[p].a=geti(); q[p].t=p;
  93.                 }
  94.                 else{
  95.                         int a=geti(),b=geti(),c=geti(),d=geti();
  96.                         q[++p].op=2; q[p].x=a-1; q[p].y=b-1;
  97.                         q[p].a=1; q[p].id=++id; q[p].t=p;
  99.                         q[++p].op=2; q[p].x=c; q[p].y=b-1;
  100.                         q[p].a=-1; q[p].id=id; q[p].t=p;
  102.                         q[++p].op=2; q[p].x=a-1; q[p].y=d;
  103.                         q[p].a=-1; q[p].id=id; q[p].t=p;
  105.                         q[++p].op=2; q[p].x=c; q[p].y=d;
  106.                         q[p].a=1; q[p].id=id; q[p].t=p;
  107.                 }
  108.         }
  109.         sort(q+1,q+1+p,cmp);//x维排序处理
  110.         solve(1,p);//t维cdq分治，y维使用树状数组统计
  111.         for(int i=1;i<=id;i++)printf("%d\n",ans[i]);
  113.         fclose(stdin);
  114.         fclose(stdout);
  115.         return 0;
  116. }

叶神小常数版：

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <vector>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. using namespace std;
  13. const int inf = 2147483640;
  14. typedef long long ll;
  15. ll geti(){
  16.         char ch=getchar(); while((ch<'0' || ch>'9')&&ch!='-') ch=getchar();
  17.         ll ret=0,k=1;
  18.         if(ch=='-') k=-1,ch=getchar();
  19.         while(ch>='0' && ch<='9') ret=ret*10+ch-'0',ch=getchar();
  20.         return ret*k;
  21. }
  22. const int maxn = 600020;
  23. struct Qst {
  24.         int op,x,y,a,id,t;
  25. } q[maxn],t[maxn];
  26. int ans[maxn];
  27. struct TreelikeArray{
  28.         int mx[maxn];
  29.         TreelikeArray(){
  30.                 memset(mx,0,sizeof(mx));
  31.         }
  32.         int lowbit(int x){
  33.                 return x&(-x);
  34.         }
  35.         void update(int x,int v){
  36.                 x+=1;
  37.                 for(int i=x;i<maxn;i+=lowbit(i))mx[i]+=v;
  38.         }
  39.         int query(int r){
  40.                 r+=1;
  41.                 int ret=0;
  42.                 for(int i=r;i>=1;i-=lowbit(i))ret+=mx[i];
  43.                 return ret;
  44.         }
  45. }T;
  46. void solve(int l,int r){ //[l,r]为时间维度, 使用归并排序来递归对x排序。
  47.         if(l>=r)return;
  48.         int mid=(l+r)>>1;
  49.         solve(l,mid);solve(mid+1,r);
  50.         //printf("solve(%d,%d)\n",l,r);cout << flush;
  51.         int x=l,m=l,g=mid+1;
  52.         while(m<=mid && g<=r){
  53.                 if(q[m].x<=q[g].x){
  54.                         t[x]=q[m];
  55.                         if(q[m].op==1){
  56.                                 T.update(q[m].y,q[m].a);
  57.                         }
  58.                         ++m;++x;
  59.                 }
  60.                 else{
  61.                         t[x]=q[g];
  62.                         if(q[g].op==2){
  63.                                 ans[q[g].id]+=q[g].a*T.query(q[g].y);
  64.                         }
  65.                         ++g;++x;
  66.                 }
  67.         }
  68.         while(m<=mid){
  69.                 t[x]=q[m];
  70.                 if(q[m].op==1){
  71.                         T.update(q[m].y,q[m].a);
  72.                 }
  73.                 ++m;++x;
  74.         }
  75.         while(g<=r){
  76.                 t[x]=q[g];
  77.                 if(q[g].op==2){
  78.                         ans[q[g].id]+=q[g].a*T.query(q[g].y);
  79.                 }
  80.                 ++g;++x;
  81.         }
  82.         for(int i=l;i<=mid;i++)if(q[i].op==1)T.update(q[i].y,-q[i].a);
  83.         for(int i=l;i<=r;i++)q[i]=t[i];
  84. }
  85. int main(){
  86.         freopen("input.txt","r",stdin);
  87.         freopen("output.txt","w",stdout);
  89.         int op,id=0,p=0;
  90.         while(1) {
  91.                 op=geti();
  92.                 if(op==3) break;
  93.                 if(op==0) {op=geti();continue;}
  94.                 if(op==1) {
  95.                         q[++p].op=1; q[p].x=geti(); q[p].y=geti(); q[p].a=geti(); q[p].t=p;
  96.                 }
  97.                 else{
  98.                         int a=geti(),b=geti(),c=geti(),d=geti();
  99.                         q[++p].op=2; q[p].x=a-1; q[p].y=b-1;
  100.                         q[p].a=1; q[p].id=++id; q[p].t=p;
  102.                         q[++p].op=2; q[p].x=c; q[p].y=b-1;
  103.                         q[p].a=-1; q[p].id=id; q[p].t=p;
  105.                         q[++p].op=2; q[p].x=a-1; q[p].y=d;
  106.                         q[p].a=-1; q[p].id=id; q[p].t=p;
  108.                         q[++p].op=2; q[p].x=c; q[p].y=d;
  109.                         q[p].a=1; q[p].id=id; q[p].t=p;
  110.                 }
  111.         }
  112.         solve(1,p);
  113.         for(int i=1;i<=id;i++)printf("%d\n",ans[i]);
  115.         fclose(stdin);
  116.         fclose(stdout);
  117.         return 0;
  118. }

事实上使用了归并排序降低常数。

其他

这一部分的内容与竞赛无关。

emacs配置

  1. (put 'set-goal-column 'disabled nil)
  2. (put 'narrow-to-region 'disabled nil)
  3. (put 'upcase-region 'disabled nil)
  4. (put 'downcase-region 'disabled nil)
  5. (put 'LaTeX-hide-environment 'disabled nil)
  6. (setq column-number-mode t)
  7. (setq auto-save-default nil)
  8. (transient-mark-mode t)
  9. (tool-bar-mode -1)
  10. (setq-default make-backup-files nil)
  11. (global-font-lock-mode 1)
  12. (setq-default indent-tabs-mode  nil)
  13. ;;;
  14. (blink-cursor-mode 1)
  15. (setq auto-save-mode t)
  16. (transient-mark-mode 1)
  17. (setq-default cursor-type 'bar)
  18. (fset 'yes-or-no-p 'y-or-n-p)
  19. (setq column-number-mode t)
  20. (setq line-number-mode t)
  21. (setq show-paren-style 'parenthesis)
  22. ;;(show-paren-mode f)
  23. (global-linum-mode t)
  24. (setq c-basic-offset 4)
  25. ;;set transparent effect
  26. (global-set-key [(f11)] 'loop-alpha)
  27. (setq alpha-list '((100 100) (95 65) (85 55) (75 45) (65 35)))
  28. (defun loop-alpha ()
  29.   (interactive)
  30.    (let ((h (car alpha-list)))                ;; head value will set to
  31.      ((lambda (a ab)
  32.         (set-frame-parameter (selected-frame) 'alpha (list a ab))
  33.        (add-to-list 'default-frame-alist (cons 'alpha (list a ab)))
  34.        ) (car h) (car (cdr h)))
  35.     (setq alpha-list (cdr (append alpha-list (list h))))
  36.      )
  37.  )
  38. ;;;调透明度
  39. (set-frame-parameter (selected-frame) 'alpha (list 95 95))
  40. ; ; 设置界面
  41. (set-cursor-color "Wheat")
  42. (set-mouse-color "Wheat")
  43. (set-foreground-color "gray80")
  44. (set-background-color "gray12")
  45. (set-face-foreground 'region "gray12")
  46. (set-face-background 'region "gray60")
  47. (set-face-foreground 'secondary-selection "gray12")
  48. (set-face-background 'secondary-selection "gray80")
  49. ;;(set-background-color "DarkSlateGray")
  50. (if window-system
  51.         (setq default-frame-alist
  52.                 (append
  53.                         '( (top . 80)
  54.                                  (left . 100)
  55.                                              (width . 110)
  56.                                              (height . 35))
  57.                                                                   default-frame-alist))
  58. )
  59. (defun du-onekey-compile ()
  60.   "Save buffers and start compile"
  61.   (interactive)
  62.   (compile (format "g++ -o %s %s -g -Wall"  (file-name-sans-extension (buffer-name))(buffer-name))))
  63.   (global-set-key [f9] 'du-onekey-compile)
  64. (custom-set-variables
  65.  ;; custom-set-variables was added by Custom.
  66.  ;; If you edit it by hand, you could mess it up, so be careful.
  67.  ;; Your init file should contain only one such instance.
  68.  ;; If there is more than one, they won't work right.
  69.  '(column-number-mode t)
  70.  '(cua-mode t nil (cua-base))
  71.  '(inhibit-startup-screen t)
  72.  '(tool-bar-mode nil))
  73. (custom-set-faces
  74.  ;; custom-set-faces was added by Custom.
  75.  ;; If you edit it by hand, you could mess it up, so be careful.
  76.  ;; Your init file should contain only one such instance.
  77.  ;; If there is more than one, they won't work right.
  78.  '(default ((t (:family "Ubuntu Mono" :foundry "unknown" :slant normal :weight normal :height 158 :width normal)))))
  79. (setq-default indent-tabs-mode  nil)
  80. (global-set-key (kbd "RET") 'newline-and-indent)

代码模板

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <vector>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. using namespace std;
  13. const int inf = 2147483640;
  14. typedef long long ll;
  15. ll geti(){
  16.     char ch=getchar();while((ch<'0' || ch>'9')&&ch!='-')ch=getchar();
  17.     ll ret=0,k=1;
  18.     if(ch=='-')k=-1,ch=getchar();
  19.     while(ch>='0' && ch<='9')ret=ret*10+ch-'0',ch=getchar();
  20.     return ret*k;
  21. }
  22. int main(){
  23.     freopen("input.txt","r",stdin);
  24.     freopen("output.txt","w",stdout);
  28.     fclose(stdin);
  29.     fclose(stdout);
  30.     return 0;
  31. }

Latex

latex是学长常用的排版语言，可以通过编写代码，使用编译的方式生成pdf文件。

安装

打开终端，输入以下命令
1.安装基本库
sudo apt-get install texlive-latex-base

(可选)安装中文库：
sudo apt-get install latex-cjk-all

2.安装常用宏包如ncctools等：
sudo apt-get install texlive-latex-extra

3.在应用程序中查找texstudio，如果没有，那么：
sudo apt-get install texstudio

编辑

打开texstudio，新建一个文件（鼠标移到顶上，file-new），然后按ctrl+s保存到你喜欢的地方。
输入以下的代码：

  1. \documentclass{article}
  2. \usepackage{xeCJK}
  3. \usepackage{listings}
  4. \setCJKmainfont{Droid Sans Fallback}
  5. \setmainfont{Ubuntu Mono}
  6. \renewcommand{\baselinestretch}{1.5}
  7. \author{你的名字}
  8. \title{你的标题}
  9. \begin{document}
  10. \maketitle
  11. 这里开始写文章
  12. \end{document}

点击工具栏中两个向右的三角形按钮（它右边是一个向右的三角形按钮），右边就会出现一个生成的pdf文件。
注意如果需要换行，那么要在两段之间留一个空行。或者输入两个反斜杠\。
接下来是一些基本语法：

  1. \section{章节标题}
  2. 章节内容
  3. \subsection{子章节标题}
  4. 子章节内容

这个在出题的时候可以把章节标题设成题目名称，子章节标题设成题目描述、输入、输出、样例等内容。section是无需关闭的，只是用于生成一个章节标题。

  1. \begin{lstlisting}[language=C]
  2. 这里是代码
  3. \end{lstlisting}

这样生成一段代码块。

  1. \clearpage

这是强制分页操作。

还有很多latex的语法，如果遇到需要使用，可以自行查找。
表格：

  1. \vspace{3ex}
  2. \makebox[0.92\linewidth]{
  3. \begin{tabularx}{\linewidth}{|p{80pt}<{\centering}|p{32pt}<{\centering}|p{32pt}<{\centering}|p{32pt}<{\centering}|X<{\centering}|}
  4. \hline
  5. 	测试点编号 & n & m & Q & 特殊性质 \\ \hline
  6. 	1-3 & 1000 & 1000 & 1 & 给出的图是一棵树 \\ \hline 
  7. 	4-10 & 1000 & 1000 & 1 & 给出的图是一棵树  \\ \hline 
  8. \end{tabularx}
  9. }

要加\usepackage{tabularx}宏包

写在2017寒假的最后

鞭炮声声，礼花阵阵。都市恢复了往日的喧嚣，伴着时光流逝的脚步，送走了新春，迎来了新的一年。只可惜，又是一个未披银装的暖冬。

常言道，“十五送春”。是时候与过往的自己作别，面对全新的挑战了。前几年到正月十五的时候，大多都已开学，唯有今年是个例外，因此得以在这时来作些忆想，好好地总结一番。

寒假是1月中旬开始的。刚结束了期考的紧张复习，就走进科学馆六楼的机房，开始第一阶段的集训了。距离四月中旬的省选还有三个多月，但知识学习的速度却难以跟上时间的步伐。啃着拗口的白书，翻着泛泛而谈的博客，时而向大佬和学长们请教些问题，似乎懂了，却又有些生疏。解题自然是困难的，一层层解开出题人的伪装，自以为找出了内在的逻辑，待到代码敲完，输入样例，F9后的错误答案却再次让欣喜的内心跌落谷底。亦或自信满满，选上一道思路清晰的问题，将全部的赌注下在上面，但时常会在编程的过程中迷失方向，最后要么爆零，要么发现所谓的正解，不过是一个更高级一点的暴力。尽管浑浑噩噩，可考场上大家似乎也都同我一般不时出些差错，加之题目又没有充分考察到所学的知识，凭着上学期积下的老本，便也没太大的问题。

从splay到整体二分，从2-SAT到网络流，似乎也学了些新东西。就这样，两个星期一晃而过，很快到了1月24日。

春节放8天假，原本是计划每天写3课把寒假作业写完的，但计划从一开始就被完全放松下来的自己打破，好像很难回到半个月前的那个积极进取、奋力拼搏的我了。对着题目发呆，常常半个小时都找不到突破的思路，虽有答案在手，可从不忍心放纵自己把答案填上、背下来，以应付开学的那场作业检测。于是整个春节期间就只写了百来页寒假作业，以至于现在还不知道作业该怎么办。

这个春节过得并不平静。25日凌晨便传来噩耗，刚过完生日的老爷爷在深夜离开了人世，而且没能见上最后一面就走了。大年三十是追悼会的日子，这使从未进过殡仪馆的我第一次理解何为阴阳两隔。既因人数受限，又因自己害怕面对死亡，火化的时候我没有进去。每次去拜访老爷爷的时候，他总说，“这个买卖子，一定会有出息的！”，同时艰难地举起手，竖起大拇指。直到这时我才真正体会到生命的短暂，要珍惜每一天，珍惜每一个家人、老师、同学、挚友，要让自己的一生过得充满意义与价值，而不是苟延残喘地活在世上。

8天后回到机房，首先接到的就是出题的通知。之前由于好玩，也算是完成教练布置的作业吧，选了几道题组装成了一套卷子，没想到真的会考。于是回来的前两天我都在修改题面、造测试数据中度过。到了考试的那天，心中的石头终于落地，除了题目描述上出了些无关紧要的小问题外，没有出什么岔子，一切都非常顺利，而且受到了ljh学长的称赞。ljh还想出了T5的线性解法，要用到莫比乌斯函数，于是花了一个晚上加早上来学。

紧接着，wfj和ywj大神都开始出题了。在他们的影响下，我开始学习了左偏树和莫队算法。同时也学习了线性模方程组的解法、高斯消元和kd树的简单应用。这三场考试中犯下了不少不应该出的错误，但总体而言还是可以的，大多数题目都还是想出了正解，分数也还不算丑。

最后就到了两次大考，wc2017和hnoi模拟。万万没想到（其实早有征兆），这两次竟然考得难以置信的差。在所有人都只能打暴力的情况下，我的暴力能力似乎还有很大欠缺。细来想想，似乎很久没有去做部分分和非完美解法了，以至于在很多细小的地方出了差池。

整个寒假下来，从AK慢慢走到爆零，反映出的问题值得深思。自认为很厉害，可事实上又拥有什么能力呢？遇到真实的考试题型就出差错，是一种非常危险的状况。没有人会知道一个人在校内赛中考了多少次rank1，别人眼里看到的，只有wc、省选和noi的成绩。网管曾说，“我相信，只要你努力，进省队还是有希望的。”但从现在看来，似乎还差得有点远。同样是高一，有的人已经wc金牌签约清华，而我却只能在键盘前黯然神伤。长郡很小，世界很大。眼光如果只看着组内，看着小小的一方澄池，必定会如井底之蛙，看不见更宽广的蓝天。高二的学长拥有强大的实力，而兄弟校的同龄人亦比你优秀太多，因此，唯有拼搏、奋斗、挑战自己，才能走向远方，否则，便只能在高二的暑假后面对理所当然的失望了。

更新

52题计划截至2017年2月24日已完成42题。
所有集训期间的代码均上传至代码仓库oi代码仓库，代替原来用博客管理代码带来的时间效率上的问题。
近期不打算使用Latex了，虽然这个语言宣称能让人专注于内容，但事实上只会让人纠结于排版。Markdown是个好东西。

  1. echo "thanks for your reading\n";

长沙市长郡中学 刘俊琦

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注