原题

传送门

题目大意

给出一串长为$2^n$的数字串，先将相邻的两个数字按位或，得到$2^{n-1}$的数字，再进行按位异或，反复进行这样的操作，直到只剩下唯一的数字。给出m个询问，每次将一个位置上的数字改成指定的数字，求最后得到的数字。

分析

这是一个单点修改区间求值的问题，可以使用线段树，只是合并的时候注意一下，需要对两个子区间的值或还是异或即可。

参考代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
int fun(int n,int k){
    int res=1;
    while(k){
        if(k&1) res*=n;
        n*=n;
        k>>=1;
    }
    return res;
}
int a[420000];
map<int,bool> mp;
void build(int root,int l,int r){
    if(l==r){
        scanf("%d",&a[root]);
        return ;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    if(mp[r-l+1]==1){
        a[root]=(a[root<<1]|a[root<<1|1]);
    } else {
        a[root]=(a[root<<1]^a[root<<1|1]);
    }
}
int query(int root,int l,int r,int x,int y){
    if(x<=l&&y>=r){
        return a[root];
    }
    int mid=(l+r)>>1;
    int ans1=-1;
    int ans2=-1;
    if(x<=mid) ans1=query(root<<1,l,mid,x,y);
    if(y>mid) ans2=query(root<<1|1,mid+1,r,x,y);
    if(ans1!=-1&&ans2!=-1){
        if(mp[r-l+1]==1){
            int ans=(ans1|ans2);
            return ans;
        } else {
            int ans=(ans1^ans2);
            return ans;
        }
    } else if(ans1!=-1){
        return ans1;
    } else if(ans2!=-1){
        return ans2;
    }
}
void change(int root,int l,int r,int x,int y){
    if(l==r){
        a[root]=y;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) {
        change(root<<1,l,mid,x,y);
    } else {
        change(root<<1|1,mid+1,r,x,y);
    }
    if(mp[r-l+1]==1){
        a[root]=(a[root<<1]|a[root<<1|1]);
    } else {
        a[root]=(a[root<<1]^a[root<<1|1]);
    }
}
void init(){
    mp.clear();
    int res=1;
    mp[res]=0;
    for(int i=1;i<=17;++i){
        res*=2;
        mp[res]=(i%2);
    }
}
int main(){
    int n,m;
    init();
    scanf("%d %d",&n,&m);
    int r=fun(2,n);
    build(1,1,r);
    while(m--){
        int p,b;
        scanf("%d %d",&p,&b);
        change(1,1,r,p,b);
        int ans=query(1,1,r,1,r);
        printf("%d\n",ans);
    }
    return 0;
}

首先，这个课程的开始形象化的表述了什么是计算机视觉，类比于人类的视觉，计算机视觉将摄像机等电子设备当作视觉器官来获取图像，然后使用电脑代替大脑进行分析，最终达到理解图像的目的。简而言之，计算机视觉是为了连通单纯的像素和理解意义。通过计算机学习，我们希望能从图片中获得的信息主要是两点：一是三维信息，即从图片这种二维载体中，恢复物体原本的三维信息；二是语义信息。计算机视觉的应用非常广泛。

接着，介绍了在计算机视觉中广泛采用的工具——线性代数和Matlab。将图像通过矩阵表示，运用矩阵的操作来操控图像完成一系列工作。矩阵的变换是其中重要的一点，例如缩放、旋转等。在实际进行计算机视觉工作时，我们经常需要进行仿射变换，为了方便进行这样的操作，引入了一个齐次坐标的概念，即将向量增加一维，并且新增的一维为1，与此同时，变换矩阵相应要增加一行，并且新增的一行，除最后一个元素为1外，其余都为0。本来平移操作是要通过矩阵的加法来完成的，但是通过增加一维后，乘法也变得可行。采用齐次坐标的方式完成仿射变换是一个常用的方式。同时还要关注矩阵的逆、矩阵的秩和矩阵的分解，如奇异值分解。奇异值分解是一种非常实用，且应用广泛的矩阵分解方式，可以用于图片的压缩。奇异值分解解决了特征值分解无法应用于非方阵的局限性，使得任何矩阵的分解成为了可能，运用主成分分析，即可完成图片的压缩。

在第四课中更加明确了图片在计算机视觉中地位，即将图片看作一个离散函数，以像素位置作为自变量，将该位置的像素的属性作为因变量。透过这个角度，使得对图像的处理成为可能，如通过过滤器就可以实现图像的降噪、超分辨率、修复等工作。过滤器常见的有移动平均和图像分割。要着重关注的两个特征：线性系统和平移不变系统。此外，卷积和互相关也常用于图像处理，但是两者都有边缘效应需要注意。同时应该注意两者之间的区别，卷积是一种滤波操作，而互相关是应用于比较相似度的。卷积和相关的计算有一定的相似度，但是卷积进行操作时要首先将卷积核旋转180度，而相关计算时则不需要，所以对于对称的卷积核，卷积和相关的结果是相同的，比如高斯核。

本章主要介绍了抽象数据类型库中比较重要的两种string和vector。

数据类型是程序的基础，本章主要介绍了内置类型，并且初步提起了一些自定义数据结构的相关内容。

基本内置类型

基本数据类型主要包括算数类型和空类型。
除开布尔类型和扩展的字符型，其他整型都分为带符号类型和无符号类型。
一般而言，将数据范围小的转化为数据类型大的不存在什么大问题，但是反之，常常会带来精度的丢失。同时，切记不要混用有符号类型和无符号类型，这常常会带来意想不到的错误。

变量

变量中需要着重区分初始化和赋值。初始化死在创建变量时赋予一个初始值，而赋值是用一个新值覆盖原来的值。
变量声明和定义也是一组要区分的概念，由于这两个常常同时发生，故具有一定的迷惑性。记住变量只能被定义一次，但能被多次声明。想要将声明和定义分开，就需要用到extren关键字。举一个例子：

1
2

extern int a; //声明a，但是没有定义
int b; //声明并定义b

复合类型

复合数据类型是指基于其他类型定义的类型，这里主要讲了两种：引用和指针。
引用相当于为已用的一个对象起了一个别名，它本身并不是一个对象，为此，引用只能绑定在对象，而不能与字面值或表达式的计算结果绑定。同时，这也决定了引用必须被初始化。
指针和引用有很多不同点。一是指针本身就是一个对象，二是指针无需在定义时赋值。
复合类型的复杂之处在于，它们是可以进行嵌套的。无论是指向指针的指针，还是指向指针的引用，都是具有相当的复杂度的。遇到这种情况，从右向左阅读，对理解有一定的帮助。
例如：

1
2

int *p;
int *&r = p; //r是一个对指针p的引用

const限定符

const对象不能执行改变其内容的操作。
对常量的引用不能修改它所绑定的对象。同时非常量引用不能指向一个常量对象，但是常量引用能绑定到非常量对象。例如：

1
2
3
4
5
6

const int a = 1024;
const int &r1 = a; //正确
const int &r2 = 1024;//正确
const int &r3 = r1 * 2;//正确
int &r4 = a;//错误，非常量引用不能指向常量对象
int &r5 = r1 * 2;//错误

注意到，常量引用能绑定到非常量对象，虽然不能通过常量引用修改值，但非常量对象本身的值可以轻易改变。

指针和const的关系要相对复杂一些，因为指针本身是一个对象，又指向了一个对象。
顶层const表示指针本身是个常量，底层const表示指针所指的对象是个常量。

1
2
3
4

int i=0;
int *const p1=&i;//顶层const
const int ci=42;//顶层const
const int *p2=&ci;//底层const

执行对象的拷贝时，顶层const还是底层const有明显的区别。
顶层const不受影响，拷入和拷出的对象是否是常量没有影响。
但底层const则有限制，拷入和拷出的对象必须具有相同的底层const资格，或者两个对象的数据类型必须能够转换。（一般是非常量转换为常量）

constexpr和常量表达式

常量表达式是指值不会改变并且在编译过程就能得到计算结果的表达式。
使用constexpr将变量声明为常量表达式，就可以由编译器验证变量的值是否为一个常量表达式了。
constexpr把它所定义的对象置为顶层const。

类型处理

类型处理的难度来自于两个方面，这两者都是由于程序的膨胀造成的。一是类型的名字的难记，二是弄不清所需的类型。

类型别名可以使用传统的typedef，或者使用新的别名声明；

1

using LL = long long;

但是类型别名如果指代复合类型或者常量，就常常容易出错。

将变量声明为auto可以让编译器去分析表达式所属类型，显然，auto定义的变量必须有初始值。
在涉及到复合类型和常量时，auto有几点要特别注意。
1、编译器以引用类型作为auto的类型；
2、auto一般会忽略顶层const；

decltype的作用时选择并返回操作数的数据类型；

1

decltype(f()) a = x;

decltype和auto不同的是，decltype返回该类型的类型，包括顶层const和引用。decltype的结果和表达的形式也是密切相关的。

1
2
3

int i=1, *p=&i;
decltype(*p) a = 1;//a的类型为int&
decltype((i)) b = 1;//b的类型为int&

decltype((variable))的结果永远是引用。
decltype处理的是一个解引用，得到的永远是引用。

这章主要浅显地介绍了C++中的一些基本概念，如类型、变量、表达式、语句及函数，还初步领略了一些C++中的类。

函数

一个函数的定义，需分为返回类型，函数名，形参列表和函数体。

输入输出

主要提到了iostream库，这个库包含两个基础类型istream和ostream，代表输入流和输出流。
标准库定义了四个io对象。用cin处理输入，表示标准输入。用cout处理输出，表示标准输出。还有cerr输出警告和错误信息，表示标准错误。clog输出程序运行的一般信息。
用<<（输出控制符）配合输出对象使用。其左边必须为ostream对象，右边为要输出的值。值得一提的是，其返回的仍是一个ostream对象，故<<可连续使用，例如cout<<a<<b是完全合法的。

控制流

控制流可以分为循环和分支。
控制常用while和for
分支常用if。