C 语言编译过程

• 源文本-------预处理，处理 define,include 等
• 预处理文本--------编译
• 汇编文本----------汇编得到二进制文件 .o
• 目标格式----------链接
• 可执行文件

二进制补码原理和 C 语言处理类型转换

• 二进制补码最高位本质是一个 \(-2^x\)
• 同时处理有符号和无符号整数比较时或者进行其它二元运算时，C 语言会默认无符号且均为正数。
• 编译器处理一个 -x 的表达式时，会先读 x 然后取反，所以 -2147483648 是不合法的，应该写为 -2147483647-1

简单的汇编语言

• 操作系统将物理内存抽象为了一个一维数组，所有汇编层面的操作均在一维数组内进行

• 每一条汇编指令都可以被描述为两个部分，指令和操作对象，这两部分的整体可以被一个或多个字节描述，此规则本质上是一颗哈夫曼树。

• 一个程序的汇编指令会被保存在主存上，有一个程序计数器 epi 指出当前执行到的地方。

• 常用寄存器名有 eax,ecx,edx,ebx,esi,edi,esp,ebp。前三者的数据由当前程序保存在栈中，后三者的值由下级程序保存，最后二者为帧指针和栈指针，一般不使用。前四个寄存器可以通过 ah,al,ax 等形式访问低二字节和低一字，但都可以用 di 形式访问低一字。

• 传送指令分为三种 movb movw movl 分别表示字节，字和双字。传送对应类型时，应该使用对应的寄存器位置。 push,pop 指令为压栈和弹栈，本质上是操作了主存和栈指针。

• lea 指令可以快速计算 a+b*(1,2,4,8)+c ，a 必须为常量，b,c 必须为寄存器中的数。

• 操作数分为三类，一类是立即数，一类是寄存器，一类是主存数据，访问格式如下。

  1 2 3 4 5 6 7 8 9 10

  $imm //立即数 imm eg. $0x3f E //寄存器 E eg. eax Imm(e1,e2,s) //主存上 Imm+e1+e2*s 位置上的数据，Imm 可以缺省，后二者可以缺省，e1 缺省时不能省略 ',' eg. 0x3f(eax,ebx,4) eg. (eax)

• 用 test 和 cmp 指令来控指条件，本质上，它们改变了条件寄存器内的值，test x x 等价于 cmp 0 x。执行 cmp 后，jl 等条件跳转语句会在 cmp 成立时执行，jl 表示小于时跳转，cmp x y 可以看作是 y<x 时执行 jl

• call 指令会将返回地址 (call) 语句后那条语句的地址入栈后跳转到函数所在位置。ret 指令利用返回地址跳转回去，一般来说，用 eax 保存返回内容。

• 由于程序寄存器中的某些值会被缓存到主存中，所以使用 gets 等不安全函数读取时，如果读取的内容过长超出了为此缓存区分别的字节后，会污染一些先前被存储在主存中的寄存器值，因为超出分配的内存后，会写在外面，通过这样的操作，我们可以改变一些系统寄存器的值，让程序跳转执行一些我们希望让它执行的代码（这样的代码通常被写在我们的输入里），这就是缓冲区攻击，通常操作是改变 ebp 的值使得 ret 操作跳到我们希望的地方。

语法，语法糖，标准库函数

介绍一些有用常用但鲜为人知的 C++ 语法，语法糖。

运算顺序

记好表，记不住打括号，最好打括号。

标准库

函数

std::swap

• 对于除了 array 容器之外的所有标准库容器，都可以 \(O(1)\) 交换

• 交换数组的复杂度为 \(O(size)\)，对二维数组的某一维使用，会将当前行视为一维数组进行交换。

memcpy

memcpy(dst, src, size)

dst:目标数组起始位置

src:源数组起始位置

size:需要复制的字节数

lower_bound,upper_bound

看下实现吧：

• upper_bound 如果对类使用，那么类的比较函数需要定义为友元函数。
• lower_bound 返回第一个大于等于它的位置，upper_bound 返回第一个大于它的位置，comp 为默认小于号。
• 如果要对不增序列操作，那么 comp 为大于号，lower_bound 返回第一个小于等于它的位置，upper_bound 返回第一个小于它的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (comp(*it, value)) {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }
    return first;
}
template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first,last);
 
    while (count > 0) {
        it = first; 
        step = count / 2;
        std::advance(it, step);
        if (!comp(value, *it)) {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }
    return first;
}

