CSP_J 暑假清北学堂集训 第一天

数据结构 ：
数据结构：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;
        }
    }