数据结构

堆

注意：这些函数中num为形参。(懒得写指针了)

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
#include<stdio.h>
void heapUp(int *heap,int index)
{
    while(index>0)
    {
        int parent=(index-1)/2;
        if(heap[parent]<heap[index])
        {
            int mid=heap[index];
            heap[index]=heap[parent];
            heap[parent]=mid;
            index=parent;
        }
        else
            break;
    }
}
void heapDown(int *heap,int index,int num)
{
    int l=index*2+1;
    int r=index*2+2;
    int big=index;
    if (l < num && heap[l] > heap[big])
        big = l;
    if (r < num && heap[r] > heap[big])
        big = r;
    if(big==index)
        return;
    int mid=heap[index];
    heap[index]=heap[big];
    heap[big]=mid;
    heapDown(heap,big,num);
}
void insertheap(int *heap,int x,int num)
{
    heap[num++]=x;
    heapUp(heap,num-1);
}
int popheap(int *heap)
{
    return heap[0];
}
void deleteheap(int *heap,int num)
{
    heap[0]=heap[num-1];
    heapDown(heap,0,num-1);
}
int main()
{
    int heap[100100];
    int num=0;
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x;
            scanf("%d",&x);
            insertheap(heap,x,num++);
        }
        else if(op==2)
            deleteheap(heap,num--);
        else
            printf("%d\n",popheap(heap));
    }
    while(num>0)
    {
        printf("%d ",popheap(heap));
        deleteheap(heap,num--);
    }

    return 0;
}

单调栈(例题)

题目描述

Thiamine 班上现在要体检，全班 n(1≤n≤3×105)n(1≤n≤3×10^5) 位同学排成了一队，第 i 位同学身高为$ a_i(1≤a_i≤10^9)$ ，正如世界上没有两朵雪花一样，也没有两个同学身高一样。

因为大家还不是很熟悉，每个人都在前后看自己的同学是谁。每个人想知道自己都能看到谁，正如某老师所说，编程是一门体力活，对身体有很大的损伤，同学们的颈椎都受到了损伤，不能抬头，故：

  • 当$ j<i$ 时，第 $i 位同学能看到第位同学能看到第 j $位同学当且仅当 ak≤ai(j≤k≤i)a_k≤a_i(j≤k≤i)

  • 当 $j>i 时，第时，第 i $位同学能看到第 $j $位同学当且仅当 ak≤ai(i≤k≤j)a_k≤a_i(i≤k≤j)

输入

第一个数为数据组数$ T(1≤T≤10)$ ；

接下来 T 组数据，每组数据包含两行；

第一行一个正整数 $n(1≤n≤3×10^5) $代表排队的同学数；

第二行 $n $个正整数 ai(1≤ai≤109)a_i(1≤a_i≤10^9) 代表每个同学的身高。

输出

为减少输出量，对于每组数据，仅输出一个正整数，代表每位同学可以看到的其他同学的数目之和。

示例代码

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int a[n+1];
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        int myStack[n+1];
        ll ans=0;
        myStack[0]=0;
        int index=0;
        for(int i=1; i<n; i++)
        {
            while(a[i]>a[myStack[index]])
            {
                index--;
                if(index<0)
                    break;
            }
            if(index<0)
                ans+=1LL*i;
            else
                ans+=1LL*i-myStack[index]-1;
            myStack[++index]=i;
        }
        myStack[0]=n-1;
        index=0;
        for(int i=n-2; i>=0; i--)
        {
            while(a[i]>a[myStack[index]])
            {
                index--;
                if(index<0)
                    break;
            }
            if(index<0)
                ans+=1LL*(n-1-i);
            else
                ans+=1LL*(myStack[index]-i-1);
            myStack[++index]=i;
        }
        printf("%lld\n",ans);
    }

    return 0;
}