atan2

1
2
3
4

double atan2(double x,double y){
    //返回 [actan(y/x)],[-Pi,Pi)
    //计算几何的神，怎么神就不用说了吧。
}

for_each(begin,end,fun)

对 begin 到 end 区间的每一个元素 x，执行 fun(x)。

如果需要传参，可以利用类的构造函数。

即给类重载一个 () 运算，然后构造输出。

accumulate(begin,end,start)

对 begin end 区间运用 + 操作，起始为 start。

效率不开 \(O2\) 时略高于循环，开了没差别。

count(begin,end,val)

返回 begin end 中 ==val 的数的个数。

开了 \(O2\) 效率和循环没差别。

结构体

一般来说 class 和 struct 竞赛上差别不大，struct 是默认 public 的 class。

重载括号

重载小括号运算符可以让你把结构体当函数用，其实本质上少写了一个 .{function name}。

它和构造函数不冲突。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

struct barrett1{
	long long m,im;
	int operator ()(int a,int b){
		ULL z=(ULL)a*b;
		int v=z-((__int128)z*im>>64)*m;
		return v<0?v+m:v;
	}
}bt1;
int a=1,b=1;
int c=bt1(a,b);

struct barrett2{
	long long m,im;
	int foo(int a,int b){
		ULL z=(ULL)a*b;
		int v=z-((__int128)z*im>>64)*m;
		return v<0?v+m:v;
	}
}bt2;
c=bt2.foo(a,b);

两者没有本质区别。

中括号可以重载，一般来说，重载中括号返回的是一个引用，中扩号只接受一个参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct array_2d{
	int a[10005],b[10005];
    int n,m;
    void init(int nn,int mm){
    	n=nn,m=mm;
	}
    int& operator[](int x){
		return a[x];
    }
}a;
a.init(4,5);
a[3]=1;a.b[4]=2;
a[4]=4;
cout<<a[4]<<' '<<a[3]<<' '<<a[1]<<endl;

构造

结构体的构造函数可以返回一个结构体实例，也可以允许在声明结构体的时候同时构造。

举个例子

1
2
3
4
5
6
7
8
9
10

struct st{
    int a,b;string str;
    st(int aa,int bb){
        a=aa;
        b=bb;
    }
};
st t1=st(2,3);
st t2(2,3);
// st t3; 这句会 CE

这两种写法都行，注意不能变量重名，不会 CE，但是函数参数里会那个名字会覆盖掉全局的。

注意写了构造函数，所有的构造都必须带参数。

定义结构体的时候还可以给变量赋初值。

1
2
3
4
5
6
7
8
9
10
11
12

struct st{
    int a,b=1;string str="str";
    st(int aa,int bb){
        a=aa;
        b=bb;
    }
};
st t1=st(2,3);
st t2(2,3);
// t1.str="str",t1.b=3
// t2.str="str",t2.b=3

但是如果构造函数里写了，就会被覆盖。声明的局部变量写了的初值会固定，没写的初值就随机。

如果没写构造函数，那么会有一个默认的列表构造函数，按照结构体内声明变量的顺序将列表中的每一个值依次赋给对应变量。

1
2
3
4
5
6

struct st{
    int a,b=1;string str="str";
};
st t1=st{2,3,'huan_yp'};
st t2{2,3,"huan_yp"};

其实构造函数还有另一种写法

1
2
3
4
5
6

struct st{
    int a,b;string str;
    st(int aa,int bb): a(aa), b(bb) {}
};
st t1=st(2,3);
st t2(2,3);

和最开始的写法是等效的。

注意，如果写了构造函数，默认的列表构造函数会调用它，所以如果你想不同参数个数构造，需要填默认参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct st{
    int a,b;string str;
    st() :a(), b(), str(){}
    //如果没有这一行，下面的第一个构造会 CE
    
    
	st(int aa, int bb,string cc) :a(aa), b(bb), str(cc){}
//    st() :a(), b(), str() {}
//    st(int aa,int bb): a(aa), b(bb) {}
};
st t1;
t1={2,3,"str"};
t1={2,3};
//最后一行会 CE

