数据结构 ：
数据结构：1.怎么写；2.怎么用
一、数组
1.负数下标是可以定义的:
1.变量局部开在栈空间里
2.数组全局变量开在堆空间里
3.数组越界会出现一些奇奇怪怪到小问题
处理方法:
int a[1000010];
int *b = a + 500000;
结果:
b[-233] -> a[500000-233];
b[-500000 ~ 500000];
栈：stack(简单一些)
queue<int> name
priority_queue<int> q;
priority_queue<int> heap_l;
priority_queue<int> heap_r;
map:
第一个int代表下标类型
第二个int代表元素类型
实现：
map<int,int> name;
操作：
map<string,int> 强过结构体呀
algorithm:
max(a,b); max(max(a,b),c)
min(a,b); min(min(a,b),c)
int c;
long long d;
min(c,d) 错误！必须同样类型
swap(a,b)换
sort排序（好东西）:
typename (int) a[100];
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(z + 1, z + n + 1); //把a[1] 到 a[n] 从小到大排序 （nlogn)
从大到小：
bool cmp(int a,int b)//返回ab后a是否应该排在b前面
｛
return a > b;
｝
sort(a + 1, a + n + 1,cmp);//从大到小 (相反数排序)
reverse(a + 1, a + n + 1);//翻转数组
unique:
unique(a + 1, a + n + 1) ; 把a[1] ~ a[n] 去重 but必须把数组排完序才能使用
int m = unique(a + 1, a + n + 1) - a - 1;去重完有几个数
random_shuffle:
random_shuffle(a + 1, a + n + 1) 把a[1] ~ a[n] 随机打乱
merge_sort:
归并排序根本思想： 分治，切几刀，分别排序，直到只剩一个数字，停下 （分） 比较两数列的最小值：min(a1,b1) min(a1,b2) ……（治）
merge_sort(int l, int r){
long long ans = 0;
if(r == l) return;啥也不用干
int m = (l + r) / 2;
ans += merge_sort(l , m);左边部分
ans += merge_sort(m + 1 , r);右边部分
int pl = l;左边第一个数的下标
int pr = m + 1;右边第一个数的下标
for(int i = l; i <= r; i++){
if(pl > m) b[i] = a[pr],pr++;左边没数了
else if(pr > r) b[i] = a[pl],pl++;右边没数了
if(a[pl] < a[pr]) b[i] = a[pl],pl++;左边少
else b[i] = a[pr],pr++,ans += m - p + 1;右边少
}
for(int i = l; i <= r; i++) a[i] = b[i];抄回来
return ans;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
merge_sort(1,n);
}
前缀和：
sum[i] = a1 + a2 + a3 + …… + ai
= a1 + a2 + …… + ar - a …… - al-1
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
cin >> m;
for(int i = 1; i <= m; i++){
int l , r;
cin >> l >> r;
cout << sum[r] - sum[l - 1];
}
注意：
1.用“\n”不用endl 差距真的很大(4s多)
2.快读代码实现：
int read(){
int x = 0;
char c = '?';
while(c < '0' || c > '9') c = getchar();
while(c > '0' && c < '9'){
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
3.不用快输，用cout就行
4.scanf用来 格式化： scanf("%d-%d-%d", &year, &month,&day);
5.速度排序：/ % < x < + - < & | ^ << >> < <= >= == !=
6.x << y == x * 2 ^ y
7.x >> y == x / 2 ^ y
map<string,string> b;
map当无限大数组用就行啦 /se
a[1] = 2; log级别速度
a[-2333] = 9 log级别速度 （所有）
b["hello"] = "world";
想怎么用就怎么用
慢！
不同类型间的关系可以用
线性结构：
struct shouxie_queue{//队列
int z[1000000];
int tail;
int head;
shouxie_queue(){//构造函数
tail = 1;
head = 0;
memset(z,0,sizeof(z));
//memset(z,-1,sizeof(z))
//memset(z,0x3f,sizeof(z))
}
void pop(){
head++;
}
void push(int x){
/*while(head <= x && x < z[tail]) 单调递增
tail --;
while(head <= x && x > z[tail])
tail --;*/
tail++;
z[tail] = x;
}
int front(){
return z[head];
}
int size(){
return tail - head + 1;
}
};
struct heap{//大根堆（二叉树）
int a[100000];
int n;
int top(){
return a[1];
}
int size(){
return n;
}
void push(int x){
n++;
a[n] = x;
int p = n;
while(p != 1){//根节点为一 不等于才需要换
int f = p / 2;
if(a[f] < a[p]){
swap(a[f], a[p]);
p = f;
}
else break;
}
}
void pop(){//弹出 每个节的值 都要大于子点的值
a[1] = a[n];
n--;
int p = 1;
while(p * 2 <= n){
int pp = 2 * p;//左儿子
if(pp + 1 <= n && a[pp + 1] > a[pp]) pp = pp + 1;
if(a[p] < a[pp]){
swap(a[p], a[pp]);
p = pp;
}
else break;
}
}
};//每个节的值 都要大于子点的值
//题目：给出序列，求每个区间的中位数 ll a[100000];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int l = 1; l <= n; l++){
heap_l.push(a[l]);
cout << 中位数 << endl;
int median = a[l];//当前中位数
for(int r = l + 1;r <= n; r++){
if(a[r] > median) heap_r.push(-a[r]);
else heap_l.push(a[r]);
while(heap_l.size() > heap_r.size() + 1){
int v = heap_l.top();
heap_l.pop();
heap_r.push(-v);
}
while(heap_r.size() > heap_l.size() + 1){
int v = heap_r.top();
heap_r.pop();
heap_l.push(-v);
}
if(heap_l.size() > heap_r.size()) median= heap_l.top();
else if(heap_l.size() < heap_r.size()) median= heap_r.top();
else median = (heap_l.top() - heap_r.top) / 2;
cout << median;
}
}