列表构造式还可以自推导。

1
2
3
4
5
6
7
8
9
10
11

struct st{
    int a,b=1;string str="str";
    st(int aa,int bb){
        a=aa;
        b=bb;
    }
};
st t1={2,3};
t1={3,4};
//t1(2,3)
//括号式式不能自推导的，这个的含义参考第一条。

语法概念

运算优先级

容易出问题的是几个位运算。

永远记住，位运算除了左右移位外，优先级低于比较操作。

比较操作之间，等于和不等的优先级低于大于小于。

引用

引用可以认为是一个隐式指针，不需要 * 的修饰便可以直接访问内容。它既然是一个指针，自然会占用一个 long 的空间。

定义，返回一个引用

可以在函数中返回一个引用，只需要在函数名前面后加一个 &，定义引用也在变量名加一个 &，和指针类似。

1
2
3
4

double &setValues(int i) {  
   double &ref = vals[i];    
   return ref;   // 返回第 i 个元素的引用，ref 是一个引用变量，ref 引用 vals[i]
}

定义引用的示例：

1
2
3
4
5
6
7
8

int n=0,m=0;
int& nn=n,mm=m;
n=10,m=20;
printf("n,m:%d,%d\n",n,m);
printf("nn,mm:%d,%d\n",nn,mm); 
//输出:
//10,20
//10,0

在重载结构体 +=,= 运算符号的时候比较常用。

引用传参应该已经很熟悉了吧。

左值引用和右值引用

C++11 新概念。参考阅读

一般的，使用引用传参时，如果接受的参数为右值，那么不能修改右值，参数必须声明为 const 类型。

算了，先咕咕咕了吧。

模板

如果用的不好，容易出现找不到实现的问题。

一个原则：所有东西的类型必须在使用前就得知。

类模板

继承的时候需要写明父类的类型参数，如果子类也是模板类，可以用子类的类型模板参数作为父类的类型模板参数。

函数模板

函数模板是可以自动推导类型的，如果出现类型冲突，那么会报 CE。

常见例子是 std::max(1,1ll) 报错。

注意字面量的类型。

指定模板参数可以仅指定一段前缀，剩下的采用自动推导。

多文件的一些问题

按惯例编写的问题

通常情况下，你会在 .h 文件中声明函数和类，而将它们的定义放置在一个单独的 .cpp 文件中。但是在使用模板时，这种习惯性做法将变得不再有用，因为当实例化一个模板时，编译器必须看到模板确切的定义，而不仅仅是它的声明。

定义和声明一起写

可以将模板的声明和定义都放置在同一个 .h 文件中。这就是为什么所有的 STL 头文件都包含模板定义的原因。

习惯来说，一般把这种包含定义的头文件后缀名写为 .hpp。

使用 export

咕咕咕

Static 关键字

声明一个静态的东西，可以用来避免命名冲突，也可以用来更好的实现一个类。

Static 关键字声明的东西生命周期是整个程序的生命周期，但作用域仅限定为声明处的作用域。

举个例子，某个函数的执行过程和它被调用的次数有关，这个可以弄个全局变量记一个次数，但是我们也可以在它的内部写个 static 变量记录，这样就不会与外部空间变量名冲突。

所有静态变量的初始值为 0

1
2
3
4
5
6
7
8

int cnt=0;
void fun(){
	static int cnt;
	cout<<++cnt<<endl;
}
fun();cnt=10;
cout<<cnt<<endl;
fun();fun();cnt++;fun();

也可以用静态成员来维护一个类，比如写链表的时候，我们通常要先写个 node 类，然后才能实现 list 类，但我们可以直接将 head 指针作为一个静态变量放入结构体中，这样，这个静态变量就可以被所有结构体的实例访问修改。

注意，如果需要两个链表，那种这种方式是不可取的，因为静态变量 head 对所有该结构体的实例来说都只有一个。

我们当然也可以声明静态成员函数。

对于结构体的静态资源，我们可以用 {结构体名}.{成员名} 来访问。

函数，匿名函数

C++ 的函数名，本质上是一个指向某个函数的指针，函数在二进制层面和数据没有差异。

functor (一般译为算子)，也可以调用，但它是一个对象。

函数类

C++ 的函数可以当作一个对象处理的，函数名是指向该对象的指针，比如说：

1
2
3
4
5
6
7

void add(int &x){x++;}
void del(int &x){x--;}
void doit(int &x,function<void(int&)> f){(x);}
n=10;doit(n,del);
printf("%d\n",n);
n=20;doit(n,add);
printf("%d\n",n);

匿名函数

格式：["捕获列表"]("参数列表")->"返回类型"{"函数体"}

捕获列表指的捕获局部变量，在函数中可以使用和修改。

参数列表无参数时可以省略，返回值如果不指定则会自动推导。

捕获列表不可省略，[] 为强制不捕获，[&] 为引用捕获全部，[=] 为取值捕获全部，也可以用变量名 [x,&y] 取值捕获 x，引用捕获 y。

1

sort(v.begin(),v.end(),[](const int &x,const int &y){return x>y;}); //降序排序

匿名函数也可以作为一个对象处理。

虚函数

这个东西自己写的时候用的比较少，毕竟不太注重面向对象，

这玩意和 Python 的 abstract_method 类似，我也不知道怎么解释，反正会用就够了。

竞赛中应用的话，可以用来重写 pd_ds 里面的平衡树，但是真的用的很少。

语法糖

函数相关

返回值为 void 的函数

你是否碰到过这样的情况，函数返回值为 void，但是返回又是有条件，并且还需要执行一些简单的操作，用 {} 括起来显得代码冗长，不妨试试：

1
2
3
4
5
6
7

void do_cool_thing(int arg){
	if(some_condition) return void(a_simple_expression);
    do_cool_thing(arg);
}
void do_cool_thing(int arg){
	if(some_condition) return void(ans++);
}

有返回值的函数

, 可以用在 return 语句，会返回最后一个值，当然也可以用在其它 Case。

1
2
3
4
5
6
7

int get_v(){
	return 3,5;// return value is 5
}
int new_node(int x){
    return a[++t]=node{mt_rand(), 1, x, 0, 0}, t;
    //can you guess what it do and when we use it?
}

列表初始化器

这东西说白了就是 {1,2,3,4,5} 这种，注意区分类成员初始化器，后者可以多类型，前者只能单类型。

循环

1
2
3

for(int v:{0,1}){
	do_cool_thing();
}

分支更少，效率更高，代码更优美！

树链剖分

常用的树链剖分有重链剖分，实链剖分和长链剖分。

长链剖分主要用于部分和深度有关的树形 \(dp\) 的优化，一般采用指针数组实现。

我们说的树链剖分一般指重链剖分，即选择每个点子树最大的儿子。

不难证明从任何一个点到根都只会经过 \(log_n\) 条重链，这也是其复杂度的保证。

可以将每条重链用一个数据结构维护起来，就能做树上操作了。

动态树

动态树是基于实链剖分的数据结构，非常强大，但编码复杂度相对较高。

我使用的是基于 \(splay\) 的动态树。

动态树维护的是若干实链，每个实链用一颗平衡树维护。

动态树的核心操作是 access，意味将目标点 \(x\) 到根的路径全部打通，并且只包含这条路径。

其它操作简要介绍一下实现：

make_root :先 access，然后把 \(x\) splay 到根，然后翻转整颗 \(splay\) ，因为 \(splay\) 外的形态没有改变，所以只要 \(splay\) 内部的形态正确，那么整棵树的形态就正确，如果对于一个 \(splay\) 所有的节点交换了左右儿子，那么就是倒序了这颗 \(splay\) ，\(x\) 又是深度最大的点，所以这样是正确的。

link :很简单，直接将目标点 \(x\) splay 到当前根，当然，注意到原树之间的关系是 \(splay\) 根节点的关系，\(splay\) 根节点的父亲其实是 \(splay\) 中深度最小的点的父亲，然后改父亲改成 \(y\) 就行。

cut :假设有一个虚根 \(0\)，把 \(x\) make_root ，把 \(y\) access 然后 splay \(y\),直接双向断开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

void push_up(int rt){}
//该更新的要更新
void push_down(int rt){}
//旋转标记和其它标记的 push_down
bool isroot(int rt){return T[T[rt].fa].son[0]!=rt&&T[T[rt].fa].son[1]!=rt;}
void rotate(int x)
{
	int y=T[x].fa,z=T[y].fa,o=T[y].son[1]==x,b=T[x].son[o^1];
	if(!isroot(y))T[z].son[T[z].son[1]==y]=x;
	T[y].fa=x;T[x].son[o^1]=y;T[x].fa=z,T[y].son[o]=b,T[b].fa=y;
	push_up(y),push_up(x);
    //已经很熟的 rotate 操作
}
void splay(int x)
{
	int u=x;st[++top]=u;
	while(!isroot(u))u=T[u].fa,st[++top]=u;
	while(top)push_down(st[top--]);
    //记得先 push_down
	
	for(int y=T[x].fa;!isroot(x);y=T[x].fa)
	{
		if(!isroot(y))rotate((T[T[y].fa].son[1]==y)==(T[y].son[1]==x)?y:x);
        //双旋，其实一般单旋也不会卡。
		rotate(x);
	}
    //亲切的 splay 操作
}
void access(int x,int y=0)
{
    //记得断开和儿子的连接
    //splay 之间是原树的关系连接，但 splay 内部维护的只是一条链，中序遍历 splay 才能得到原树
	for(;x;y=x,x=T[x].fa)
	{
		splay(x);T[x].son[1]=y;
		push_up(x);
	}
}

虚树：

一般用来处理询问很多但规模不大的树上问题。

点分治

用来处理树上路径的计数问题，特别是路径长度相关

后缀排序

对一个字符串的所有后缀排序，约定 \(sa[i]\) 表示排名为 \(i\) 的后缀的起始位置，约定 \(rk[i]\) 表示起始位置为 \(i\) 的后缀的排名。\(height[i]\) 为排名为 \(i,i-1\) 的后缀的 \(lcp\) 。

先按第一个字母基数排序一遍，然后倍增法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

for(i=1;i<=n;i++)sum[rk[i]=ch[i]]++;
for(i=1;i<=128;i++)sum[i]+=sum[i-1];
//统计 sum,sum[i] 表示关键字比 i 小的总个数，然后遍历的时候，用每个后缀当前排名访问 sum，
//得到 sum[rk[i]] 为以 i 为起始位置的后缀的排名。
//访问后 sum 需要自减。
//但并不记录这个排名，因为它不准确，相同的会认为是不同，记录排名为 sum[rk[i]] 的后缀的起始位置。
for(i=n;i>=1;i--)sa[sum[rk[i]]--]=i;
for(i=1;i<=n;i++)tp[i]=rk[i];
for(i=1;i<=n;i++)rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]])?m:++m;
//这里重新计算每个后缀的排名，我们可以简单由 sa 数组得到。
for(k=1;;k<<=1)
{
    m=s=0;
    for(i=n-k+1;i<=n;i++)tp[++s]=i;
    //这些第二关键字为 0 ，所以仍在最前面
    //tp[i] 在这里表示第二关键字排名为 i 的后缀的起始位置
    //这里在按第二关键字安排顺序，第一遍在外面排序的时候不关心第二关键字
    //在倍增里排序关心第二关键字，我们只需要按第二关键字的顺序访问 sum，就能得到正确顺序。
    for(i=1;i<=n;sum[i++]=0)if(sa[i]>k)tp[++s]=sa[i]-k;
    //同样是处理第二关键字，按照上一轮排名顺序遍历即可。
    //位置减去 k,得到第二关键字的起始位置。
    for(i=1;i<=n;i++)sum[rk[i]]++;
    for(i=1;i<=n;i++)sum[i]+=sum[i-1];
    for(i=n;i>=1;i--)sa[sum[rk[tp[i]]]--]=tp[i];
    //同样的道理，只不过是按第二关键字大小顺序遍历
    for(i=1;i<=n;i++)tp[i]=rk[i];
    //这里的 tp 用来拷贝 rk,因为 rk 在计算时会改变
    for(i=1;i<=n;i++)rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?m:++m;
    //计算每个后缀当前排名
    if(m==n)break;
    //后缀排序结束后退出。
}
//计算 height 数组
//height 数组满足 height[sa[i]] >= height[sa[i]-1] - 1
//如果 sa[i] = 1，那么 height 没定义，不管。
//原因很简单，以  排名在以 sa[i]-1 为起始点的后缀 x 前一个的后缀 y。
//由定义 lcp(x,y) = height[sa[i]-1]
//将 x 删掉最前一个字符得到以 sa[i] 为起始点的后缀 a， y 删掉最前一个字符得到 b
//那么 lcp(a,b) = lcp(x,y)
//显然 b 排在 a 前面
//显然排名在 a 前一位的那个后缀与 a 的 lcp 不可能少于 height[sa[i]-1]
for(i=1;i<=n;i++)
{
    height[rk[i]]=max(0,height[rk[i-1]]-1);
    if(rk[i]==1)continue;
    while(ch[i+height[rk[i]]+1]==ch[sa[rk[i]-1]+height[rk[i]]+1])height[rk[i]]++;
}

莫队

莫队是暴力数据结构，将询问离线后，以较低的复杂度移动左右端点，然后处理询问。

设移动端点的复杂度为 \(O(x)\) ，那么莫队复杂度为 \(O(n \sqrt n\times x)\)，无法将 \(x\) 放在 \(\sqrt n\) 下面。

常见的卡常技巧有奇偶性排序等。

如果只能支持插入和删除中的一种操作，那么可以使用回滚莫队，拿一个栈记录操作，基于操作的撤销实现插入或删除。

树上莫队和普通莫队区别不大。

(差一个二次离线要补)

拓展KMP

咕咕咕

树哈希

一般来讲，可以这么哈希，再加上树大小的判断，就不会出问题。 \[ f_{now}=1+\sum f_{son(now,i)} \times prime(size_{son(now,i)}) \]

但这个哈希是有错的，可以对最小括号序列哈希。

具体的，一颗无标号有根树按照遍历顺序可以得到一个括号序列，即将子树的括号序列拼起来再套一个括号。

然后考虑对这个括号序列哈希，因为遍历顺序无关，所以要最小括号序列。

实际上可以直接对子树哈希值排序之后，按这个顺序往后写，外面添一层括号，对括号序列（二进制串）哈希。

关于某道题的优化

题意

给定一个长度为 \(n\) 的序列 \(a_i\)，求有多少个区间满足每个数出现次数均为偶数。

\(n\leq 3\times 10^4,a_i\leq 10^6\)

思路

双指针扫描每个区间，拿个桶，\(O(1)\) 更新状态，然后 \(O(n^2)\)，可以得到 \(40\) 的好成绩。

代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=30005;
int i,j,k,n,s,t,m,ans;
int a[N],b[N];
unsigned cnt[1024*1024];
signed main()
{
 	freopen("gf.in","r",stdin);
	freopen("gf.out","w",stdout);
	//freopen(".in","w",stdout);
	read(n);
	for(i=1;i<=n;i++)read(a[i]),b[i]=a[i];
	int now=0;
	for(i=1;i<=n;i++){
		
		memset(cnt,0,sizeof(cnt));
		now=0;
		for(j=i;j<=n;j++){
            if(cnt[a[j]])now+=(cnt[a[j]]&1)?1:-1;
			cnt[a[j]]+=1;
			ans+=now==0;
		}	
	}
	cout<<ans<<endl;
	return 0;
}

优化

1.高速缓存原理

计算机有个东西叫高速缓存，可以优化内存访问延迟。

一次独立的内存操作会读取一个 \(64Byte\) 的 \(cacheline\)，从指令发出到从内存收到数据需要约 \(200\) 个 \(CPU\) 周期，而 \(CPU\) 会将一些常用的数据塞进 \(cache\)，也就是高速缓存中，加速读取，寄存器的访问速度是最快的，只需要不到 \(1\) 个时间周期，\(L1\) 缓存需要约 \(3\) 个时间周期，\(L2\) 为 \(10\) 个左右，\(L3\) 为 \(20\) 个周期。

具体时间视计算机本身有差别，但基本的比例是这个。

代码一中，我们只关注瓶颈。

1
2
3
4

now+=-1+((cnt[a[j]]&1)<<1);
now+=!cnt[a[j]];
cnt[a[j]]+=1;
ans+=now==0;

其中，对于 cnt 的访问和对于 a 的访问，由于高速缓存并不大，所以塞不下 cnt，因此我们每个循环都需要等一个 200 时间周期的延迟，这是相当致命的，实际上等待的延迟并没有 200 时间周期，因为 \(CPU\) 将部分数据还是放进来 cache，但具体放哪些是由 CPU 决定的。

对于这个致命的延迟，我们可以将数据离散化，然后就可以得到一个 75pts 的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=30005;
int i,j,k,n,s,t,m,ans;
int a[N],b[N];
unsigned cnt[1024*30];
signed main()
{
 	freopen("gf.in","r",stdin);
	freopen("gf.out","w",stdout);
	//freopen(".in","w",stdout);
	read(n);
	for(i=1;i<=n;i++)read(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);m=unique(b+1,b+n+1)-b-1;
	for(i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	int now=0;
	for(i=1;i<=n;i++){
		
		memset(cnt,0,sizeof(cnt));
		now=0;
		for(j=i;j<=n;j++){
			if(cnt[a[j]])now+=cnt[a[j]]&1?1:-1;
			cnt[a[j]]+=1;
			ans+=now==0;
		}	
	}
	cout<<ans<<endl;
	return 0;
}

2.流水线模式和延迟隐藏

现代计算机各类硬件的设计都采用了流水线模式，将每条汇编指令的执行都划分为了不同的流水线。

也就是说 CPU 可以不间断的向内存发出访问指令，这些指令经过一定延迟后，内存会不间断的向CPU传数据，这个过程中，我们就只等待了一个内存延迟。打个比方，这玩意就像烧水，水壶很多，灌水和倒水的时间都很短，所以正确的方式是全部烧上等，而不是烧一个等一个。

所以，如果我们能够连续的发出内存访问指令，那么内存延迟可以被有效隐藏，但注意到代码中，访问了内存后执行了一些计算，而内存访问是依赖于这些计算的，这产生了一个依赖，我们必须等待计算完成之后才能进行访问，所以无法有效的隐藏延迟。

向内存写入数据也是需要等待延迟的。

3.流水线和依赖分析

上一部分简单介绍了流水线模式，在我们的 \(CPU\) 中，也采用流水线的设计。

一条汇编指令的执行在 \(CPU\) 上大致分为五个部分，分别是：取指，访(寄)存，计算，内存操作，写回。

\(CPU\) 在这五个部分的设计上也采用了流水线，一条指令开始访存时，另一条指令的取指就开始了。

而如果下一条指令对前一条指令有数据依赖，那么 \(CPU\) 会通过转发操作消除这种依赖，但如果下一条指令的内容对上一条指令有依赖（比如说 if），那么 \(CPU\) 就不得不停止流水线，向流水线中插入气泡以等待。

这会极大降低 \(CPU\) 的利用率，因此，内循环中的 \(if\) 是相当不应该的。

4.流水线和分支预测

事实上，硬件的设计者注意到了这种依赖，而 \(CPU\) 会对这种依赖做出预测，预测基于程序计数器的的原理和一些其它统计数据，正确率约在 \(65\%\) 左右，如果分支预测出现错误，那么会花费两个时间周期去消除这个错误，所以我们需要通过算术方式避免分支。

方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
template<typename _type>
inline void read(_type &x){
	x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch>'9'||ch<'0'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}x*=f;
}
template<typename _type1,typename _type2>void cmin(_type1 &a,const _type2 b){if(a>b)a=b;}
template<typename _type1,typename _type2>void cmax(_type1 &a,const _type2 b){if(a<b)a=b;}
const int N=30005;
int i,j,k,n,s,t,m,ans;
int a[N],b[N];
unsigned short cnt[1024*30];
signed main()
{
 	freopen("gf.in","r",stdin);
	freopen("gf.out","w",stdout);
	//freopen(".in","w",stdout);
	read(n);
	for(i=1;i<=n;i++)read(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);m=unique(b+1,b+n+1)-b-1;
	for(i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	int now=0;
	for(i=1;i<=n;i++){
		
		memset(cnt,0,sizeof(cnt));
		now=0;
		for(j=i;j<=n;j++){
			now+=-1+((cnt[a[j]]&1)<<1);
			now+=!cnt[a[j]];
			cnt[a[j]]+=1;
			ans+=now==0;
		}	
	}
	cout<<ans<<endl;
	return 0;
}

目前是最快代码。

一些 AI 相关的资料

GPU 编程

• GPU 编程
• CPU,GPU 内存缓存原理以及相关内容在 CUDA 上的应用